Circular Path algorithm

Question

I am stuck at developing a circular path algorithm creating a path out of points. This is the array I am starting with:

(1,1)
(1,6)
(2,2)
(2,5)
(4,1)
(4,2)
(6,5)
(6,6)

These are points in a coordinate system and I want to be ordered so I only need horizontal or vertical lines between the adjacent points. So the sorted array needs to look like this

(1,1)        (A,H)
(1,6)        (A,B)
(6,6)        (C,B)
(6,5)        (C,D)
(2,5)        (E,D)
(2,2)        (E,F)
(4,2)        (G,F)
(4,1)        (G,H)

EDIT: These points are extracted out of the different edges. Every edge is defined by two points. There are no edges which overlay each other.

Edge: (1,1) -> (1,6)
Edge: (1,6) -> (6,6)
Edge: (6,6) -> (6,5)
Edge: (6,5) -> (2,5)
Edge: (2,5) -> (2,2)
Edge: (2,2) -> (4,2)
Edge: (4,2) -> (4,1)
Edge: (4,1) -> (1,1)

Thank you for any help!

Answer 1

Supposing, than edges must alternate (every vertical to be followed by horizontal and vice versa), algorithm may be the following:

P = input // collection of points
EH = []   // collection of horizontal edges
EV = []   // collection of vertical edges

sort P by x, then y         // (1,1), (1,2), (1,4), (1,6), (2,2), (2,5), ...
for (i = 0; i < P.size; i += 2) 
    if P[i].x != P[i+1].x return   // no solution
    EH.add(new edge(P[i], P[i+1]))

sort P by y, then x         // (1,1), (4,1), (2,2), (4,2), ...
for (i = 0; i < P.size; i += 2)
    if P[i].y != P[i+1].y return   // no solution
    EV.add(new edge(P[i], P[i+1]))

// After this, every point belongs to 1 horizontal egde and 1 vertical
// If exists closed path which traverses all points without overlapping, 
// such path is formed by these edges

S = []          // path
S.add(EH[0])
cp = EH[0].p2   // closing point 
p =  EH[0].p1   // current ending point
find edge e in EV where e.p1 = p or e.p2 = p
if e not found return empty path      // no solution
S.add(e)   
if p = e.p1
    p = e.p2
else
    p = e.p1
while (p != cp) {
    find edge e in EH where e.p1 = p or e.p2 = p
    if not found return empty path    // no solution
    S.add(e)
    if p = e.p1           
       p = e.p2
    else
       p = e.p1
    find edge e in EV where e.p1 = p or e.p2 = p
    if not found return empty path    // no solution
    S.add(e)
    if p = e.p1 
       p = e.p2
    else
       p = e.p1
}
return S 

To simplify edge search, mentioned collections EV and EH may be implemented using hash maps (point, point), where for each actual edge e(p1, p2) two entries should be put: p1->p2 and p2->p1. Every point belongs to 1 horizontal and 1 vertical edge, so entries won't be overwritten. Thus second part of algorithm may be simplified:

while (p != cp) {
    get from EH point pp by key p
    if not found return empty path    
    S.add(new edge(p, pp))
    p = pp
    get from EV point pp by key p
    if not found return empty path    
    S.add(new edge(p, pp))
    p = pp
}