2

我有一个很大的多边形列表（比如说大小 250,000）和一个很大的点列表（比如说大小 100,000）。我需要做的是找出每个点属于哪个多边形。

多边形始终是具有 5 个点的矩形/菱形，其中第一个点和最后一个点相同。它们还具有与多边形相关的近似中心点。示例多边形如下： Polygon(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)

这是一个简化的例子。这些点中的大多数都是经纬度/GIS 坐标。

输入的点列表可能与任何多边形都不匹配，或者可能与多边形列表中的一个或多个多边形匹配。

目前我有一个函数，它需要一个点和一个多边形来查看该点是否在多边形内。每当我想看到一个点在多边形中时，我必须遍历完整的多边形列表以查看它是否匹配。此外，由于一个点可能位于多个多边形中，因此我每次都必须遍历完整列表。这是非常低效的。

我正在寻找的是将这些多边形排序为 HashMap 或其他东西，以便我可以快速获取一些需要检查每个点的多边形，而不是完整的多边形列表。由于这些点同时具有 x 和 y 参数，因此我无法找到对多边形进行排序的好方法。另请注意，每个多边形都有一个中心点。那么有没有办法根据这些中心点作为关键点对多边形进行排序，以便我们轻松查找？

对此有任何想法/想法吗？谢谢！

4

2 回答 2

2

使用 kd 树，这是一种有效的空间分区

http://en.wikipedia.org/wiki/K-d_tree

于 2013-02-19T17:02:25.403 回答
0

将您的 2D 空间拆分为方形单元，每个单元存储与单元相交的多边形列表。当需要检查点时，首先找到该单元点所属的单元格点，然后遍历与该单元格相交的所有多边形并进行测试。选择像元大小，以便每个像元有合理数量的多边形。

如果您的多边形分布不均匀，您可能需要使用四叉树而不是方形单元格。

于 2013-02-19T16:20:26.343 回答