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

Question

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

加上关于多边形的描述。二维、静态、复杂的多边形(也有孔)。

任何建议将不胜感激。

Answer 1

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

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

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