Найти ближайшую точку из вектора точек

Question

У меня есть вектор указателей на очень простой Point класса:

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

Как найти ближайший объект к точке референтной с использованием STL?
Нужен ли мне сначала сортировать вектор первым или есть более эффективный способ?

Answer 1

Сортировка занимает O(n*log(N)), поэтому она не очень эффективна. Вы можете сделать это в O(n), просто перебирая элементы и запоминая наилучшее соответствие.

Используя for_each от <algorithm>, вы можете определить функцию, которая отслеживает самые близкие элементы и заканчивается в O(n).

Или, возможно, вы даже можете использовать min_element, также из <algorithm>.

Answer 2

Вы не можете идти быстрее, чем линейное сравнение, если знаете только, что есть точки в векторе. Однако, если у вас есть дополнительные знания, многое можно улучшить. Например, если вы знаете, что все точки упорядочены и лежат на одной строке, есть логарифмическое решение.

Также существуют лучшие структуры данных для решения вашей проблемы, например, k-d tree. Он не является частью STL - вам придется реализовать его самостоятельно, но именно структура данных используется для решения проблемы, которая у вас есть.

Answer 3

Основной вопрос: как часто вы будете делать запросы против одного набора точек.

Если вы собираетесь найти одну ближайшую точку в наборе один раз, то @Lucian прав: вы можете также оставить точки не отсортированными и выполнить линейный поиск, чтобы найти нужную точку.

Если вы сделаете относительно большое количество запросов против одного и того же набора точек, целесообразно организовать точечные данные для повышения скорости запроса. @izomorphius уже упоминал дерево k-d, и это, безусловно, хорошее предложение. Другая возможность (по общему признанию, совершенно аналогичная) - это oct-tree. Между ними, я нахожу, что oct-tree немного легче понять. Теоретически, дерево k-d должно быть немного более эффективным (в среднем), но я никогда не видел большой разницы - хотя, возможно, с разными данными разница была бы значительной.

Однако следует отметить, что построить что-то, как к-й дерево или октаву дерево не страшно медленно, так что вам не нужно делать очень много запросов относительно набора точек, чтобы оправдать строительство одного. Один запрос явно не оправдывает его, и два, вероятно, тоже не будут, но, вопреки тому, что предполагает Лучиан, O (N log N) (например,) не очень медленный. Грубо говоря, log (N) - это число цифр в числе N, поэтому O (N log N) на самом деле не намного медленнее, чем O (N). Это, в свою очередь, означает, что вам не нужно особо большое количество запросов, чтобы оправдать организацию данных, чтобы ускорить их.

Answer 4

вы можете попробовать использовать квадрадерево http://en.wikipedia.org/wiki/Quadtree

или что-то подобное.