geometry - 从大量多边形中确定一个点在哪些多边形内

Question

假设我有一个 2D 平面，上面覆盖着多边形（标识为顶点数组），类似于：

假设我在这个平面上也有一个坐标点，返回该点所在的多边形的最简单方法是什么？

尽管此示例列出了 4 个多边形，但对每个多边形运行检查以查看该点是否在其中会很简单，但我正在构建一个目前有大约 150 个多边形的系统，并且可以扩展到数千个，所以这样做这种方式可能会变得非常缓慢。

那么，是否有任何解决方案不会导致遍历所有可用多边形并检查该点是否存在？

Answer 1

您可以使用 kd-tree 或 r-tree。它可以减少搜索空间。您也可以寻找四叉树。您可以选择四边形大小以适合多边形并最小化重叠边界框。