Все k ближайших соседей в 2D, C ++

Question

Мне нужно найти для каждой точки набора данных всех его ближайших соседей. Набор данных содержит ок. 10 миллионов 2D очков. Данные близки к сетке, но не образуют точную сетку ...

Эта опция исключает (на мой взгляд) использование деревьев KD, где основное предположение состоит в том, что точки не имеют одинаковую координату x и координату y.

Мне нужен быстрый алгоритм O (n) или лучше (но не слишком сложный для реализации :-))), чтобы решить эту проблему ... Из-за того, что boost не стандартизирован, я не хочу его использовать ...

Спасибо за ваши ответы или примеры кода ...

Answer 1

Я бы сделал следующее:

1. Создать большую сетку поверх точек.

2. Пройдите через точки линейно идля каждой из них определите, к какой большой «ячейке» она принадлежит (и добавьте точки в список, связанный с этой ячейкой).

   (это можно сделать за постоянное время для каждой точки, просто выполнитецелочисленное деление координат точек.)

3. Теперь снова пройдем точки линейно.Чтобы найти 10 ближайших соседей, вам нужно только посмотреть на точки в соседних, более крупных клетках.

   Поскольку ваши точки довольно равномерно распределены, вы можете сделать это во времени, пропорциональном количеству точек в каждом(большая) ячейка.

Вот (уродливая) картинка, описывающая ситуацию:

Ячейки должны быть достаточно большими для(центр) и соседние ячейки содержат 10 ближайших точек, но достаточно малы, чтобы ускорить вычисления.Вы можете видеть это как «хэш-функцию», где вы найдете самые близкие точки в том же сегменте.

(Обратите внимание, что строго говоря, это не O (n) , а путем настройкиразмер больших ячеек, вы должны быть достаточно близко.: -)

Answer 2

Я использовал библиотеку под названием ANN (Приблизительный ближайший сосед) с большим успехом.Он использует подход Kd-дерева, хотя было несколько попыток.Я использовал его для определения точки на триангулированной поверхности.Возможно, вам повезет с этим.Он минимален и его легко включить в мою библиотеку, просто опустив его источник.

Удачи в этом интересном задании!