Ближайшая точка к данной точке

Question

У меня есть набор K случайно выбранных пикселей в 2D-изображении. Для каждого другого пикселя в изображении мне нужно выяснить, какой из пикселей в наборе K наиболее близок к нему (используя стандартную меру расстояния sqrt (dx ^ 2 + dy ^ 2)). Я знаю, что может быть более одного решения для каждого пикселя. Очевидно, что это может быть сделано грубой силой против каждого пикселя в наборе, но я бы предпочел этого избежать, так как это неэффективно. Любые другие хорошие предложения?

Приветствие.

Answer 1

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

Если вы просто хотите найти ближайший (а не его действительное расстояние), просто используйте dx^2 + dy^2, который даст вам квадрат расстояния до каждого элемента, что также полезно.

Если у вас нет структуры данных, упаковывающей этот список пикселей, вам нужно будет просто проверить их все.

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

Answer 2

Мне придется согласиться с Дж. К. и Эваном в создании диаграммы Вороного . Это разделит пространство на многоугольники. Каждая точка в K будет иметь многоугольник, описывающий все точки, которые находятся ближе всего к ней. Теперь, когда вы получаете запрос к точке, вам нужно найти, в каком полигоне она лежит. Эта проблема называется Расположение точки и может быть решена путем построения Трапециевидной карты .

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

Но самое главное, ожидаемое время запроса: O (log n). Это (теоретически) лучше, чем O (& radic; n) kD-дерева.

Мой источник (кроме ссылок выше): Вычислительная геометрия: алгоритмы и приложения , главы шесть и седьмая.

Там вы найдете подробную информацию о двух структурах данных (включая подробные доказательства). Версия книг Google содержит только часть того, что вам нужно, но других ссылок должно быть достаточно для вашей цели. Просто купите книгу, если вы заинтересованы в подобных вещах (это хорошая книга).

Answer 3

Построение Диаграммы Вороного - это ветвь Вычислительная геометрия .Построение Триангуляции Делоне предполагает аналогичные соображения.Возможно, вам удастся адаптировать один из следующих алгоритмов Делоне в соответствии с вашими потребностями.

• Алгоритмы переворачивания
• Пошаговые
• Разделяй и властвуй
• Sweepline

Answer 4

Поместите точки в дерево KD, после этого очень быстро найти ближайшего соседа. Подробнее см. эту статью в Википедии.

Answer 5

вы пытаетесь построить диаграмму Вороного , это можно сделать в O (n log n) с помощью развертки плоскости

Answer 6

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

Существует несколько решений: линейный поиск, локальное хеширование, файлы векторной аппроксимации и разбиение пространства.

Гугл должен помочь.

Answer 7

Еще один совет: расстояние всегда больше или равно каждой разнице координат и всегда меньше или равно их сумме, т.е.

d >= dx, d >= dy, d <= dx + dy.

Это может помочь вам выполнить сортировку более эффективно.

Answer 8

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

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