一千萬個為什麽

搜索

如何組合復雜的多邊形?

給出兩個多邊形:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

如何計算並集(組合多邊形)?

enter image description here

Dave's example uses SQL server to produce the union, but I need to accomplish the same in code. I'm looking for a mathematical formula or code example in any language that exposes the actual math. I am attempting to produce maps that combine countries dynamically into regions. I asked a related question here: Grouping geographical shapes

最佳答案

這個問題問得好。我前段時間在c#上實現了相同的算法。算法構造兩個多邊形的公共輪廓(即構造一個沒有孔的聯合)。這裏是。


Goal

步驟1.創建描述多邊形的圖形。

輸入:第一個多邊形(n個點),第二個多邊形(m個點)。輸出:圖表。頂點 - 多邊形交點。

我們應該找到交叉點。遍歷兩個多邊形[O(n * m)]中的所有多邊形邊並找到任何交點。

  • 如果找不到交叉點,只需添加頂點並連接它們即可 到了邊緣。

  • 如果找到任何交叉點,請按長度對它們的起點進行排序,然後添加全部 頂點(開始,結束和交叉點)並連接它們(已經在 排序順序)到邊緣。

第2步。檢查構造的圖形

如果在構建圖形時我們沒有找到任何交叉點,則我們具有以下條件之一:

  1. Polygon1包含polygon2 - return polygon1
  2. Polygon2包含polygon1 - return polygon2
  3. Polygon1和polygon2不相交。返回polygon1和polygon2。

第3步。找到左下角的頂點。

找到最小x和y坐標(minx,miny)。然後找到(minx,miny)和多邊形點之間的最小距離。這一點將是左下角。

Left-bottom point

步驟4.構建共同的輪廓。

我們開始從左下角遍歷圖形並繼續直到我們回到它。在開始時,我們將所有邊標記為未訪問。在每次叠代時,您應該選擇下一個點並將其標記為已訪問。

要選擇下一個點,請選擇逆時針方向具有最大內角的邊。

我計算了兩個向量:當前邊緣的vector1和每個下一個未訪問邊緣的vector2(如圖所示)。

對於矢量我計算:

  1. 標量積(點積)。它返回與向量之間的角度相關的值。
  2. 矢量產品(交叉產品)。它返回一個新的向量。如果是z坐標 矢量是積極的,標量產品給我直角     逆時針方向。否則(z坐標為負),我     計算矢量之間的角度為360° - 角度的標量     產品

結果,我獲得了具有最大角度的邊緣(以及對應的下一個頂點)。

I add to result list each passed vertex. Result list is the union polygon. Vectors

備註

  1. 此算法允許我們合並多個多邊形 - 叠代地應用多邊形對。
  2. 如果您的路徑包含許多貝塞爾曲線和線條,則應首先展平此路徑。

轉載註明原文: 如何組合復雜的多邊形?