以有效的方式找到最近点

Question

我在 2d 平面上有一个点，例如 (x0,y0) 和一组 n 点 (x1,y1)...(xn,yn)，我想在 a 中找到距离 (x0,y0) 最近的点比尝试所有要点要好得多。有什么解决办法吗？

我还应该说我的观点是这样排序的：

bool less(point a,point b){
  if(a.x!=b.x)
     return a.x<b.x;
  else
     return a.y<b.y;
 }

Answer 1

使用四叉树进行 2D
http://en.wikipedia.org/wiki/Quadtree

Answer 2

Voronoi 图 专为快速查找最近点而设计。尽管实现起来很痛苦，但您可能会找到一些现有的库/实现。

还可以选择将平面重复划分为正方形，从而构建某种树，其中每个非叶节点有 4 个子节点（右上角正方形、右下正方形等）。然后，在四个方格中找到你的点所在的方格，并递归地继续下去。通常，这会产生足够接近的点，因此您可以消除检查其他方块的需要。
但很容易为该策略创建一个“反例”，这将导致线性时间。

但是您无法对已排序的数组执行太多操作来加快该过程。您将需要一个特殊的数据结构。

编辑
第二个结构称为四叉树，感谢VGE提供了这个名称。

Answer 3

为了高效的最近邻搜索，您需要使用空间分区方案，例如 kd-树。

Answer 4

如果您不使用任何类型的树数据结构来帮助限制必须查询的值的范围，则您将必须检查潜在“邻居”范围中的每个点。限制比较的一种方法是检查距给定点的平方距离的最小值：

Point myPoint = {x, y};
std::vector<Point> otherPoints; // given list of points to check

struct PointDistance
{
    Point pt;
    float dist;
};

std::vector<PointDistance> squaredDistances(otherPoints.size()); // will be filled in with squared distances

float CalculateDistance(const Point& pt1, const Point& pt2)
{
    float deltaX = pt1.x - pt2.x;
    float deltaY = pt1.y - pt2.y;
    return (deltaX * deltaX) + (deltaY * deltaY);
}

// should be changed to use an algorithm, but for clarity done as a loop here
for (int i = 0; i < otherPoints.size(); ++i)
{
    PointDistance pd;
    pd.pt = otherPoints[i];
    pd.dist = CalculateDistance(myPoint, pd.pt);
    squaredDistances.push_back(pd);
}

bool DistanceLess(const PointDistance& lhs, const PointDistance& rhs)
{
    return lhs.dist < rhs.dist;
}

std::sort(squaredDistances.begin(), squaredDistances.end(), DistanceLess);

// squaredDistances[0].pt will be your closest point.

Answer 5

如果您要创建 N 个点的集合，那么您可以根据它们与所考虑的点的线性距离对它们进行散列和映射，而不是仅仅将它们推入集合中。因此具有相同线性距离的点将位于同一个桶中。然后根据距离获取点将是一个恒定时间的操作。

Answer 6

一个特别好的解决方案是 ANN：用于近似最近邻搜索的库。 我'我们用它来进行三角测量中的点定位。您用点初始化数据结构，在我的例子中，我使用三角形的中心点。然后您可以传入另一个点并返回近似最近邻点的列表。甚至返回的点数也可以作为参数进行选择。不管怎样，对于我的目的来说，ANN 是一个很棒的图书馆，我建议你去看看。

祝你好运！