Поиск Удаленных точек в 2D

Question

У меня есть набор точек на бесконечной (ну, двойной точности) 2D плоскости.

Учитывая выпуклую оболочку для этого множества, как можно найти некоторые точки на внутри выпуклой оболочки, которые находятся относительно далеко от всех точек во входном наборе?

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

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

Поиск самой дальней точки http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

---

Обновить:Использование алгоритма Делоне для поиска больших пустых треугольников представляется отличным подходом для этого:Решение Делоне http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png

Answer 1

Это хороший пример проблемы, которая может быть решена с помощью KD-Деревья...есть несколько хороших замечаний в Числовых рецептах 3-го дополнения.

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

Сложность создания KD-Дерева составила бы O (n log ^ 2 n)...и создание отсортированного списка квадратичных размеров было бы равно O(n Log n).Кажется разумным даже для большого количества баллов (конечно, в зависимости от ваших требований).

Answer 2

Это наивный алгоритм:

1. Получите список точек внутри выпуклой формы.
2. Из них найдите минимальное расстояние до любой другой точки.
3. Ранжируйте все точки по их соответствующим значениям R
4. Выберите верхние x точек.

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

Чтобы оптимизировать поиск, вы можете разделить пространство на сетку и назначить каждой точке местоположение в сетке.Затем ваш поиск по (2) выше сначала будет проверяться в пределах того же квадрата и окружающие 8 квадратов.Если минимальное расстояние до другой точки находится в пределах то же самое square, верните это значение.Если это от одного из 8 и расстояние таково, что точка за пределами 9 может быть ближе, вам нужно затем проверить следующий контур местоположений сетки за пределами этих 9 на наличие каких-либо более близких, чем те, которые находятся внутри 9.Промыть /повторить.