2
我有一個多邊形的大列表（比如說大小爲250,000）和一個大的列表（比如100,000）。我需要做的是找出每個這些點屬於哪個多邊形。匹配點在多邊形列表中的多邊形
多邊形總是矩形/菱形，其中第一個點和最後一個點是相同的5個點。它們也有與多邊形相關的近似中心點。多邊形（a; b; c; d; a）=（3,1; 5,3; 3,5; 1,3; 3,1）和中心點（x）=（ 3，3）。請參閱下面的示例圖：
c (3,5)
/\
/\
(1,3) d/ \b (5,3)
\ x/
\/
\/
a (3,1)
這是一個簡化示例。這些點中的大部分都是lat-lon/GIS座標。
點的輸入列表可能不匹配任何多邊形，也可能與多邊形列表中的一個或多個多邊形相匹配。
目前我有一個函數，它需要一個點和一個多邊形來查看點是否在多邊形內。任何時候我想看到一個點在多邊形中，我必須遍歷多邊形的完整列表來查看它是否匹配。另外，由於一個點可能在多個多邊形中，因此每次都必須遍歷完整列表。這是非常低效的。
我在找的是將這些多邊形排序成一個HashMap或其他東西，這樣我就可以快速獲取需要爲每個點檢查的幾個多邊形，而不是完整的多邊形列表。由於點有x和y兩個參數，因此我無法找到訂購多邊形的好方法。 另請注意，每個多邊形都有一箇中心點。那麼有沒有辦法將基於這些中心點的多邊形排序爲關鍵點，以便我們可以輕鬆查找？
對此有何想法/想法？謝謝！