我正在處理IfcFace。我給了一個帶孔的簡單多邊形，並且我需要將它轉換爲多個簡單的多邊形，以便我的CAD進一步處理它。小演示ilustration：將具有孔的多邊形轉換爲無孔的多個簡單多邊形
我的最好的辦法是做一個約束Delaunay三角測量和重返三角形成更大的多邊形。像這樣： 
但是，由於浮點精度和算法不穩定性，delaunay三角剖分甚至更多的約束部分往往因難以輸入而失敗。我的輸入有時會生成高度爲1e-8和基線長度爲1的三角形。
是否有更好的更穩健的算法來實現此轉換？
我認爲形狀的完整三角測量是一個很大的計算，你需要什麼。而三角剖分也使得三角形位於圖形外部，甚至部分位於內部和部分位於外部，所以正確重組它們也是複雜的。
提案1
我考慮完全不同的方法。
真的需要將數字分成兩個數字才能在CAD程序中使用它？如果你可以把它描述成一個循環中的一個數字（形成一個多邊形的一個點列表），我相信也是可以的。
您需要的是找到連接圖形的不同環路和完全位於圖形內部的線條，以便您可以使用它們組合環路。
我會先比較不同循環的片段對，然後搜索彼此最接近的片段。 開始將外部循環的所有段與所有內部循環的所有段進行比較。
實際上，我會通過比較外部循環上的點與內部循環的分段和內部循環上的點與外部循環的分段來實現它。如果x或y距離大於已經找到的最小距離，我將通過跳過計算來進行優化。
2個線段或彼此最接近的點和線段將爲您提供一條線，可用於合併線圈（或分割圖形）：從其中一個線的角（或點）垂直線在另一部分。缺點是您要添加新節點，但效率高且始終正確。
一旦找到這樣的行，連接的內部循環和新的行/段可以組合在一個修改的外部循環中，其中包括新的段兩次以關閉新的循環。您可以通過將修改後的外部循環的段與其餘的其他內部循環進行比較來重複該過程。
當使用所有內部循環時，您有一個循環描述整個圖形。
要將這個數字完全分成2個數字，您需要多一個額外的分段。
但我認爲我們現在所用的循環可以用於大多數CAD軟件來表示您的圖形。這不是一個標準化的數字，因爲它觸及到自身，但CAD程序通常不關心這一點。 CAD程序完全可以用來表示圖形的表面。
如果您確實想將其完全拆分爲2個數字，則可以通過搜索2個部分或更好的方式找到需要的額外線條，或者如果將比較限制爲線段對和點之間的距離最好它們在循環中由循環的兩個方向上的所有已經添加的分段分隔開。所有添加的段在循環中都是兩次，因此總是會有新循環的兩部分被所有這些循環分開。在你的答案
評論提案1
我沒有權尚未就此發表評論你的答案，因爲我沒有足夠的學分，所以我將評論添加到我自己的答案。
我在看你的例子，我首先誤解了，所以我改編了這個評論。
您有3個洞，所以算法的第一部分將添加您顯示的3段。
而且，是的，您顯然對算法的第二部分有問題。你需要第四行，但在這種情況下，沒有2個部分，它們在兩個方向上都被3個添加的段分開，或者我不會立即看到它們。
我認爲總會有2個部分的新環路將被所有的新環節分開。當有3個或更多孔時，這個假設是錯誤的。
但我會進一步思考。
提案2
我現在想另一種可能的算法。
計算圖中每個孔的表面。選擇每個孔的一個角落。
通過最小的2個孔的選定角繪製一條線。
它可以是任何2個孔，但是取最小的那個孔會增加以較少線條切割更多孔的機會。
如果只剩下一個洞，只需在你得到的一點上劃一條線即可。方向並不重要。我會選擇通過選定的點和最接近的其他點來定義該孔。
檢測畫出的線與圖形的各個部分的所有交點，以將線縮減爲完全位於圖形內部的一組線段並連接圖形的不同環。在同一個循環中省略開始結束的任何段。
如果僅在一個點中找到的段碰到一個孔。將一個片段移動到最接近該點的同一個孔的位置，以避免結束與具有與外部接觸的孔的圖形。 檢查修改後的段的新交叉點，如果發現任何問題，請再次拆分。
找到所有相交點需要將找到的線與圖中的所有線段進行比較，這也是很多計算的內容，但您可以通過在計算交點之前檢查該線穿過線段的邊界框來跳過計算。我將首先計算與外部循環的交點，以儘可能快地爲線的其餘部分設定邊界框，因爲這也可以幫助檢查不需要比較交點的部分。
您還可以通過將連接段的最近端點（如果尚未位於2段連接點中）連接的段替換每個找到的段進行優化。這樣做可以避免爲新數字創建附加點，並增加一步完成更多空洞的機會。但是，您需要再次檢查新的交叉點並重復此優化，直到找到不再有交點。
還有一種可能的優化方法：檢查尚未切割的靠近找到的切割點的切割點，並將找到的切割線分成兩段，以在同一步驟中捕捉該切割線。就像之前的優化一樣，這也需要再次檢查新的交點。
使用段將圖分成2個數字，然後從步驟2開始重複每個仍然有孔的新圖。
的缺點是，你可能最終超過2個位數（MAX（n，其中n爲孔數+1）/ 2的數字），但如果你有導致許多人物有許多小孔它可能有可能重組其中一些。
我用這個答案形象化我到@Stefan Mondelaers評論：
這就是爲什麼我使用約束 Delaunay三角。但你是對的，我也認爲這是太多的工作。
不幸的是，CAD確實需要多個循環，因爲循環中的所有點必須是唯一的。
我認爲你的算法的第二部分不起作用。
如果您確實想將其完全拆分爲2個數字，則可以通過搜索2個部分或更好地選擇最接近彼此的部分來找到所需的額外行，如果將比較限制爲段對以及在循環的兩個方向上由所有已經添加的分段在循環中分開的點。所有添加的段在循環中都是兩次，因此總是會有新循環的兩部分被所有這些循環分開。
看一下這個例子，其中橙色是外部多邊形，藍色是它的孔。算法的第一部分將執行此操作： 
但是現在第二部分將只添加藍色多邊形之間的連接，因爲它們最接近。但是這不會解決持有橙色多邊形的循環問題，因爲新引入的點將在那裏兩次。
這個問題會受益於截圖或某種插圖。 – Wossname
編輯：根據要求一些例證。 – PanicSheep
儘管它是CAD，但您可能在https://gis.stackexchange.com/上發佈了更多的好消息 –