确定某个位置是否位于Google地球的多边形内？

Question

所以我有一个.csv文件约50,000坐标条目和.kml文件约40多边形。

对于我来说，确定哪些点位于多边形内的最佳方法是什么？

我试图编写一个python script执行光线追踪算法来逐点确定，但它需要5分钟以上，我需要运行这么多次。有什么建议么？

Answer 1

在标准模板库（C++，Java）中搜索Lucas Simonson的算法。我认为他们在2010年被接受。他在基本的多边形操作方面做了一些奇妙的工作，减少了复杂性的次序。在多边形集合中包含一个点就是其中之一。