Выпуклая оболочка простого многоугольника
В дискретной геометрии и вычислительной геометрии выпуклая оболочка простого многоугольника — это многоугольник минимального периметра, содержащий заданный простой многоугольник . Это частный случай более общего понятия выпуклой оболочки . Его можно вычислить за линейное время , быстрее, чем алгоритмы для выпуклых оболочек наборов точек .
Выпуклую оболочку простого многоугольника можно разделить на сам данный многоугольник и на многоугольные карманы , ограниченные ломаной цепочкой многоугольника вместе с одним ребром выпуклой оболочки. Многократное отражение произвольно выбранного кармана через этот выпуклый край оболочки создает последовательность более крупных простых многоугольников; согласно теореме Эрдеша-Надя , этот процесс в конечном итоге заканчивается выпуклым многоугольником.
Структура
[ редактировать ]Выпуклая оболочка простого многоугольника сама по себе является выпуклым многоугольником . Наложение исходного простого многоугольника на его выпуклую оболочку разбивает этот выпуклый многоугольник на области, одна из которых является исходным многоугольником. Остальные регионы называются карманами . Каждый карман сам по себе является простым многоугольником, ограниченным полигональной цепочкой на границе данного простого многоугольника и одним краем выпуклой оболочки. У уже выпуклого многоугольника карманов нет. [1]
Можно сформировать иерархическое описание любого заданного многоугольника, построив таким образом его оболочку и карманы, а затем рекурсивно сформировав однотипную иерархию для каждого кармана. [1] Эту структуру, называемую выпуклым деревом разностей , можно эффективно построить. [2]
Алгоритмы
[ редактировать ]Нахождение выпуклой оболочки простого многоугольника можно выполнить за линейное время . Несколько ранних публикаций по этой проблеме оказались неверными, часто потому, что они приводили к промежуточным состояниям с пересечениями, приводившими к их разрушению. Первый правильный алгоритм с линейным временем для этой задачи был предложен МакКаллумом и Ависом (1979) . [3] Даже после его публикации продолжали публиковаться другие неверные алгоритмы. [4] Brönnimann & Chan (2006) пишут, что большинство опубликованных алгоритмов решения этой проблемы неверны. [5] хотя в более поздней истории, собранной Грегом Алуписом, только семь из пятнадцати алгоритмов указаны как неправильные. [6]
Особенно простой алгоритм решения этой задачи был опубликован Грэмом и Яо (1983) и Ли (1983) . Как и алгоритм сканирования Грэма для выпуклых оболочек наборов точек, он основан на стековой структуре данных . Алгоритм обходит многоугольник по часовой стрелке, начиная с вершины, которая, как известно, находится на выпуклой оболочке (например, ее крайней левой точки). При этом он сохраняет в стеке выпуклую последовательность вершин, тех, которые еще не были идентифицированы как находящиеся внутри карманов. Точки в этой последовательности — это вершины выпуклого многоугольника (не обязательно оболочка всех вершин, замеченных до сих пор), к некоторым из его краев могут быть прикреплены карманы. На каждом шаге алгоритм следует по пути вдоль многоугольника от вершины стека до следующей вершины, которая не находится ни в одном из двух карманов, соседних с вершиной стека. Затем, хотя две верхние вершины стека вместе с этой новой вершиной не находятся в выпуклом положении, он извлекает стек, прежде чем окончательно поместить новую вершину в стек. Когда обход по часовой стрелке достигает начальной точки, алгоритм завершается, и стек содержит вершины выпуклой оболочки в порядке по часовой стрелке. На каждом этапе алгоритма вершина либо помещается в стек, либо извлекается из стека, причем каждая вершина помещается и извлекается не более одного раза, поэтому общее время работы алгоритма является линейным. [7] [8] Если входные вершины заданы в массиве по часовой стрелке, то выходные данные можно вернуть в том же массиве, используя только постоянное количество дополнительных переменных в качестве промежуточного хранилища. [5]
Подобный метод можно использовать и для построения выпуклых оболочек кусочно-гладких замкнутых кривых на плоскости. [9] Используя дек вместо стека, аналогичный алгоритм можно обобщить на выпуклую оболочку любой многоугольной цепи, а алгоритм для простых многоугольников можно запустить в любой вершине многоугольника, вместо того, чтобы требовать крайнюю вершину в качестве начальной вершины. . [10]
Откидные карманы
[ редактировать ]Переворот . кармана создает новый многоугольник из заданного путем отражения многоугольной цепи, ограничивающей карман, через выпуклый край оболочки кармана При каждом перевороте создается еще один простой многоугольник с равным периметром и большей площадью, хотя несколько одновременных переворотов могут привести к появлению пересечений. Если перевернуть произвольно выбранный карман и затем повторить этот процесс с карманами каждого последовательно сформированного многоугольника, получится последовательность простых многоугольников. Согласно теореме Эрдеша-Надя , этот процесс переворачивания в конечном итоге завершается, достигая выпуклого многоугольника. Как и проблема построения выпуклой оболочки, эта проблема имеет долгую историю неверных доказательств. [11]
Ссылки
[ редактировать ]- ^ Jump up to: а б Тор, СБ; Миддлдич, AE (1984), «Выпуклое разложение простых многоугольников», ACM Transactions on Graphics , 3 (4): 244–265, doi : 10.1145/357346.357348
- ^ Раппопорт, Ари (1992), «Эффективный адаптивный алгоритм построения дерева выпуклых разностей простого многоугольника», Computer Graphics Forum , 11 (4): 235–240, doi : 10.1111/1467-8659.1140235 , S2CID 20137707
- ^ МакКаллум, Дункан; Авис, Дэвид (1979), «Линейный алгоритм поиска выпуклой оболочки простого многоугольника», Information Processing Letters , 9 (5): 201–206, doi : 10.1016/0020-0190(79)90069-3 , MR 0552534
- ^ Туссен, Годфрид (1991), «Контрпример к алгоритму выпуклой оболочки для многоугольников», Распознавание образов , 24 (2): 183–184, Бибкод : 1991PatRe..24..183T , doi : 10.1016/0031-3203 (91)90087-Л , МР 1087740
- ^ Jump up to: а б Брённиманн, Эрве; Чан, Тимоти М. (2006), «Эффективные с точки зрения использования пространства алгоритмы для вычисления выпуклой оболочки простой ломаной за линейное время», Computational Geometry , 34 (2): 75–82, doi : 10.1016/j.comgeo.2005.11 .005 , МР 2222883
- ^ Алупис, Грег, История алгоритмов выпуклой оболочки, работающих в линейном времени для простых многоугольников , Университет Макгилла , получено 1 января 2020 г.
- ^ Грэм, Рональд Л .; Яо, Ф. Фрэнсис (1983), «Нахождение выпуклой оболочки простого многоугольника», Journal of Algorithms , 4 (4): 324–331, doi : 10.1016/0196-6774(83)90013-5 , MR 0729228
- ^ Ли, Д.Т. (1983), «О поиске выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук , 12 (2): 87–98, doi : 10.1007/BF00993195 , MR 0724699 , S2CID 28600832
- ^ Шеффер, Алехандро А.; Ван Вик, Кристофер Дж. (1987), «Выпуклые оболочки кусочно-гладких жордановых кривых», Журнал алгоритмов , 8 (1): 66–94, doi : 10.1016/0196-6774(87)90028-9 , MR 0875326
- ^ Мелькман, Авраам А. (1987), «Онлайн-построение выпуклой оболочки простой ломаной», Information Processing Letters , 25 (1): 11–12, doi : 10.1016/0020-0190(87)90086-X , МР 0896397
- ^ Демейн, Эрик Д .; Гассенд, Блез; О'Рурк, Джозеф ; Туссен, Годфрид Т. (2008), «Все многоугольники переворачиваются конечно ... верно?», Обзоры по дискретной и вычислительной геометрии , Современная математика, том. 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 231–255, doi : 10.1090/conm/453/08801 , MR 2405683