Существует ли алгоритм для поиска почти выпуклой оболочки с учетом угла допуска?

9

Я хотел бы знать, если есть алгоритм, который дает множество точек и угол вычисляет выпуклую оболочку, если угол α=0 и дали α>0 вычисляет конверт, который более близко следует за «периметром».

Иллюстрация эффекта размера $ \ alpha $

И если есть определение непересекающегося периметра множества точек, в этом случае результирующий многоугольник, когда α большой.

Другой взгляд на проблему может состоять в том, чтобы найти алгоритм, который можно параметризировать, чтобы найти для α=0 минимальное решение по периметру (выпуклая оболочка) и для α=1 (нормализовано) полилинии минимальной площади, охватывающей все точки.

naufraghi
источник
Вы изучили концепцию сильно выпуклых множеств ?
Смертельное дыхание
Не могли бы вы уточнить цель α? Какой цели это служит?
Павел
Было бы разрешено предложить алгоритм, который больше работает как αрастет? Или вы ожидали увеличенияαуменьшит «ожидаемую» сложность?
hardthth
Я задумал это как угол, которому алгоритму позволено отходить от выпуклой оболочки. И нет, я не думаю, что это уменьшит сложность.
Науфраги

Ответы:

3

Вы можете исследовать так называемый альфа-корпус , например: пакет CRAN , Википедия по альфа-фигурам :
       введите описание изображения здесь
      [Изображение по этой ссылке .]

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

Джозеф О'Рурк
источник
Спасибо, альфа-формы очень интересны, они имеют расширенный набор свойств, которые я искал (меня интересует только один конверт), и реализация не сравнима с выпуклой оболочкой. Я подожду немного больше, если кто-то может предложить что-то попроще, если нет, я приму этот ответ.
Науфраги
1

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

αкритерий треугольника может быть сформулирован для данной пары последовательных граничных вершин как лежащий в области между дугой окружности и ее хордой = граничный сегмент. Можно назвать этот круговой сегмент.

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

hardmath
источник