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

Question

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

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

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

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

---

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

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

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

Answer 1

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

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

Answer 2

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

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

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

1 Наихудший случай (на мой взгляд) для огромного N - возьмите круг радиуса R / 2 и случайным образом расположите точки на его границе и сразу за ней.

Answer 3

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