Выпуклая оболочка простого многоугольника - Convex hull of a simple polygon

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

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

Выпуклая оболочка простого многоугольника может быть разбита на сам многоугольник и на многоугольные. карманы ограниченный многоугольная цепь многоугольника вместе с одним выпуклым краем оболочки. Многократное отражение произвольно выбранного кармана через этот выпуклый край корпуса создает последовательность больших простых многоугольников; согласно Теорема Эрдеша – Надя, этот процесс в конечном итоге завершается выпуклым многоугольником.

Структура

Выпуклая оболочка простого многоугольника сама является выпуклый многоугольник. Наложение исходного простого многоугольника на его выпуклую оболочку разбивает этот выпуклый многоугольник на области, одна из которых является исходным многоугольником. Остальные регионы называются карманы. Каждый карман представляет собой простой многоугольник, ограниченный многоугольная цепь на границе данного простого многоугольника и одним ребром выпуклой оболочки. У уже выпуклого многоугольника карманов нет.[1]

Можно сформировать иерархическое описание любого данного многоугольника, построив его корпус и карманы таким образом, а затем рекурсивно сформировав иерархию того же типа для каждого кармана.[1] Эта структура, названная выпуклое дерево разностей, можно построить эффективно.[2]

Алгоритмы

Нахождение выпуклой оболочки простого многоугольника можно выполнить в линейное время. Было обнаружено, что несколько ранних публикаций по этой проблеме неверны, часто потому, что они приводили к промежуточным состояниям с пересечениями, которые вызывали их разрушение. Первый правильный алгоритм линейного времени для этой проблемы был дан Маккаллум и Авис (1979).[3] Даже после его публикации другие неверные алгоритмы продолжали публиковаться.[4] Брённиманн и Чан (2006) напишите, что большинство опубликованных алгоритмов решения проблемы неверны,[5] хотя более поздняя история, собранная Грегом Алуписом, перечисляет только семь из пятнадцати алгоритмов как неправильные.[6]

Особенно простой алгоритм для этой проблемы был опубликован Грэм и Яо (1983) и Ли (1983). Словно Сканирование Грэма алгоритм для выпуклой оболочки точечных множеств, он основан на структура данных стека. Алгоритм обходит многоугольник по часовой стрелке, начиная с вершины, о которой известно, что она находится на выпуклой оболочке (например, ее крайней левой точки). При этом он сохраняет в стеке выпуклую последовательность вершин, тех, которые еще не были идентифицированы как находящиеся в карманах. Точки в этой последовательности - это вершины выпуклого многоугольника (не обязательно оболочки всех видимых до сих пор вершин), на некоторых из ребер которого могут быть карманы. На каждом шаге алгоритм следует по пути вдоль многоугольника от вершины стека до следующей вершины, которая не находится в одном из двух карманов, смежных с вершиной стека. Затем, хотя две верхние вершины в стеке вместе с этой новой вершиной не находятся в выпуклом положении, он выталкивает стек, прежде чем, наконец, поместить новую вершину в стек. Когда обход по часовой стрелке достигает начальной точки, алгоритм завершается, и стек содержит вершины выпуклой оболочки в порядке по часовой стрелке. Каждый шаг алгоритма либо выталкивает вершину в стек, либо выталкивает ее из стека, и каждая вершина выталкивается и выталкивается не более одного раза, поэтому общее время для алгоритма линейно.[7][8] Если входные вершины указаны в массиве в порядке по часовой стрелке, то выходные данные могут быть возвращены в том же массиве, используя только постоянное количество дополнительных переменных в качестве промежуточного хранилища.[5]

Аналогичный метод можно использовать и для построения выпуклых оболочек кусочно гладкий замкнутые кривые на плоскости.[9]Используя дек вместо стека аналогичный алгоритм может быть обобщен на выпуклую оболочку любой многоугольной цепи, а алгоритм для простых многоугольников может быть запущен в любой вершине многоугольника, вместо того, чтобы требовать крайнюю вершину в качестве начальной вершины.[10]

Откидные карманы

Основная статья: Теорема Эрдеша – Надя

А кувырок of a pocket формирует новый многоугольник из данного, отражая многоугольную цепь, ограничивающую карман через выпуклый край корпуса кармана. Каждое отражение создает еще один простой многоугольник с равным периметром и большей площадью, хотя несколько одновременных отражений могут привести к пересечению. Перевернув произвольно выбранный карман, а затем повторяя этот процесс с карманами каждого последовательно сформированного многоугольника, вы получите последовательность простых многоугольников. Согласно Теорема Эрдеша – Надя, этот процесс переворота в конечном итоге завершается достижением выпуклого многоугольника. Как и проблема построения выпуклой оболочки, эта проблема имеет долгую историю неверных доказательств.[11]

Рекомендации

  1. ^ а б Tor, S. B .; Миддледич, А. Э. (1984), "Выпуклое разложение простых многоугольников", Транзакции ACM на графике, 3 (4): 244–265, Дои:10.1145/357346.357348
  2. ^ Раппопорт, Ари (1992), "Эффективный адаптивный алгоритм для построения выпуклого дерева разностей простого многоугольника", Форум компьютерной графики, 11 (4): 235–240, Дои:10.1111/1467-8659.1140235
  3. ^ Маккаллум, Дункан; Авис, Дэвид (1979), "Линейный алгоритм поиска выпуклой оболочки простого многоугольника", Письма об обработке информации, 9 (5): 201–206, Дои:10.1016/0020-0190(79)90069-3, МИСТЕР  0552534
  4. ^ Туссен, Годфрид (1991), «Контрпример алгоритму выпуклой оболочки для многоугольников», Распознавание образов, 24 (2): 183–184, Дои:10.1016 / 0031-3203 (91) 90087-Л, МИСТЕР  1087740
  5. ^ а б Брённиманн, Эрве; Чан, Тимоти М. (2006), "Компактные алгоритмы для вычисления выпуклой оболочки простой ломаной за линейное время", Вычислительная геометрия, 34 (2): 75–82, Дои:10.1016 / j.comgeo.2005.11.005, МИСТЕР  2222883
  6. ^ Алупис, Грег, История алгоритмов выпуклой оболочки с линейным временем для простых многоугольников, Университет Макгилла, получено 2020-01-01
  7. ^ Грэм, Рональд Л.; Яо, Ф. Фрэнсис (1983), "Нахождение выпуклой оболочки простого многоугольника", Журнал алгоритмов, 4 (4): 324–331, Дои:10.1016/0196-6774(83)90013-5, МИСТЕР  0729228
  8. ^ Ли, Д. Т. (1983), «О нахождении выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук, 12 (2): 87–98, Дои:10.1007 / BF00993195, МИСТЕР  0724699
  9. ^ Schäffer, Alejandro A .; Ван Вик, Кристофер Дж. (1987), "Выпуклые оболочки кусочно гладких жордановых кривых", Журнал алгоритмов, 8 (1): 66–94, Дои:10.1016/0196-6774(87)90028-9, МИСТЕР  0875326
  10. ^ Мелкман, Авраам А. (1987), "Он-лайн построение выпуклой оболочки простой ломаной линии", Письма об обработке информации, 25 (1): 11–12, Дои:10.1016 / 0020-0190 (87) 90086-X, МИСТЕР  0896397
  11. ^ Демейн, Эрик Д.; Гассенд, Блэз; О'Рурк, Джозеф; Туссен, Годфрид Т. (2008), «Все полигоны бесконечно переворачиваются ... верно?», Обзоры по дискретной и вычислительной геометрии, Современная математика, 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 231–255, Дои:10.1090 / conm / 453/08801, МИСТЕР  2405683