多邊形自交的處理？

第一次發帖有些地方可能處理得不好，請見諒。

最近在處理一些多邊形的計算（多個多邊形的合併，兩個多邊形的距離，簡化多邊形的線段生成SVG）。其中有一個問題難了好久，就是對自交多邊形的處理。

首先，這個多邊形是用0校驗檢測內外的。那麼最簡單的五角星要怎麼簡化。

1. 如果用找凸包的方式會弄出個五邊形來。

2. 我自己想到了一個辦法，就是看所有交點對應的線，有沒有重複，如果有則去掉重複的線。這樣就解決了五角星的問題。

但是以上的演算法不能解決如下圖形，會誤刪需要的線。

這個問題卡了好久，我想諮詢下是否已有相關的研究提到了解決這個問題的演算法？

謝謝。

---

那個五角星的立體裡面，根據你要不要保留中間五邊形的部分，有兩種不同的現成的演算法。題主自己找找就有了。

---

找到所有的交點。然後把線打斷。形成一個圖。

很顯然這是一個平面圖，尋找這個平面圖的外邊界即可。

---

你沒有定義你最後想要的是什麼啊.

你想要的應該是minimal simply connected set that contains這個多邊形. (這樣的多邊形不會中間有個洞).

可以通過這個多邊形和自己的交點弄出一個對應的平面圖來, 然後trace一下outer face就好.

---

clipper：an open source freeware polygon clipping library

boost geometry：Chapter 1. Geometry

演算法很多，clipper用的是這個：Vatti clipping algorithm

---

用 Non-zero 的方法掃描整個圖形的填充，把被填充的像素點去掉。

填充的時候只包括圖形裡面的點，而不包括圖形輪廓上的點。這樣輪廓和填充的交集就是要去掉的點。

---

以某個點為頂點，向周圍去尋找另外相連的兩個點構成一個[最大的三角形](也就是與能構成三角形的最遠的兩個點所構成的三角形)，然後在這個三角形的兩條側邊上搜索屬於同一條線上的點，以這兩個點為端點的線段就是要刪除的線，但是並不是馬上刪除它，而是記錄下來等全部點遍歷結束再刪除。

這樣？不知道這個思路正不正確。

---

瞎想的一個，沒試過

1. 取最左的點中最下的點 記為(其他亦可)

2. 找出與其相鄰的點

3. 求出 中與x軸夾角最大的(最小亦可),記為

—— 循環 ——

4. 對於任意點,找出與其相鄰的以外的所有點

5. 找出向量與中夾角最大的，且叉乘為負(如果3取最小角) 或正(如果3取最大角)

—— 循環直至形成閉合迴路 ——

---

取所有小碎塊,去重,合在一起?

或者先找到一定包含整張圖的大塊,然後去掉邊角?

//題主你到底知道什麼,並且想要求什麼啊?

//是知道上圖五角星的線,想要求輪廓嗎?

那先給外面染色就好了啊//嫌複雜度太高嗎?

---

推薦閱讀：