Лучшая динамическая структура данных для 2d круга ближайшего соседа

Название-это большая часть проблемы. У меня есть набор кругов, каждый из которых задан центром C и радиусом R. расстояние между двумя кругами - это Евклидово расстояние между их центрами минус оба их радиуса. Для кругов a и b,

D_ab = |C_a-C_b| - r_a-r_b.

Обратите внимание, что это может быть отрицательным, если круги перекрываются.

Тогда какова самая быстрая структура данных для нахождения ближайшего (минимального расстояния) соседа данного круга в сет?

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

Это будет сердце системы, где типичное число кругов составляет 50 000 и 10 тысяч запросов, вставок и удалений будут необходимы, в идеале на скорости взаимодействия с пользователем (секунда или меньше) на планшетном устройстве высокого класса.

Ближайшим соседом точки является изучили до смерти, но эта версия с кругами кажется несколько сложнее.

Я посмотрел на kd-деревья, Квадро-деревья, r-деревья и некоторые их вариации. Оба совета о том, какой из них лучше всего попробовать, а также новые предложения были бы потрясающей помощью.
4 8
language-agnostic algorithm computational-geometry

4 ответа:

Деревья покрытия являются еще одной возможностью для структуры близости. Они не поддерживают удаление (?), но вы можете мягко удалять и перестраивать в фоновом режиме, чтобы мусор не скапливался, что может быть полезным методом для других структур.

Существует редукция от задачи двумерного круга к задаче трехмерной точки с фанковой метрикой, которая выглядит следующим образом. (Структуры близости, которые вы назвали, должны быть адаптируемыми.) Отображение окружности с центром в точке (x, y) радиусом r на точка (x, y, r). Для определения длины вектор (DX, dу, DZ, а), будет корень(с DX**2 + ды**2) + АБС(ДЗ). Это вызывает метрику. Чтобы найти окружность, ближайшую к центру (x, y) (радиус круга запроса не имеет значения), выполните поиск близости по (x, y, R), где R больше или равен максимальному радиусу окружности (возможно, можно изменить структуру близости, чтобы не было необходимости отслеживать R).

Из моего опыта реализации kd-деревьев и диаграмм Вороного на точках, значительно проще будет реализовать kd-деревья с нуля. Даже если вы повторно используете чьи-то надежные геометрические примитивы (и, пожалуйста, сделайте это, чтобы сохранить свое здравомыслие, если вы идете этим путем), вырожденные граничные случаи расположения Вороного/точки требуют времени, чтобы получить правильный результат.

5

Я предлагаю следующую эвристику, используя KD-дерево или что-то еще, что позволяет O(log N) ближайший сосед. Вместо того, чтобы использовать одну точку и радиус для представления окружности. Используйте k равноудаленных точек на самой окружности, плюс центр окружности, иначе у вас могут возникнуть проблемы с маленьким кругом внутри большого круга. Это то же самое, что использовать правильный многоугольник из k вершин для представления круга. Тогда можно взять одну вершину и найти ее ближайший сосед (игнорируя вершины на том же круге), чтобы найти приближение к тому, что является ближайшим кругом на основе ближайшего правильного многоугольника.

Выступления следующие:

Создайте KD-дерево: O (KN log kN)

Удалить / добавить окружность в KD-дерево: O(K log kN) - Добавить или удалить все k точек окружности внутри KD-дерева

Запрос ближайшего круга (Circle): O (k log kN) -Это делается путем удаления сначала всех k точек окружности (O(K log kN)), так как это не ужасно полезно узнать, что ближайшим соседом круга является, что неудивительно, сам круг. Затем для каждого k точек в окружности найдите ближайшего соседа (O (k log kN)). Как только ближайшие соседи найдены, фактическим ближайшим (с некоторой погрешностью) является тот, у которого наименьшее расстояние (после вычисления истинного расстояния на основе точки и радиуса) (O(1)).

Я бы предложил либо использовать k = log (N), если вы предпочитаете, чтобы это было быстро, либо k = sqrt(N), если вы предпочитаете, чтобы это было точный.

Кроме того, возможно, я не рассматривал какой-то частный случай, который вызывает проблемы, поэтому следите за ними.

2

Если есть гарантия, что круги не имеют большого радиуса, по крайней мере, что максимальный радиус (R) значительно меньше, чем площадь, где расположены круги, чем я думаю, что он может быть покрыт стандартным разделением пространства и поиском ближайших соседей.

При поиске окружности в множестве, имеющем минимальное расстояние до заданной окружности, радиус заданной окружности не имеет значения (определение расстояния.) Из-за того, что это одно и то же, если только центр (Точка) сравнивается с множеством круги.

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

  • найти ближайший центр к данной точке P. скажем, окружность C с центром c и радиусом r.
  • центр окружности, который ближе к P, на ваше расстояние, может находиться только в кольце вокруг P с внутренним радиусом r и внешним радиусом R-d (P, c). Для поиска кандидатов достаточно найти разделы, пересекающие это кольцо.

Можно оптимизировать поиск, объединив эти два шага. На первом этапе некоторые разделы, представляющие интерес, уже посещены. Запоминая, какие разделы посещаются, и окружность с минимальным расстоянием, найденным в этих разделах, поиск на втором шаге может быть уменьшен.

1

Спасибо @David Eisenstadt за идею трехмерной поисковой структуры. Это часть лучшего ответа, хотя его странная метрика не нужна.

Ключ состоит в том, чтобы подробно рассмотреть, как работает поиск ближайших соседей. Я покажу это для Квадри. KD-деревья с k=3 похожи. Вот псевдокод: 
# Let nearest_info be a record containing the current nearest neighbor (or nil 
# if none yet) and the distance from point to that nearest neighbor.
def find_nearest_neighbor(node, target, nearest_info)
  if node is leaf
    update nearest_info using target and the points found in this leaf
  else
    for each subdivision S of node
      if S contains any point P where dist(P,T) < nearest_info.distance,
        find_neareast(S, target, nearest_info)
      end
    end
  end
end

Когда это сделано, nearest_info содержит ближайший сосед и его расстояние.

Ключ-это if S contains any point P where dist(P,T) < nearest_info.distance. В трехмерном пространстве из (x,y,r) троек, описывающих окружности, мы есть 

def dist(P,T)
  return sqrt( (P.x - T.x)^2 + (P.y - T.y)^2 ) - P.r - T.r 
end

Здесь p-произвольная точка в октанте из восьмеричного дерева набора кубовидной. Как рассмотреть все точки в кубоиде? Заметим, что все компоненты T эффективно фиксированы для данного поиска, поэтому будет понятнее, если мы запишем цель в виде постоянной точки (a, b, c): 

def dist(P)
  return sqrt( (P.x - a)^2 + (P.y - b)^2 ) - P.r
end

, где мы полностью исключили c = T.r, потому что его можно вычесть из минимального расстояния после завершения алгоритма. Другими словами, радиус цели не влияет на результат.

При этом довольно легко видеть, что P, необходимое для получения минимального расстояния до кубоида, является евклидовым ближайшим к цели относительно x и y и с максимальным представленным радиусом. Это очень легко и быстро вычислить: расстояние 2d точка-прямоугольник и операция 1d max.

В ретроспективе все это очевидно, но потребовалось некоторое время, чтобы увидеть это с правильной точки зрения. Спасибо за идеи.
0