Быстрый алгоритм для вычисления объединения «локальных выпуклых оболочек»

У меня есть набор двумерных точек, из которых я хочу создать многоугольник (или набор полигонов), в котором изложена «форма» этих точек, , используя следующую концепцию :Быстрый алгоритм для вычисления объединения «локальных выпуклых оболочек»

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

Подход грубой силы при фактическом построении всех этих выпуклых оболочек является чем-то вроде O (N^2 + R^2 log R). Известен ли более эффективный алгоритм для получения того же результата? Или, возможно, другой способ выразить проблему?

Примечание: Я знаю альфа-формы, они разные; Я ищу алгоритм для выполнения описанного выше.

Следующее решение не работает - экспериментально опровергнуто в MATLAB.

~~Обновление: у меня есть предлагаемое решение.~~

Предложение: принять триангуляцию Деланея множества точек, удалить все треугольники, имеющие окружность больше R. Затем возьмем объединение оставшихся треугольников.

источник

2009-08-31 James

Я не уверен, чего вы пытаетесь достичь. Является ли это невыпуклой оболочкой, представляющей форму точечного облака лучше выпуклой? –

Да, это правильно. Немного похоже на альфа-формы: http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html. За исключением того, что мой метод дает визуально более приятные результаты (IMO) для данных, с которыми я работаю. – James

Да, с использованием вращающихся суппортов. Мой проф написал some stuff на этом, он начинается на странице 19.

источник

2009-08-31 02:41:11 mpen

Спасибо за интересную информацию, но я не уверен, как ее можно использовать для решения проблемы.Я вижу, как вращающиеся суппорты используются для нахождения тангенсов для слияния выпуклых оболочек подмножества в единую выпуклую оболочку, но это отличается от объединения выпуклых оболочек - результат может быть вогнутым или содержать отверстия, например. Я что-то упускаю? – James

О ... Я думаю, что неправильно понял, что вы подразумеваете под «союзом». Я предположил, что вы захотите объединить их в один выпуклый корпус. В этом случае я не уверен, есть ли какие-либо преимущества, которые могут быть использованы с использованием корпусов против невыпуклых полигонов. Я предлагаю вам взглянуть на существующие алгоритмы и посмотреть, есть ли какие-либо хитрости, которые вы можете сделать, чтобы воспользоваться преимуществами выпуклого многоугольника. – mpen

Ок, круто, да, я бы тоже не использовал «правильную» терминологию. Во всяком случае, я добавил предложенное решение к моему вопросу выше - если у вас есть какие-либо мысли по этому поводу, дайте мне знать. Приветствия. – James

Пожалуйста, дайте мне знать, если я неправильно понял проблему.

Я не вижу, как вы получаете N^2 раз для грубой форсировки всех выпуклых оболочек в худшем случае(). Что, если почти любые 2 точки ближе, чем R - в этом случае вам нужно как минимум N^2 * logN, чтобы просто построить выпуклые оболочки, оставьте в покое вычисление их объединения.

Кроме того, где R^2 * logR в вашей оценке исходит?

Худший случай (как я вижу) для огромного N - возьмем круг радиуса R/

источник

2009-08-31 08:40:51 Olexiy

Да, я был не очень понятен. O (N^2 + R^2 log R) на самом деле не является наихудшим временным временем, но является средним случаем для равномерно распределенных точек и достаточно малым R. N^2 был для нахождения множества точек в радиусе R каждый пункт. (Для каждой из N точек необходимо проверить расстояние до остальных N-1 точек). R^2 принимал равномерное распределение точек, так что число точек в каждой выпуклой оболочке будет пропорционально R^2. Вычисление выпуклой оболочки R^2 точек равно O (R^2 log R). Наконец, взяв объединение N выпуклых оболочек, я не был уверен и не ушел. – James

A sweep line algorithm может улучшить поиск R-соседей. В качестве альтернативы вы можете рассмотреть только пары точек, находящихся в соседних квадратах квадратной сетки ширины R. Обе эти идеи могут избавиться от N^2 - конечно, только если точки относительно редки.

Я считаю, что умная комбинация подметающего и выпуклого корпуса, находящего кошку, избавляется от N^2, даже если точки не разрежены (как в примере Олексия), но не могут найти конкретного алгоритма.

источник

2009-09-01 20:18:53

Спасибо за идею, теперь я пытаюсь решить проблему, используя подход линии развертки. Обязательно отправьте сообщение, если я придумаю хорошее решение. – James

Быстрый алгоритм для вычисления объединения «локальных выпуклых оболочек»

ответ

Смежные вопросы