我有一組不相交的線,其中一些連接在頂點。我試圖找到包含給定點的最小多邊形(如果存在的話)。所以,在下面的圖片中,在所有線段的列表中,給出紅色的點,我只想得到藍色的點。我正在使用Python,但可能會適應其他語言的算法;我不知道這個問題叫什麼。如何從一組線中找到包圍點的多邊形?
回答
首先,移除具有至少一個自由端點,與任何其他段不重合的所有線段。重複這樣做直到沒有這樣的細分市場。
現在你有一個很好的細分成多邊形區域的平面。
查找離您最近的點。不是最接近的端點,而是最接近的部分,請介意。找出沿着你需要的段的哪個方向(你的點應該在有向段的右側)。轉到端點,向右轉(即,從您來自的端點旁邊的部分,逆時針計數)。繼續進入下一個終點並向右轉,直到再次點擊最接近的段。
然後,檢查多邊形是否包圍給定的點。如果不是,那麼你找到了一個「島」;刪除該多邊形及其所屬的整個連接組件,然後再次選擇最近的片段重新開始。連接的組件可以通過簡單的DFS找到。
這給你一個順時針方向的多邊形。如果你想逆時針旋轉,這通常是軟件和文獻中默認的「正向」方向,從左邊開始,然後在每個十字路口左轉。
如果給定一個端點,您可以快速找到與之相關的所有細分,它肯定會有所幫助。
如果您使用相同的線條和不同的點數進行了多次處理,則需要進行預處理以計算出所有多邊形。然後很簡單:從點到無窮(從概念上講)畫一條線。每當你穿過一條線時,增加該線所屬的每個多邊形的交叉點數。最後,具有奇數交叉數的第一個多邊形是最小的包圍多邊形。由於任意一行可以和其他任何行一樣(甚至不需要是直的),所以通過繪製垂直或水平線來簡化算術,但要注意穿越實際的端點。
您可以在不經過預處理的情況下通過在每條線上交叉時創建多邊形來執行此操作。這基本上減少到n.m.的算法,但沒有所有的特殊情況檢查。
請注意,一條線可以屬於兩個多邊形。事實上,它可能屬於比較,但它不是我清楚你會怎麼說:考慮以下幾點:
+---------------------------+
| |
| +-------------------+ |
| | | |
| | +-----------+ | |
| | | | | |
| | | | | |
+---+---+-----------+---+---+
這真的只是@ N.M.的答案的實現。 這是我在賞金到期前得到了多少;它完全沒有經過測試。
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
方法。 我建議將輸入解釋爲PSLG,G,它由頂點和邊組成。然後你的問題簡化爲尋找被點p命中的G的面部。這是通過拍攝從某個方向的一條光線來完成的,從而找到臉部邊界的邊緣並沿某個方向穿過臉部的邊界。但是,第一次擊中的邊緣可能是一個不被p命中的面部,但它本身被p命中的面部所包圍。因此,我們可能需要沿着由p發出的光線進行搜索。
實施細節。 在下面的代碼中,我向東方向拍攝光線,並以順時針方向圍繞臉部運動,即在每個頂點處取下一個逆時針邊緣,直到我再次結束第一個頂點。生成的面將作爲G的頂點序列返回。
如果要返回simple polygon,則必須通過修剪G中的樹來清理輸入圖G,以便只保留簡單的面。
def find_smallest_enclosing_polygon(G, p, simple=False):
"""Find face of PSLG G hit by point p. If simple is True
then the face forms a simple polygon, i.e., "trees"
attached to vertices are pruned."""
if simple:
# Make G comprise simple faces only, i.e., all vertices
# have degree >= 2.
done = False
while not done:
done = True
for v in [v in vertices if degree(v) <= 1]:
# Remove vertex v and all incident edges
G.remove(v)
done = False
# Shoot a ray from p to the east direction and get all edges.
ray = Ray(p, Vector(1, 0))
for e in G.iter_edges_hit(ray):
# There is no enclosing face; p is in the outer face of G
if e is None:
return None
# Let oriented edge (u, v) point clockwise around the face enclosing p
u, v = G.get_vertices(e)
if u.y < v.y
u, v = v, u
# Construct the enclosing face in clockwise direction
face = [u, v]
# While not closed
while face[-1] != face[0]:
# Get next counter-clockwise edge at last vertex at last edge.
# If face[-1] is of degree 1 then I assume to get e again.
e = G.get_next_ccw_edge(face[-2], face[-1])
face.append(G.get_opposite_vertex(e, face[-1]))
# Check whether face encloses p.
if contains(face, p):
return face
return None
複雜性。 設n表示頂點的數量。請注意,在PSLG中,邊的數量在O(n)中。修剪部分可能需要O(n^2)時間的方式在上面實現。但是,它可能是O(n)時間中的一個,它通過識別1次頂點並繼續遍歷這些頂點。
射線交點例程可以在O(n)時間內平均實現。構造人臉需要O(m)個時間,其中m是構造的多邊形的大小。我們可能需要測試多個多邊形,但所有多邊形的大小總和仍然在O(n)中。包含(face,p)的測試可以通過檢查臉是否包含由G.iter_edges_hit(ray)返回的奇數個邊,即在O(m)時間來完成。
通過一些預處理,您可以建立一個數據結構,在O(log n)時間內通過經典的point location算法找到p命中的面,並且可以將結果多邊形預先存儲,以便簡單和/或非簡單的情況。
- 1. 查找包圍一組點的邊界多邊形的區域
- 2. 包含一組點的多邊形
- 3. 給定非凸多邊形中的一大組頂點,我如何找到邊?
- 4. 多邊形頂點從一組點
- 5. 我如何找到從一個點到該多邊形的多邊形上的最短點(不是距離)
- 6. 如何在多邊形內找到點?
- 7. 如何從一組點中繪製最大的多邊形
- 8. 在每個多邊形中查找一組多邊形的最大點R
- 9. 如何在Java中圍繞一個點旋轉多邊形/點
- 10. 如何找到一組線的最小邊界矩形?
- 11. 找到所有由線交點形成的多邊形
- 12. 如何從一組無序點中繪製多邊形
- 13. 如何找到多邊形的中心?
- 14. 如何找到一個點位於一條線或多邊形內
- 15. 從多邊形網格中找到唯一邊的算法
- 16. 如何在一組簡單多邊形中分割多邊形
- 17. 從具有共線邊的多邊形中提取多邊形
- 18. 如何在不規則多邊形內找到一個點
- 19. MongoDB如何查找哪個多邊形包含指定的點?
- 20. 如何從一組邊緣起點和終點構造多邊形?
- 21. 如何將一組二維點(多點)轉換爲多邊形?
- 22. 一組線條的多邊形檢測?
- 23. 如何在JavaScript中圍繞多段線繪製多邊形?
- 24. Boost.Geometry沒有找到多邊形線intersecion
- 25. 如何找出多邊形中邊,面,頂點的數量
- 26. 確定哪些多邊形的點是從一個大組多邊形
- 27. 找到一組多邊形的邊,沒有重複
- 28. 找到點與多邊形之間最長的「直線」路徑
- 29. 如何獲得點周圍的邊界多邊形?
- 30. 多邊形圍繞中心點繪製
我不認爲問題陳述是正確的(毫不含糊)。紅點周圍最小的多邊形可以由該點的西南頂點和該點以東的黑線段形成。 – 2013-04-22 07:36:37
我的意思是,最小的多邊形只由已經存在的線條構成。 – Skyler 2013-04-22 16:18:30
定義「最小」 – Cam 2013-05-01 06:08:27