В геометрии , А прямой скелет представляет собой метод , представляющие собой многоугольник с помощью топологического скелета . Она в некотором роде похожа на среднюю ось, но отличается тем, что каркас состоит из отрезков прямых линий, в то время как средняя ось многоугольника может включать параболические кривые. Однако оба они гомотопически эквивалентны лежащему в основе многоугольнику. [1]
Прямые скелеты были впервые определены для простых многоугольников Aichholzer et al. (1995) , [2] и обобщены на планарные прямолинейные графы (PSLG) Айхольцером и Ауренхаммером (1996) . [3] В их интерпретации как проекции поверхностей крыши они уже широко обсуждались Г. А. Пешкой ( 1877 ). [4]
Определение
Прямой каркас многоугольника определяется непрерывным процессом сжатия, в котором края многоугольника перемещаются внутрь параллельно себе с постоянной скоростью. Когда ребра движутся таким образом, вершины, в которых встречаются пары ребер, также перемещаются со скоростью, которая зависит от угла вершины. Если одна из этих движущихся вершин сталкивается с несмежным ребром, многоугольник разделяется на две части в результате столкновения, и процесс продолжается в каждой части. Прямой каркас - это набор кривых, очерченных движущимися вершинами в этом процессе. На рисунке верхний рисунок показывает процесс усадки, а средний рисунок изображает прямой каркас синим цветом.
Алгоритмы
Прямой каркас можно рассчитать путем моделирования процесса усадки, которым он определяется; был предложен ряд вариантов алгоритмов его вычисления, различающихся предположениями, которые они делают на входе, и структурами данных, которые они используют для обнаружения комбинаторных изменений во входном многоугольнике по мере его сжатия.
Следующие алгоритмы рассматривают входные данные, образующие многоугольник, многоугольник с отверстиями или PSLG. Для многоугольного входа мы обозначаем количество вершин через n, а количество рефлекторных (вогнутых, т. Е. С углом больше π ) вершин через r . Если входом является PSLG, то мы рассматриваем исходную структуру волнового фронта, которая формирует набор многоугольников, и снова обозначаем n количество вершин и r количество рефлекторных вершин относительно направления распространения.
- Aichholzer et al. [2] [3] показали, как вычислить прямые скелеты PSLG за время O ( n 3 log n ), точнее за время O (( n 2 + f ) log n ), где n - количество вершин входного polygon, а f - количество событий переворота во время строительства. Самая известная оценка для f - O ( n 3 ).
- Алгоритм с наихудшим временем выполнения в O ( nr log n), или просто O ( n 2 log n), представлен Хубером и Хельдом ( 2010 , 2011 ), которые утверждают, что их подход, вероятно, будет работать почти в два раза. линейное время для многих входов. [5] [6]
- Петр Фелкель и Штепан Обдржалек разработали алгоритм для простых многоугольников, который, как говорят, имеет эффективность O ( nr + n log r ). [7] [8] Однако было показано, что их алгоритм неверен. [9] [10]
- Используя структуры данных для задачи бихроматической ближайшей пары , Эппштейн и Эриксон показали, как построить задачи с прямым скелетом, используя линейное число обновлений структуры данных ближайшей пары. Ближайшая парная структура данных на основе квадродеревьев обеспечивает алгоритм времени O ( nr + n log n ), или значительно более сложная структура данных приводит к лучшей асимптотической временной границе O ( n 1 + ε + n 8/11 + ε r 9 / 11 + ε ) или, проще говоря, O ( n 17/11 + ε ) , где ε - любая константа больше нуля. [11] Это остается наилучшей временной границей для наихудшего случая, известной для построения прямого каркаса с неограниченными входами, но он сложен и не был реализован.
- Для простых многоугольников задача построения прямого каркаса проще. Ченг и Виньерон показали, как вычислить прямой скелет простых многоугольников за время O ( n log 2 n + r 3/2 log r ). [12] В худшем случае r может быть порядка n , и в этом случае эта временная граница может быть упрощена до O ( n 3/2 log n ).
- Монотонный многоугольник относительно линии L представляет собой многоугольник с тем свойством , что каждая линия ортогональна L пересекает многоугольник в одном интервале. Когда вход представляет собой монотонный многоугольник, его прямой скелет может быть построен за время O ( n log n ). [13]
Приложения
Каждую точку во входном многоугольнике можно поднять в трехмерное пространство, используя время, в которое процесс сжатия достигает этой точки, в качестве координаты z точки. Полученная трехмерная поверхность имеет постоянную высоту на краях многоугольника и поднимается с них с постоянным наклоном, за исключением точек самого прямого каркаса, где встречаются участки поверхности под разными углами. Таким образом, прямой каркас можно использовать как набор коньковых линий крыши здания, основанный на стенах в виде исходного многоугольника. [2] [14] На нижнем рисунке изображена поверхность, образованная таким образом из прямого каркаса.
Демейн, Демейн и Любив использовали прямой скелет как часть техники складывания листа бумаги так, чтобы данный многоугольник можно было вырезать из него одним прямым разрезом ( теорема о сгибании и разрезании ), и связанных с этим проблем проектирования оригами. . [15]
Barequet et al. использовать прямые скелеты в алгоритме поиска трехмерной поверхности, которая интерполируется между двумя заданными многоугольными цепями . [16]
Тэнасе и Велткамп предлагают разложить вогнутые многоугольники на объединение выпуклых областей с использованием прямых каркасов в качестве этапа предварительной обработки для согласования формы при обработке изображений. [17]
Багери и Раззази используют прямые скелеты для направления размещения вершин в алгоритме рисования графа , в котором рисунок графа ограничен, чтобы лежать внутри многоугольной границы. [18]
Прямой каркас также можно использовать для построения кривой смещения многоугольника со скошенными углами , аналогично построению кривой смещения с закругленными углами, образованными от средней оси. Томоэда и Сугихара применяют эту идею в дизайне вывесок, видимых под широким углом, с иллюзорной глубиной. [19] Точно так же Асенте и Карр используют прямые скелеты для создания цветовых градиентов, которые соответствуют контурам букв или другим формам. [20]
Как и в случае с другими типами каркаса, такими как средняя ось , прямой каркас можно использовать для сжатия двумерной области до упрощенного одномерного представления области. Например, Хаунерт и Сестер описывают применение этого типа для прямых каркасов в географических информационных системах при поиске осевых линий дорог. [21] [22]
Любое дерево без двух степеней вершин может быть реализовано как прямой каркас выпуклого многоугольника . [23] выпуклая оболочка формы крыши , соответствующей этой прямой скелет , образует реализацию Штейница из графа Halin , образованного из дерева, соединяя его листья в цикле.
Высшие измерения
Barequet et al. определил версию прямых скелетов для трехмерных многогранников , описал алгоритмы ее вычисления и проанализировал ее сложность на нескольких различных типах многогранников. [24]
Huber et al. исследовали метрические пространства, при которых совпадают соответствующие диаграммы Вороного и прямые скелеты. Для двух измерений характеристика таких метрических пространств завершена. Для более высоких измерений этот метод можно интерпретировать как обобщение прямых скелетов определенных входных форм до произвольных размеров с помощью диаграмм Вороного. [25]
Рекомендации
- ^ Хубер, Стефан (2018), «Топология скелетов и смещений» (PDF) , Труды 34-го Европейского семинара по вычислительной геометрии (EuroCG'18).
- ^ а б в Айхольцер, Освин; Ауренхаммер, Франц ; Альбертс, Дэвид; Гертнер, Бернд (1995), "Новый тип каркаса для полигонов" , журнал Юниверсал Computer Science , 1 (12): 752-761, DOI : 10.1007 / 978-3-642-80350-5_65 , MR 1392429.
- ^ а б Айхольцер, Освин; Ауренхаммер, Франц (1996), "Прямые скелеты для общих многоугольных фигур на плоскости" , Proc. 2nd Ann. Int. Конф. Computing and Combinatorics (COCOON '96) , Lecture Notes in Computer Science, 1090 , Springer-Verlag, pp. 117–126.
- ^ Пешка, Густав А. (1877), Котирте Эбенен: Kotirte Projektionen und deren Anwendung; Vorträge , Brünn: Buschak & Irrgang, doi : 10.14463 / GBV: 865177619.
- ^ Хубер, Стефан; Хелд, Мартин (2010), «Вычисление прямых скелетов плоских прямолинейных графов на основе мотоциклетных графов» (PDF) , Труды 22-й Канадской конференции по вычислительной геометрии.
- ^ Хубер, Стефан; Хелд, Мартин (2011), «Теоретические и практические результаты о прямых каркасах плоских прямолинейных графов» (PDF) , Труды двадцать седьмого ежегодного симпозиума по вычислительной геометрии (SCG'11), 13–15 июня 2011 г., Париж, Франция , стр. 171–178..
- ^ "CenterLineReplacer" , FME Transformers , Safe Software , получено 5 августа 2013 г..
- ^ Фелькель, Петр; Обдржалек, Штепан (1998), «Реализация прямого каркаса», SCCG 98: Материалы 14-й весенней конференции по компьютерной графике , стр. 210–218..
- ^ Хубер, Стефан (2012), Вычисление прямых скелетов и графиков мотоциклов: теория и практика , Shaker Verlag, ISBN 978-3-8440-0938-5.
- ^ Якерсберг, Евгений (2004), Морфинг между геометрическими формами с использованием интерполяции на основе прямого скелета. , Израильский технологический институт.
- ^ Эпштейн, Дэвид ; Эриксон, Джефф (1999), «Подъем крыш, циклы сбоев и игровой пул: приложения структуры данных для поиска парных взаимодействий» (PDF) , Дискретная и вычислительная геометрия , 22 (4): 569–592, DOI : 10.1007 / PL00009479 , Руководство по ремонту 1721026.
- ^ Ченг, Сиу-Винг; Виньерон, Антуан (2002), «Графики мотоциклов и прямые скелеты» (PDF) , Труды 13-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 156–165.
- ^ Бидль, Тереза ; Хелд, Мартин; Хубер, Стефан; Каасер, Доминик; Пальфрейдер, Питер (февраль 2015 г.). «Простой алгоритм для вычисления положительно взвешенных прямых скелетов монотонных многоугольников» (PDF) . Письма об обработке информации . 115 (2): 243–247. DOI : 10.1016 / j.ipl.2014.09.021 .Как Biedl et al. Отметим, что более ранний алгоритм для монотонных многоугольников, разработанный Das et al. неверно, как описано, и в лучшем случае работает только для входов в общем положении, которые не имеют событий вершина-вершина: Das, Gautam K .; Мухопадхьяй, Асиш; Nandy, Subhas C .; Патил, Сангамесвар; Рао, С.В. (2010), «Вычисление прямых скелетов монотонного многоугольника за время O ( n log n )» (PDF) , Труды 22-й Канадской конференции по вычислительной геометрии.
- ^ Беланже, Дэвид (2000), Проектирование крыш зданий.
- ^ Демейн, Эрик Д .; Демейн, Мартин Л .; Любив, Анна (1998), «Складывание и резка бумаги» , Пересмотренные документы Японской конференции по дискретной и вычислительной геометрии (JCDCG'98) , Конспекты лекций по информатике, 1763 , Springer-Verlag, стр. 104–117, doi : 10.1007 / b75044.
- ^ Барекет, Гилл; Гудрич, Майкл Т .; Леви-Штайнер, Айя; Штайнер, Двир (2003), "Контурная интерполяция на основе прямого каркаса" , Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 119–127.
- ^ Тэнасе, Мирела; Велткамп, Ремко К. (2003), «Разложение многоугольника на основе скелета прямой линии», Труды 19-го ежегодного симпозиума ACM по вычислительной геометрии , стр. 58–67, doi : 10.1145 / 777792.777802.
- ^ Багери, Алиреза; Razzazi, Mohammadreza (2004), «Рисование свободных деревьев внутри простых многоугольников с использованием многоугольного каркаса», Computing and Informatics , 23 (3): 239–254, MR 2165282.
- ^ Томоэда, Акиясу; Сугихара, Кокичи (2012), «Вычислительное создание нового иллюзорного твердого знака», Девятый международный симпозиум по диаграммам Вороного в науке и технике (ISVD 2012) , стр. 144–147, doi : 10.1109 / ISVD.2012.26.
- ^ Асенте, Пол; Карр, Натан (2013), «Создание контурных градиентов с использованием трехмерных скосов», Труды симпозиума по вычислительной эстетике (CAE '13, Анахайм, Калифорния) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 63–66, doi : 10.1145 / 2487276.2487283 , ISBN 978-1-4503-2203-4.
- ^ Хаунерт, Ян-Хенрик; Сестер, Моника (2008), "Площадь обрушения и дорожные Осевые , основанные на прямых скелетов", Геоинформатика , 12 (2): 169-191, DOI : 10.1007 / s10707-007-0028-х.
- ^ Роли, Дэвид Бэринг (2008 г.), Корректировка осевых линий дороги с помощью прямого каркаса на основе грубых данных GPS: пример из Боливии , Университет штата Огайо, Геодезические науки и геодезия.
- ^ Айхольцер, Освин; Ченг, Ховард; Devadoss, Satyan L .; Хакл, Томас; Хубер, Стефан; Ли, Брайан; Ристески, Андрей (2012), "Что делает дерево прямым скелетом?" (PDF) , Материалы 24-й Канадской конференции по вычислительной геометрии (CCCG'12).
- ^ Барекет, Гилл; Эпштейн, Дэвид ; Гудрич, Майкл Т .; Ваксман, Амир (2008), "Прямые скелеты трехмерных многогранников", Proc. 16-й Европейский симпозиум по алгоритмам , конспект лекций по информатике, 5193 , Springer-Verlag, стр. 148–160, arXiv : 0805.0022 , doi : 10.1007 / 978-3-540-87744-8_13.
- ^ Хубер, Стефан; Айхольцер, Освин; Хакл, Томас; Фогтенхубер, Биргит (2014), "Прямые скелеты с помощью диаграмм Вороного при многогранных функциях расстояния" (PDF) , Proc. 26-я Канадская конференция по вычислительной геометрии (CCCG'14).
Внешние ссылки
- Эриксон, Джефф. «Прямой каркас простого многоугольника» .
- 2D прямой скелет в CGAL , библиотеке алгоритмов вычислительной геометрии
- Прямой скелет для многоугольника с отверстиями Конструктор прямого скелета реализован на java.
- Амит Парнеркар, Сарнатх Рамнатх. «Разработка эффективного алгоритма для поиска прямого скелета простого многоугольника за O (n log n) » .