java快速算法在数百万个多边形中找到数千个点?
我试图通过网络服务找到成千上万的多边形点。起初,我用java实现了算法(多边形中的点),但这需要很长时间。然后我在mysql中拆分了表,并尝试使用多线程来解决它,但仍然效率低下。有没有更快的算法或实现来解决这个问题
加上多边形的描述。二维、静态、复杂多边形(也带有孔)
任何建议都将不胜感激
你可以在下面搜索框中键入要查询的问题!
我试图通过网络服务找到成千上万的多边形点。起初,我用java实现了算法(多边形中的点),但这需要很长时间。然后我在mysql中拆分了表,并尝试使用多线程来解决它,但仍然效率低下。有没有更快的算法或实现来解决这个问题
加上多边形的描述。二维、静态、复杂多边形(也带有孔)
任何建议都将不胜感激
# 1 楼答案
如果多边形的集合是静态的,那么首先将它们注册到空间数据结构中可能会有所帮助——假设多边形之间没有太多重叠,那么R-tree可能是一个不错的选择
要针对多边形集合测试点,首先会找到树中的封闭叶(一个
O(log(n))
式操作),然后只需要对与封闭叶关联的多边形执行完整的多边形内点测试这种方法应该大大加快每个点测试的速度,但需要额外的设置阶段来构建R树
希望这有帮助