0

ポリラインのループを表す位置 (つまりポリゴン) を検出したいと考えています。たとえば、次のポリラインには 3 つのループがあります。

ここに画像の説明を入力

2 つの線分が交差しているかどうかを判断するコードがありましたが、ループに対応する領域を見つけたいと考えています。

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

1 に答える 1

0

効率的ではありませんが、実装は簡単です:

  • ポリラインに沿ってすべてのセグメント A を順番に試し、

  • すべてのセグメント A について、ポリラインに沿って順番に、後続のすべてのセグメント B を試します。

  • A と B の交差を検出した場合は、ループが見つかりました。セグメント B からスキャンを続行します。

  • 交差点が検出されない場合は、セグメント A の処理は終了です。スキャンを続けます。

より効率的ですが、より複雑なソリューションは次のとおりです。

  • Bentley や Ottmann などの線分交差アルゴリズムを使用する。

  • 最初のセグメントのインデックスで交差点を並べ替える。

  • ループは、偶数番号の交点に奇数番号を結合しています。

于 2021-08-04T06:52:30.900 に答える