循环路径算法

Question

循环路径算法

algorithmpath-findingcircular-dependency

4

我被困在开发一个圆形路径算法的过程中，该算法要从点中创建一条路径。这是我要开始处理的数组：

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

感谢任何帮助！

- Phil Niedertscheider

1

这不是排序，只是某种类型的排序。如果它是排序，你可以取任意两个点并告诉哪一个“更大”，哪一个“更小”。在这里，下一个项目的顺序取决于前面的顺序。 - Alex Salauyou

据我理解，您在尝试构建一个连接N个点的圆形路径，其中每条边必须是水平或垂直的，并且每个水平边必须跟随垂直边，反之亦然。如果对于任何给定的x或y坐标，您只有0或2个点（如您的示例中所示），则存在一条这样的路径（不考虑遍历方向），并且可以很容易地恢复。如果对于任何给定的x或y，可以有任意偶数个点，则问题变得更加困难。 - Alex Salauyou

你说得对。排序是我问题的正确定义。我能够回到一步，那里我有由两个点定义的不同边缘，我想这样使用点会更容易，但我忘记了两个边缘可能使用相同的点的可能性。 - Phil Niedertscheider

边缘是否可以相交？ - Alex Salauyou

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - RaGe

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex Salauyou · Accepted Answer

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

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。每个点属于一个水平边缘和一个垂直边缘，因此条目不会被覆盖。因此，算法的第二部分可以简化:

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
}