# Q：循环路径算法

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!

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)
``````

``````(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)
``````

``````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)
``````

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

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

// 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
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 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 p = e.p1
p = e.p2
else
p = e.p1
find edge e in EV where e.p1 = p or e.p2 = p
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
p = pp
get from EV point pp by key p
p = pp
}
``````

``````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

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

// 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
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 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 p = e.p1
p = e.p2
else
p = e.p1
find edge e in EV where e.p1 = p or e.p2 = p
if p = e.p1
p = e.p2
else
p = e.p1
}
return S
``````

``````while (p != cp) {
get from EH point pp by key p