在点向量中找到最近的点

Question

我有一个指向非常简单的Point类的指针向量：

class Point{
public:
    float x;
    float y;
    float z;
};

我如何使用STL找到距离参考点最近的对象？是否需要先对向量进行排序，还是有更有效的方法？

您可以使用STL中的min_element算法来查找距离参考点最近的对象。不需要对向量进行排序，该算法将自动查找最小值并返回其迭代器。

- Damir

Answer 1

排序需要 O(n*log(N)) 的时间，因此效率不是很高。你可以通过遍历元素并记忆最佳匹配来在 O(n) 的时间内完成。

使用 <algorithm> 中的 for_each，你可以定义一个函数来跟踪最接近的元素，并在 O(n) 的时间内完成。

或者，你甚至可以使用同样来自 <algorithm> 的 min_element。

- Luchian Grigore

---

+1 对于 O(n)。我认为 std::min_element 可能是最自然的解决方案。 - Eitan T

Answer 2

这里的基本问题是您将多频繁地针对单个点集进行查询。

如果您只需在集合中找到一个最近的点，则@Lucian是正确的：您可以将点保持未排序状态，并执行线性搜索以找到正确的点。

如果您将对相同的点集进行相对较大数量的查询，则值得组织点数据以提高查询速度。 @izomorphius已经提到了k-d树，这绝对是一个好建议。另一个可能性（诚然，非常相似）是八叉树。在这两者之间，我发现八叉树要容易理解得多。理论上，k-d树应该稍微更有效（平均而言），但我从未看到过太大的区别 - 虽然也许使用不同的数据会产生显着差异。

请注意，构建像k-d树或八叉树这样的东西并不是非常慢，因此您不需要对一组点进行大量查询来证明构建它的必要性。一个查询显然不能证明它，两个查询可能也不行——但与Luchian所暗示的相反，O（N log N）（仅举例而言）实际上并不是非常慢。粗略地说，log（N）是数字N中的位数，因此O（N log N）并不比O（N）慢得多。这反过来意味着您不需要特别大量的查询来证明组织数据以加速每个查询的必要性。

- Jerry Coffin

Answer 3

如果你只知道向量中存在点，那么你不能比线性比较更快。但是，如果你有额外的知识，情况就会好很多。例如，如果你知道所有点都是有序的，且位于同一条直线上，那么就有一个对数解。

此外，还有更好的数据结构可以解决你的问题，例如k-d tree。它不是STL的一部分-你需要自己实现它，但这是解决你问题所需使用的数据结构。

- Ivaylo Strandjev

Answer 4

你可以尝试使用四叉树http://en.wikipedia.org/wiki/Quadtree

或类似的东西。

- Michael