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两个参数，因此我无法找到订购多边形的好方法。 另请注意，每个多边形都有一个中心点。那么有没有办法将基于这些中心点的多边形排序为关键点，以便我们可以轻松查找？
对此有何想法/想法？谢谢！