通過填充矩形檢查許多（小）多邊形與一個（大）多邊形的交集？

Question

我有一個2D計算幾何/ GIS問題，我認爲應該是常見的，我希望找到一些現有的代碼/庫來使用。

的問題是，以檢查其中大集的一個子集小多邊形（千）有一個大的多邊形相交。 （通過「小」和「大」我指的是多邊形覆蓋的空間量，而不是定義它們的點的數量，儘管通常假設定義多邊形的點的數量大致與其幾何尺寸成比例。爲了給人一種比例感，把「大」看作美國州的多邊形，將「小」看作小鎮的多邊形）。

假設使用標準CheckIfPolygonsIntersect（ P，p）函數，對於每個小多邊形p對一個大的多邊形P要求，太慢了。似乎有辦法預先處理大的多邊形，以使交叉點檢查大多數小多邊形不重要。特別是，您似乎可以創建一小部分矩形，部分/幾乎填滿大多邊形。類似地，您可以創建一小部分矩形，部分/幾乎填充實際上不在大多邊形內的大多邊形的邊界框的區域。那麼絕大多數小多邊形都可以被包含或排除在外：如果它們完全位於大多邊形的邊界矩之外，則將它們排除在外。如果它們完全位於內邊界矩形邊界之內但是外部多邊形矩形的邊界內，則它們被排除。如果他們的任何觀點都在任何內部觀點之內，那麼它們都包含在內。只有以上都不適用，你必須調用CheckIfPolygonsIntersect（P，p）函數。

那是一個衆所周知的算法？你知道現有的代碼來計算任意（凸或凹）多邊形的一組合理的內/外矩形嗎？在所有情況下，矩形不一定是完美的;他們只需要填充大部分多邊形，以及大部分內部邊界但是外部多邊形區域。

下面是我怎麼可能會計算這些矩形一個簡單的計劃：

• 採取大多邊形的邊框和構建點的，比如，10×10格在它
• 每個點，確定如果是內部還是多邊形
• 在四個方向的反覆擴張，直到矩形邊緣之一穿過的多邊形邊一個「成長」的每個點成長方形，在這種情況下，你已經走得太遠了外（這實際上是在「二分搜索」類型的迭代中完成的，因此只需幾次迭代就可以找到正確的數額在每個方向擴大;當然還有一些問題是否要一次最大化一個邊或者一個邊是否一致）
• 任何尚未擴展的網格點被另一個點的擴展覆蓋消失
• 當所有點已經擴大（或已經消失），你有你的一套內部和外部矩形

當然，大的多邊形某些瘋狂的凹形可能會導致一些窮/小的矩形。但假設多邊形大部分是合理的（比如說，它們是美國各州的形狀），看起來你會得到一組好的矩形，並且可以大大地優化你隨後做的數千次相交檢查。

是否有該算法的名稱（和代碼）？

編輯：我已經在使用四叉樹來確定可能與大多邊形的邊界矩相交的小多邊形。所以問題是檢查多邊形實際上是否與大多邊形相交的那些。

感謝您的任何幫助。

Answer 1

在你的計劃中，你描述了一些非常類似於簽名的距離圖方法。詳細信息請參閱Google的「距離圖算法」。我希望這將是你要找的。