algorithm - 图的划分以定位点

Question

我有一个区域已经被划分为数十个子区域(就像一个国家被划分为多个州)。

现在我有了一个点坐标，告诉我该点处于哪个状态的最佳算法是什么？

当然，我可以逐个子区域匹配子区域，但这很愚蠢，因为我必须平均搜索一半，对吗？

有没有一种算法可以确定如何将相邻的几个子区域组合在一起方便搜索，从而优化搜索次数？

Answer 1

我将从消除所有不能包含点的区域开始。

假设您有一个 2D 笛卡尔坐标系，您有一个作为 2D 向量的点，并且这些区域被描述为其边界点的集合。

然后您可以根据区域的最小和最大x 和y 坐标对区域进行排序(共有4 种排序方式)。您可以消除所有最小 x 坐标大于您点等的 x 坐标的区域。

之后，您可以使用简单的 ray-casting algorithm 检查剩余的多边形你应该很好。

如果您有一个结构可以使区域在所有不同的方向上排序，那么这将非常有效，因为您可以在对数时间内消除这些区域。