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

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

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

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

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

http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

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


c# point 2d
person David Rutten    schedule 25.09.2009    source источник
comment
У вас есть уравнения, описывающие эту поверхность? Похоже, вы просите 3D-решение, поскольку оранжевые точки находятся внутри.   -  person James Black    schedule 25.09.2009
comment
Это точная перефразировка вопроса? У меня есть набор очков; Я хочу упорядочить их по убыванию по расстоянию до ближайшей другой точки в наборе, а затем отбросить из моего упорядочивания любые точки на выпуклой оболочке. Затем вы можете взять первые n элементов из этого списка.   -  person Eric Lippert    schedule 25.09.2009
comment
Я думаю, что оранжевые точки — это возможные точки, которые он хочет определить, а не точки, которые есть в наборе.   -  person RMorrisey    schedule 25.09.2009
comment
@ Эрик, нет. У меня есть набор точек, и я хочу найти новые точки, начиная с самой удаленной от всего остального.   -  person David Rutten    schedule 25.09.2009
comment
А, понял. Выполните поиск в Интернете по диаграмме Вороного. Думаю, это может тебе помочь. Готов поспорить, что существует связь между самой большой вороной областью и ее краями с набором, который вы хотите определить.   -  person Eric Lippert    schedule 25.09.2009
comment
@ Эрик, диаграммы Вороного и триангуляции Делоне двойственны друг другу, поэтому самый большой треугольник в сетке Делоне, вероятно, даст тот же результат. К сожалению, код, который я написал для delaunay и voronoi, находится в другом проекте (VB.NET D'oh!), поэтому мне потребуется некоторое время, чтобы перевести его целиком.   -  person David Rutten    schedule 25.09.2009

Ответы (2)


arrow_upward
1
arrow_downward

Это хороший пример проблемы, которую можно решить с помощью KD-Tree. , есть несколько хороших заметок в Numerical Recipes 3rd Add.

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

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

person tbischel    schedule 25.09.2009
comment
Интересный. Я буду продолжать это, это определенно звучит многообещающе. Либо найдите пустые прямоугольники в деревьях Kd или Quad, либо, возможно, центры больших треугольников в триангуляции Делоне. - person David Rutten; 25.09.2009
comment
еще одна вещь может заключаться в том, что эта область может вводить в заблуждение ... у вас может быть высокая узкая коробка, так что на самом деле она будет близка к точке. Вероятно, лучшей метрикой будет наименьшая длина ребра четырехугольника и поиск четырехугольников, которые максимизируют эту метрику. - person tbischel; 25.09.2009

arrow_upward
1
arrow_downward

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

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

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

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

person richardtallent    schedule 25.09.2009
comment
Это работает только в том случае, если оранжевые точки известны заранее - я думаю, он пытается найти/сгенерировать точки, которые не близки к другим. - person Reed Copsey; 25.09.2009
comment
Я могу довольно быстро найти ближайшие точки со структурой QuadTree, этот код у меня уже есть. Проблема в том, что количество точек внутри выпуклой оболочки огромно. Чтобы получить необходимую мне точность, потребуются миллионы и миллионы поисков. Изображение показывает довольно хорошее распределение, но иногда точки чрезвычайно сгруппированы в далекие галактики. Мне нужно, чтобы это было очень быстро, так как оно вызывается в графическом интерфейсе, и мне нужно поддерживать частоту обновления более 30 кадров в секунду. Я ценю ответ, но это не сработает. - person David Rutten; 25.09.2009
comment
@Reed: мой алгоритм сравнивал каждую точку с каждой другой точкой, поэтому он автоматически определял, какие из них (на основе некоторого порогового значения в стиле TOP x следует считать оранжевыми. - person richardtallent; 25.09.2009