java - 在数百万个多边形中找到数千个点的快速算法？

Question

我试图通过网络服务找出百万多边形中的数千个点。起初我在java中实现了算法（多边形中的点），但需要很长时间。然后我在mysql中拆分表并尝试使用多个线程来解决它，但仍然效率低下。有没有更快的算法或实现来解决这个问题？

加上关于多边形的描述。2D，静态，复杂多边形（也有孔）。

任何建议将不胜感激。

Answer 1

无论您的点在多边形函数中的效率如何，针对一百万个多边形测试一个点都将花费大量时间。

您需要缩小搜索列表的范围。首先为每个多边形制作一个边界框，并且仅当点在边界框内时才选择多边形。

如果多边形不变，您可以将每个多边形转换为一组三角形。测试一个点是否在三角形中应该比测试它是否在任意多边形中要快得多。尽管三角形的数量会比多边形的数量大得多，但总体上可能会更快。

Answer 2

如果多边形的集合是静态的，那么首先将它们注册到空间数据结构中可能会有所帮助 - R-tree可能是一个不错的选择，假设多边形不会相互重叠太多。

要针对多边形集合测试一个点，首先会找到树中的封闭叶子（O(log(n))样式操作），然后只需对与封闭叶子相关联的多边形执行完整的多边形点测试.

这种方法应该大大加快每个点测试，但需要一个额外的设置阶段来构建 R-tree。

希望这可以帮助。

Answer 3

如果您处理数百万个多边形，则需要某种空间分区，否则会很慢，无论您​​的命中测试功能如何优化或有多少线程在解决您的查询。

什么样的空间分区？这取决于：

• 二维？3D？
• 你的多边形设置是静态的吗？如果不是，是否经常更换？
• 你对这个系列有什么要求？
• 它是什么样的多边形？三角形？凸？凹？复杂的？有孔吗？

我们需要更多信息来帮助您。

编辑

这是一个简单的空间分区方案。

假设您的 2D 空间上有一个笛卡尔网格，并且具有给定的步长。

添加多边形时：

• 计算它的边界框
• 查找与边界框相交的所有网格单元
• 对于每个单元格，在特殊表格中添加一行。

该表如下所示：cell_x, cell_y, polygon_id. 添加正确的索引（至少cell_x和cell_y）

当然，您要选择网格步长，使大多数多边形位于少于 10 个单元格中，否则您的单元格表将很快变得巨大。

现在很容易找到给定点的多边形：

• 计算您的点属于哪个单元格
• 获取与此单元格关联的所有多边形
• 对于每个多边形，使用你的命中测试函数

该解决方案远非最佳，但易于实施。

Answer 4

我认为这是分而治之的情况，您可以尝试制作子多边形或简化一些 poonts，也许尝试一种启发式方法，这是我的 5 美分。