通過座標搜索笛卡爾平面上的幾何形狀

Question

我在笛卡爾平面上有算法問題..我需要高效地搜索與給定點相交的幾何形狀。有幾種形狀（矩形，圓形，三角形和多邊形），但這些並不重要，因爲確定實際點包含在這裏不是問題，我將自己實現這些。問題在於確定哪些形狀需要驗證包含在給定的點。在平面上迭代我的所有形狀並在它們中的每一個上運行點包含方法都是低效的，因爲形狀的實例數量會非常大。我的第一個想法是爲平面劃分平面（平面是有限的，但對於任何類型的3D陣列都太大），並且在向數據庫添加形狀時，我將確定它將與哪些分段相交併將它們保存在對象中形狀。然後，當給出包含驗證的點時，我只需要確定點所在的段，然後只驗證包含與該段相交的對象的包含。

這就是要走的路嗎？我不知道我描述的方法是最優的還是我沒有錯過什麼。任何幫助將提前感激..

感謝

P.S：我會在C寫這篇++。這並不真正相關，因爲它更像是一個算法問題，但我想把它說出來，如果有人很好奇......

Answer 1

網格化方法可以在這裏使用。

將平面看作光柵圖像，使用掃描轉換算法繪製所有形狀，確保所有像素部分覆蓋。對於每個圖像像素，保留一個填充它的形狀列表。

查詢是直截了當然後：找到該查詢點落在時間O(1)像素和檢查每個形狀在列表中，在時間O(K)，其中K是列表的長度，約等於交叉形狀的數量。

如果圖像是由N²像素，你必須有一個平均面積A像素M對象，您將需要存儲N²+M.A列表元素（形狀識別+到下一個鏈接）。您將選擇像素大小以實現準確性和存儲成本之間的良好折中。無論如何，您必須將自己限制爲N²<Q.M，其中Q是查詢的總數，否則僅初始化映像的成本可能會超過總查詢時間。

如果場景非常稀疏（空洞多於形狀），則可以使用壓縮的圖像表示，使用quadtree。