找到你要的答案

Q:Circular Path algorithm

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)

谢谢你的帮助!

answer1: 回答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
}

假设,比边必须交替(每一个垂直,其次是水平的,反之亦然),算法可能如下:

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
}
algorithm  order  path-finding  circular-dependency