python - 你如何找到折线中循环的位置？

Question

我想检测描述折线中循环的位置（即多边形）。例如，下面的折线有 3 个循环。

我有代码来确定两个线段是否相交，但想找到与循环对应的区域：

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y

def ccw(A,B,C):
    return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)

def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

这是上图的代码：

import pylab

points = [
    [-326.0419254504, -160.71836672119],
    [-144.5703805370, 3.89159459966009],
    [-163.5692598748, 142.014754139665],
    [-260.4767655176, 108.905787255049],
    [-142.6710783719, -46.249469979213],
    [-22.96021284291, 16.1890735212646],
    [ 86.29780272233, 106.064044401492],
    [ 196.5051938150, 124.986746707329],
    [ 161.3537057610, 76.7377751584564],
    [ 130.0004832662, 133.499810130049],
    [ 211.7040108463, 212.968452780035],
    [ 279.1609152616, 124.043058681519],
    [ 219.3115560361, -57.600537709290],
    [ 52.09696347526, -149.37169880679],
    [-52.41376323308, -165.45492932181],
    [-24.86101299577, -200.45984531646],
    [ 1.741836268130, -113.42121703400],
    [-200.6288906555, -155.99195627907],
]

x, y = zip(*points)

pylab.figure()
pylab.plot(x, y, 'g', lw=5)
pylab.show()

Answer 1

效率不高，但易于实现：

• 沿折线按顺序尝试每个线段 A，

• 对于每个段 A，尝试所有后续段 B，按照折线的顺序，

• 如果您检测到 A 和 B 之间的交叉点，则您发现了一个循环；从段 B 继续扫描；

• 如果您没有检测到交叉点，那么您就完成了 A 段，继续扫描。

---

更有效但更复杂的解决方案是

• 使用线段相交算法，例如 Bentley 和 Ottmann；

• 按第一段的索引对交叉点进行排序；

• 循环将奇数编号连接到偶数编号的交叉点。