图的划分以定位点

Question

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

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

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

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

Answer 1

我首先要消除所有不能包含点的区域。

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

然后你可以按区域的最小和最大x和y坐标进行排序（共有4种排序方式）。您可以消除所有最小 x 坐标大于您点等 x 坐标的区域。

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

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