交差しない線のセットがあり、そのうちのいくつかは頂点で接続されています。特定の点を囲む最小の多角形が存在する場合、それを見つけようとしています。したがって、下の画像では、すべての線分のリストから、赤い点が指定されているため、青い線分のみを取得したいと考えています。私は Python を使用していますが、おそらく他の言語のアルゴリズムを適応させることができます。この問題が何と呼ばれているのかわかりません。
4 に答える
最初に、少なくとも 1 つの自由端点を持ち、他のセグメントと一致しないすべての線分を削除します。そのようなセグメントがなくなるまで繰り返します。
これで、平面が多角形領域にうまく分割されました。
ポイントに最も近いセグメントを見つけます。最も近いエンドポイントではなく、最も近いセグメントです。念のため。セグメントに沿って必要な方向を見つけます (ポイントは有向セグメントの右側にある必要があります)。終点に行き、右に曲がります (つまり、元のセグメントの隣のセグメントを反時計回りに数えます)。次のエンドポイントに進み、最も近いセグメントに再び到達するまで右に曲がります。
次に、ポリゴンが指定された点を囲んでいるかどうかを確認します。そうでない場合は、「島」を見つけたことになります。そのポリゴンとそれが属する接続されたコンポーネント全体を削除し、最も近いセグメントをもう一度選択してやり直します。接続されたコンポーネントは、単純な DFS で見つけることができます。
これにより、時計回りの多角形が得られます。多くの場合、ソフトウェアと文献の両方でデフォルトの「正の」方向である反時計回りが必要な場合は、左側のポイントから始めて、各交差点で左に曲がります。
特定のエンドポイントに関連するすべてのセグメントをすばやく見つけることができれば、確実に役立ちます。
これは実際には @nm の回答の単なる実装です。これは、賞金の期限が切れる前に私が得た距離です。それは完全にテストされていません。
def smallestPolygon(point,segments):
"""
:param point: the point (x,y) to surrond
:param segments: the line segments ( ( (a,b),(c,d) ) , . . . )
that will make the polygon
(assume no duplicates and no intersections)
:returns: the segments forming the smallest polygon containing the point
"""
connected = list(segments)
def endPointMatches(segment1,segment2):
"""
Which endpoints of segment1 are in segment2 (with (F,F) if they're equal)
"""
if ( segment1 == segment2 or segment1 == segment2[::-1] ):
return ( False, False )
return ( segment1[0] in segment2 , segment1[1] in segment2 )
keepPruning = True
while ( keepPruning ):
keepPruning = False
for segment in connected:
from functors import partial
endPointMatcher = partial(endPointMatches,segment1=segment)
endPointMatchings = map(endPointMatcher,connected)
if ( not and(*map(any,zip(*endPointMatchings))) ):
connected.remove(segment)
keepPruning = True
def xOfIntersection(seg,y):
"""
:param seg: a line segment ( (x0,y0), (x1,y1) )
:param y: a y-coordinate
:returns: the x coordinate so that (x,y) is on the line through the segment
"""
return seg[0][0]+(y-seg[0][1])*(seg[1][0]-seg[0][0])/(seg[1][1]-seg[0][1])
def aboveAndBelow(segment):
return ( segment[0][1] <= point[1] ) != ( segment[1][1] <= point[1] )
# look for first segment to the right
closest = None
smallestDist = float("inf")
for segment in filter(aboveAndBelow,connected):
dist = xOfIntersection(segment,point[1])-point[0]
if ( dist >= 0 and dist < smallestDist ):
smallestDist = dist
closest = segment
# From the bottom of closest:
# Go to the other end, look at the starting point, turn right until
# we hit the next segment. Take that, and repeat until we're back at closest.
# If there are an even number of segments directly to the right of point[0],
# then point is not in the polygon we just found, and we need to delete that
# connected component and start over
# If there are an odd number, then point is in the polygon we found, and we
# return the polygon
同じ線と異なる点でこれを何度も行う場合は、すべてのポリゴンを把握するために前処理を行う価値があります。次に、それは簡単です: 点から無限に線を引きます (概念的に言えば)。ラインを横切るたびに、ラインが含まれる各ポリゴンの交差数を増やします。最後に、交差数が奇数の最初のポリゴンが最小の囲みポリゴンになります。任意の線は他の線と同じように機能するため (直線である必要さえありません)、垂直線または水平線を引いて計算を単純化しますが、実際の端点を横切ることに注意してください。
各ラインを横切るときにポリゴンを作成することで、前処理なしでこれを行うことができます。これは基本的に nm のアルゴリズムに縮小されますが、特別なケースのチェックはすべて行われません。
ラインは 2 つのポリゴンに属することができることに注意してください。確かに、それはもっと多くのものに属している可能性がありますが、あなたがどのように言うかは私には明らかではありません: 以下を考えてみてください:
+---------------------------+
| |
| +-------------------+ |
| | | |
| | +-----------+ | |
| | | | | |
| | | | | |
+---+---+-----------+---+---+