1

我有类似于以下的多边形链...

替代文字

...给定图像中的链，我将如何计算定义相同形状但没有交叉路径的链？

具体来说，对于图像的输入链，我想要的结果如下所示：

A1 ,
A2 , A2和A3
之间的 相交 , A3和A4之间的相交, A4 , A5 , A3和A4 之间的相交, A3 , A3和A2 之间的相交, A6






我正在寻找一种算法来为任何链完成此任务，但我不确定我正在尝试做的事情是否被调用，这使得寻找解决方案变得很棘手。

如果我正在尝试做的事情有一个名字，那么了解它会很有帮助。

感谢您的任何帮助！

4

1 回答 1

3

这是一个简单的算法：

for each line segment in the chain:
    Identify any segments which cross this segment
    If crossings > 0
         Follow the branch to the right, if this doesn't lead back to the 
         current intersection follow the branch to the left
    go to the next line segment

如果跟随一个分支在到达链的末端之前没有回到那个交叉点，这意味着你已经跳过了一个循环，所以你需要选择另一个分支。

对于您的示例，运行此算法将产生

Start at segment A1-A2
No intersections, goto next
Segment A2-A3
Intersection A2-A3/A6-A5 choose right path and store the current intersection somewhere
Segment A6-A5
Intersection A6-A5/A4-A3 choose right path and store intersection
Segment A3-A4
A4-A5
A5-A6
Back at intersection A6-A5/A4-A3, go right again to be back on A4-A3
A3-A2
Back at intersection A2-A3/A6-A5, go right again
Finish
于 2010-06-04T04:42:37.673 回答