如何重繪完全自相交的多邊形？

Question

問題是重繪自相交2D多邊形，它的邊界是總是其內部和其外部之間的分隔線並完全橫穿本身在某些點（即，在這些點，多邊形內部開關的側邊界，從左到右，反之亦然）。

什麼是可以做的，最簡單的算法？

初始多邊形（左）和重繪一個（右）：

。

我又添加了一個更復雜的初始多邊形示例，它仍然非常簡單（它只有一個自交頂點）in this third picture其中多邊形內部填充（點A，B，C，D， E在繪製多邊形邊框時最初以字母順序出現）。

Answer 1

你問的不是那麼簡單。

您可以使用掃描程序。一般原則如下。

當您在多邊形畫出水平線，它滿足偶數邊緣。將交叉點從左向右排列，並將它們成對鏈接，即可獲得內部細分。

如果你這樣做了橫向的所有位置，你就會分解在一些單調鏈的多邊形，即折線一直走下去。

當多簡單，鏈在頂點是成對出現的，在另一對消失，住自己的靜物。但是當多邊形交叉時，鏈可以相互交叉。這可以通過以下事實來檢測：從水平的一個位置到下一個位置，交叉點的順序改變。

現在你已經通過「uncrossing」的枷鎖，這是由在交叉點分割邊做修復。

我不能開發出更多的這裏，試圖查找「掃掠跡線算法」。