2013-04-22 135 views
3

我有一組不相交的線,其中一些連接在頂點。我試圖找到包含給定點的最小多邊形(如果存在的話)。所以,在下面的圖片中,在所有線段的列表中,給出紅色的點,我只想得到藍色的點。我正在使用Python,但可能會適應其他語言的算法;我不知道這個問題叫什麼。如何從一組線中找到包圍點的多邊形?

Example

+0

我不認爲問題陳述是正確的(毫不含糊)。紅點周圍最小的多邊形可以由該點的西南頂點和該點以東的黑線段形成。 – 2013-04-22 07:36:37

+0

我的意思是,最小的多邊形只由已經存在的線條構成。 – Skyler 2013-04-22 16:18:30

+0

定義「最小」 – Cam 2013-05-01 06:08:27

回答

5

首先,移除具有至少一個自由端點,與任何其他段不重合的所有線段。重複這樣做直到沒有這樣的細分市場。

現在你有一個很好的細分成多邊形區域的平面。

查找離您最近的點。不是最接近的端點,而是最接近的部分,請介意。找出沿着你需要的段的哪個方向(你的點應該在有向段的右側)。轉到端點,向右轉(即,從您來自的端點旁邊的部分,逆時針計數)。繼續進入下一個終點並向右轉,直到再次點擊最接近的段。

然後,檢查多邊形是否包圍給定的點。如果不是,那麼你找到了一個「島」;刪除該多邊形及其所屬的整個連接組件,然後再次選擇最近的片段重新開始。連接的組件可以通過簡單的DFS找到。

這給你一個順時針方向的多邊形。如果你想逆時針旋轉,這通常是軟件和文獻中默認的「正向」方向,從左邊開始,然後在每個十字路口左轉。

如果給定一個端點,您可以快速找到與之相關的所有細分,它肯定會有所幫助。

+1

然後,檢查多邊形是否包圍給定的點。 – WolframH 2013-04-22 12:23:07

+1

@WolframH:是的,當然忘了補充一點。一個點可能在任何封閉多邊形之外。 – 2013-04-22 12:33:12

+0

如果最近的線段位於不包含該點的不同多邊形中,該怎麼辦? – Skyler 2013-04-22 17:01:36

0

如果您使用相同的線條和不同的點數進行了多次處理,則需要進行預處理以計算出所有多邊形。然後很簡單:從點到無窮(從概念上講)畫一條線。每當你穿過一條線時,增加該線所屬的每個多邊形的交叉點數。最後,具有奇數交叉數的第一個多邊形是最小的包圍多邊形。由於任意一行可以和其他任何行一樣(甚至不需要是直的),所以通過繪製垂直或水平線來簡化算術,但要注意穿越實際的端點。

您可以在不經過預處理的情況下通過在每條線上交叉時創建多邊形來執行此操作。這基本上減少到n.m.的算法,但沒有所有的特殊情況檢查。

請注意,一條線可以屬於兩個多邊形。事實上,它可能屬於比較,但它不是我清楚你會怎麼說:考慮以下幾點:

+---------------------------+ 
|       | 
| +-------------------+ | 
| |     | | 
| | +-----------+ | | 
| | |   | | | 
| | |   | | | 
+---+---+-----------+---+---+ 
+0

在你的例子中你會考慮多少個多邊形 - 3或6?你是怎麼找到他們的? – WolframH 2013-04-23 11:05:57

+0

有3 *最小*多邊形(不是其他多邊形的一部分)和恰好6段分別屬於兩個多邊形(兩個內部Π形折線)。 – 2013-04-23 12:56:32

+0

@WolframH:當然有三個多邊形。如果您不知道哪些是多邊形,那麼您必須假定沒有多邊形包含另一個多邊形。但是如果兩個外部多邊形下降了一個像素的一部分(最外面的一個像素爲兩個部分),那麼您將得到不同的讀數。 – rici 2013-04-23 13:34:13

1

這真的只是@ 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 
0

方法。 我建議將輸入解釋爲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命中的面,並且可以將結果多邊形預先存儲,以便簡單和/或非簡單的情況。

相關問題