圆形路径算法

Question

我坚持开发一种圆形路径算法，创建一个点外的路径。这是我开始的数组：

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

感谢您的帮助！

Answer 1

假设，边缘必须交替（每个垂直后跟水平，反之亦然），算法可能如下：

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

为了简化边搜索，提到的集合 EV 和 EH 可以使用哈希映射（点，点）来实现，其中对于每个实际边 e(p1, p2) 应该放置两个条目: p1->p2 和 p2->p1。每个点都属于 1 个水平边缘和 1 个垂直边缘，因此条目不会被覆盖。因此可以简化算法的第二部分：

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
}

圆形路径算法

Circular Path algorithm

algorithm

path-finding

circular-dependency