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

Question

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

Cheers.

Answer 1

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

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

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

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

Answer 2

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

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

Путь к ним должен помочь.

Answer 3

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

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

Answer 4

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

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

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

Answer 5

, что вы пытаетесь сделать, это построить voronoi diagram это может быть сделано в O (N журнал N), используя plane sweep

Answer 6

Строительство Voronoi Diagrams является филиалом Computational Geometry. Конструкция Delaunay Triangulations включает в себя аналогичные соображения. Возможно, вы сможете адаптировать одно из следующих Delaunay algorithms в соответствии с вашими потребностями.

• алгоритмы Раскладные
• Инкрементальный
• разделяй и властвуй
• Sweepline

Answer 7

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

Answer 8

Должен согласиться с jk и Ewan с составлением Voronoi Diagram. Это разделит пространство в многоугольниках. Каждая точка в K будет иметь многоугольник, описывающий все точки, которые ближе всего к нему. Теперь, когда вы получаете запрос точки, вам нужно найти, в каком полигоне она лежит. Эта проблема называется Point Location и может быть решена путем построения Trapezoidal Map.

jk уже связан с созданием Voronoi Diagram с использованием Fortune's algorithm, который принимает вычислительные шаги O (n log n) и затраты O (n) пространства. This website показывает вам, как сделать трапециевидную карту и как ее запросить. Вы также можете найти некоторые оценки там:
Ожидаемое время создания: O (N журнал N)
Ожидаемое пространство сложность: O (п)

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

Мой источник (кроме ссылок выше): Computational Geometry: algorithms and applications, главы шесть и семь.

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