大量積分的點多邊形

Question

我想知道什麼可能是確定大量積分（O（100萬）是集合內部還是外部（O（10））的最有效方式？ ）的多邊形？後者不一定是凸的，但它們沒有孔，此時我通過比較它們的位置與邊界框來修剪點的數量，然後在其餘點上使用this穿越數方法。有沒有更快的方法？

Answer 1

假設你有軸對齊的邊界框，你可以通過它們的x座標對點列表進行排序，通過二分搜索找到列表點上的位置或邊界框外的位置，可能一次丟棄大量的點，重複y座標像以前一樣用剩下的點。您可以執行多邊形三角測量以加快邊界框內的測試。

當平面的面積遠大於多邊形的面積並且多邊形相當緊湊時（即不會很長且很薄，這可能會導致很多誤報），性能會更好。

Answer 2

我可能會使用Quadtree來快速粗略測試「我在多邊形內部還是外部」，以達到您在生成四叉樹時確定的某個精度級別。

每次查找都是O（log n），這將會盡可能快地得到。對於標記爲「包含邊緣」的四叉樹單元格內的點，則必須執行傳統的點中多邊形測試。

Answer 3

這裏有一個高效的matplotlib函數：matplotlib.nxutils.points_inside_poly()。算法記錄在this page上。