9計算交集矩陣兩個多邊形之間

Question

的問題

給定兩個無孔非凸多邊形，我想計算相應的9交集矩陣。

A 9交集矩陣的形式爲：

| I | B | E 
I | I ∩ I | I ∩ B | I ∩ E 
B | B ∩ I | B ∩ B | B ∩ E 
E | E ∩ I | E ∩ B | E ∩ E 

I - Interior 
B - Border 
E - Exterior 

在矩陣的每個細胞，我想知道的交集是否存在，如果它存在，我想知道它是否是點，線或多邊形。

值得注意的是，對於給定的單元格，多邊形之間的交集可能由一組幾何圖形組成。但是，如果這個集合是由一個點和一條線組成的，我只對知道這條線感興趣。在這個邏輯中，點的優先級最低，多邊形最高。因此，如果我們認爲一個點是0維，一維線和多邊形二維，我想知道交點的最高維。

我至今

好了，有算法，如華帝裁剪算法，該剪輯多邊形到另一個。這意味着這些算法提供了相交的幾何對象，可能是一組對象。得到這個結果後，我相信有可能推導出9-Intersection Matrix，即使我沒有真正想過它。

這種方法存在的問題之一是剪裁算法的二次複雜性，因爲該算法將被包含在GIS中用於有效的拓撲查詢回答。我確實認爲可以僅使用邊界之間的交點來填充矩陣，可以在O（Nlog（N）+ k）中計算，其中K是使用Balaban提出的算法的交點的數量，和簡單的點位置。

但是，我也相信這種方法會導致一組非常大的條件。到目前爲止，我已在以下條件：

• 外牆之間的交集總是2維
• 如果兩個多邊形的邊界在一個點上，是不是一個角相交，的交集內部是二維的
• 如果邊界不相交併且另一箇中包含至少一個多邊形點，則第一個包含在第二個中（並且可以填充大量矩陣單元）
• 如果邊界不相交併且多邊形的至少一個點位於另一個點的外部，則多邊形不相交（並且所有矩陣c ells可以填寫）

問題是，這套規則是遠遠不完整的。例如，對於邊界在至少一個多邊形的角點也相交的情況，我仍然沒有一個好的規則。

的實際問題

給定兩個非凸多邊形沒有孔也沒有自交差，什麼是計算的最有效的方式9的交集矩陣，其涉及兩個幾何對象？

Answer 1

構建多邊形線段（在輸出元素數目中爲linearithmic）的平面直線圖（PSLG），將多邊形轉換爲PSLG週期，確定由這些週期包圍的面（基本上是深度優先搜索） ，然後其餘的都是微不足道的。這裏最困難的部分是計算PSLG，但也有一些庫。