У меня есть набор K случайно выбранных пикселей в 2D-изображении. Для каждого другого пикселя в изображении мне нужно выяснить, какой пиксель в множестве K ближе всего к нему (используя стандартную меру расстояния sqrt (dx ^ 2 + dy ^ 2)). Я знаю, что для каждого пикселя может быть несколько решений. Очевидно, это может быть сделано грубой силой против каждого пикселя в наборе, но я бы предпочел избежать этого, поскольку он неэффективен. Любые другие хорошие предложения?
Приветствия.
Не забывайте, что вам не нужно беспокоиться о квадратном корне.
Если вы просто хотите найти ближайший (а не фактическое расстояние), просто используйте dx^2 + dy^2, который даст вам квадрат расстояния к каждому элементу, что так же полезно.
Если у вас нет структуры данных, обертывающей этот список пикселей вверх, вам нужно просто протестировать их все.
Если у вас есть определенная гибкость, есть множество хороших способов сокращения рабочей нагрузки. Сделайте Quadtree или сохраните отсортированный список пикселей (отсортированный по x и отсортированный по y), чтобы быстрее сократить ваш поиск.
Мне нужно будет согласиться с jk и Ewan с помощью диаграммы Вороного. Это разделит пространство в многоугольниках. Каждая точка в K будет иметь многоугольник, описывающий все точки, которые ближе всего к нему. Теперь, когда вы получаете запрос точки, вам нужно найти, в каком полигоне она лежит. Эта проблема называется Point Location и может быть решена путем создания Трапецеидальной карты.
jk уже связан с созданием диаграммы Вороного с помощью Фортунный алгоритм, который принимает O (n log n) вычислительные этапы и расходы O (n).
Этот сайт показывает вам, как сделать трапециевидную карту и как ее запросить. Вы также можете найти некоторые границы:
Ожидаемое время создания: O (n log n)
Ожидаемая сложность пространства: O (n)
Но самое главное, ожидаемое время запроса: O (log n). Это (теоретически) лучше, чем O (& radic; n) kD-дерева.
Мой источник (кроме ссылок выше): Вычислительная геометрия: алгоритмы и приложения, главы шесть и семь.
Здесь вы найдете подробную информацию о двух структурах данных (включая подробные доказательства). В книжной версии Google есть только часть того, что вам нужно, но другие ссылки должны быть достаточными для вашей цели. Просто купите книгу, если вас интересует такая вещь (это хорошая книга).
Конструкция Диаграммы Вороного - это ветвь Вычислительная геометрия. Конструкция Триангуляции Делоне включает в себя аналогичные соображения. Возможно, вы сможете адаптировать один из следующих алгоритмы Delaunay в соответствии с вашими потребностями.
Поместите точки в дерево KD, после этого очень быстро найдите ближайшего соседа. Подробнее см. эту статью о википедии.
Это называется поиском ближайшего соседа. Дональд Кнут назвал это проблемой почтового ветки.
Существует ряд решений: линейный поиск, чувствительность к местоположению, файлы векторной аппроксимации и разбиение пространства.
Поиск в googling должен помочь.
то, что вы пытаетесь сделать, это построить диаграмму voronoi, это можно сделать в O (n log n), используя развертка плоскости
Другой намек: расстояние всегда больше или равно каждой разности координат и всегда меньше или равно их сумме, т.е.
d >= dx, d >= dy, d <= dx + dy.
Это может помочь вам сделать сортировку более эффективно.
В зависимости от того, насколько плотно это изображение заполнено пикселями, вам может быть лучше просто искать внешний вид от вашего пикселя происхождения.
Я запрограммировал что-то подобное для эмуляции графического терминала. То, что я закончил, это программирование шаблона поиска в форме прямоугольной спирали, которая выросла из центральной точки, и я позволил ей расти, пока она не ударила. Это было достаточно быстро для этой цели, даже на старом процессоре.