6

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

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

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

4

4 回答 4

7

排序需要O(n*log(N))，因此效率不高。您可以O(n)通过迭代元素并记住最佳匹配来做到这一点。

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

或者，您甚至可以使用min_element, 也来自<algorithm>.

于 2012-06-25T13:55:39.150 回答
1

这里的基本问题是您多久会针对一组点进行查询。

如果您打算一次在集合中找到一个最近的点，那么@Lucian 是对的：您最好不要对这些点进行排序，然后进行线性搜索以找到正确的点。

如果您要针对同一组点进行相对大量的查询，则值得组织点数据以提高查询速度。@izomorphius 已经提到了一棵 kd 树，这绝对是一个好建议。另一种可能性（诚然，非常相似）是八叉树。在两者之间，我发现八叉树更容易理解。从理论上讲，kd 树应该稍微更有效（平均而言），但我从来没有看到太大的差异——尽管也许使用不同的数据，差异会变得显着。

但是请注意，构建类似 kd 树或 oct 树的东西并不是非常慢，因此您不需要针对一组点进行大量查询来证明构建一个点是合理的。一个查询显然不能证明它是合理的，而两个可能也不会 - 但与 Luchian 暗示的相反，O(N log N) （仅作为示例）并不是真的很慢。粗略地说，log(N) 是数字 N 中的位数，所以 O(N log N) 并不比 O(N) 慢很多。反过来，这意味着您不需要特别大量的查询来证明组织数据以加快每个查询的合理性。

于 2012-06-25T14:10:03.440 回答
0

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

或类似的东西。

于 2012-06-25T16:11:10.647 回答
0

如果你只知道向量中有点，你就不能比线性比较更快。但是，如果您有额外的知识，可以改进很多。例如，如果您知道所有点都是有序的并且位于同一条线上，则存在对数解。

还有更好的数据结构可以解决您的问题，例如kd 树。它不是 STL 的一部分——您必须自己实现它，但它是用于解决您遇到的问题的数据结构。

于 2012-06-25T13:58:21.530 回答