0

我有一个笛卡尔平面上的点列表和一个测试点。我想找到最接近测试点的三个点的列表索引。找到这些索引的更好方法是什么？提前感谢您的旅游回复。

=== 编辑 ===

我在 C++ 中找到了解决方案。首先我创建一个向量：

typedef struct
{
  int iIndex;
  double dSqrDistance;
} IndexedDistance;

std::vector<IndexedDistance> xDistanceVector;

然后是一个对其元素进行排序的函数

bool compareIndexedDistance(IndexedDistance xD1, IndexedDistance xD2)
{
  return (xD1.dSqrDistance < xD2.dSqrDistance);
}

然后在一个循环中计算所有距离，然后对它们进行排序，最后我取前三个元素：

IndexedDistance xDistanceElement;
for (int i = 0; i < xPointList.size(); i++)
{
  dSqrDistance = xPointList.at(i).sqrDistance(xTestPoint);
  xDistanceElement.iIndex = i;
  xDistanceElement.dSqrDistance = dSqrDistance;
  xDistanceVector.push_back(xDistanceElement);
}

std::sort(xDistanceVector.begin(), xDistanceVector.end(), compareIndexedDistance);
xDistanceVector.resize(3);

就这样，我找到了我需要的东西。我不知道这是否是最好的方法，但它似乎有效。

4

1 回答 1

0

二进制空间分区可以提供 O(log n * log n) 的算法复杂度。

  1. 确定点集的界限。Infinum 和 supremum 点将为您提供一个轴对齐的正方形，其中包含集合中的所有点。
  2. 通过任意轴将边界方块一分为二。为每个正方形制作一个单独的包含点列表。将每个边界方块链接到父方块。
  3. 重复分割边界方块（第 2 步），直到包含点的相应列表足够小以使用穷举搜索。

现在，您将能够使用树搜索来定位感兴趣点周围的空间，从而大大减少距离测试的次数。

棘手的部分是您必须扫描兴趣点周围的所有相邻边界方块，因为最近的点可能位于其中任何一个。

于 2014-07-22T14:23:55.103 回答