Прямой каркас - Straight skeleton

Процесс усадки, прямой каркас (синий) и модель крыши.

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

Прямые скелеты были впервые определены для простых многоугольников Aichholzer et al. (1995),[2] и обобщены на планарные прямолинейные графики (PSLG) автор: Айхольцер и Ауренхаммер (1996).[3]В их интерпретации как проекции поверхностей кровли они уже широко обсуждались Г. А. Пешкой (1877 ).[4]

Определение

Прямой каркас многоугольника определяется непрерывным процессом сжатия, в котором края многоугольника перемещаются внутрь параллельно себе с постоянной скоростью. Когда ребра движутся таким образом, вершины, в которых встречаются пары ребер, также перемещаются со скоростью, зависящей от угла вершины. Если одна из этих движущихся вершин сталкивается с несмежным ребром, многоугольник разделяется на две части в результате столкновения, и процесс продолжается в каждой части. Прямой скелет - это набор кривых, очерченных движущимися вершинами в этом процессе. На рисунке верхний рисунок показывает процесс сжатия, а средний рисунок изображает прямой скелет синим цветом.

Алгоритмы

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

Следующие алгоритмы рассматривают входные данные, образующие многоугольник, многоугольник с отверстиями или PSLG. Для многоугольного входа обозначим количество вершин через п и количество рефлексов (вогнутых, т. е. угол больше π) вершины р. Если входом является PSLG, то мы рассматриваем исходную структуру волнового фронта, которая образует набор многоугольников, и снова обозначаем через п количество вершин и на р количество рефлекторных вершин относительно направление распространения.

  • Aichholzer et al.[2][3] показал, как вычислить прямые скелеты ПСЛГ за время O (п3 бревноп), а точнее время O ((п2+ж) бревноп), куда п - количество вершин входного многоугольника и ж - количество событий переворота во время строительства. Самый известный маршрут для ж это O (п3).
  • Алгоритм с наихудшим временем работы в O (номер log n) или просто O (п2 log n), дается Хубером и Хельдом (2010, 2011 ), которые утверждают, что их подход, вероятно, будет работать почти за линейное время для многих входных данных.[5][6]
  • Петр Фелкель и Штепан Обдржалек разработали алгоритм для простых многоугольников, который, как говорят, имеет эффективность O (номер + п бревно р).[7][8] Однако было показано, что их алгоритм неверен.[9][10]
  • Используя структуры данных для бихроматическая задача о ближайшей паре, Эппштейн и Эриксон показал, как построить задачи с прямым скелетом, используя линейное число обновлений структуры данных ближайших пар. Структура данных ближайшей пары на основе квадродеревья дает O (номер + п бревноп) временного алгоритма, или значительно более сложная структура данных приводит к лучшей асимптотической временной границе O (п1 + ε + п8/11 + εр9/11 + ε), или проще O (п17/11 + ε), где ε - любая константа больше нуля.[11] Это остается наилучшей временной границей для наихудшего случая, известной для построения прямого каркаса с неограниченными входами, но он сложен и не реализован.
  • За простые многоугольники, задача построения прямого каркаса проще. Ченг и Виньерон показали, как вычислить прямой скелет простых многоугольников за время O (п бревно2 п + р3/2 бревно р).[12] В худшем случае р может быть в порядке п, и в этом случае эта временная граница может быть упрощена до O (п3/2 бревноп).
  • А монотонный многоугольник относительно линии L является многоугольником, каждая прямая, ортогональная L пересекает многоугольник за один интервал. Когда вход представляет собой монотонный многоугольник, его прямой скелет может быть построен за время O (п бревноп).[13]

Приложения

Каждую точку внутри входного многоугольника можно поднять в трехмерное пространство, используя время, в которое процесс сжатия достигает этой точки, в качестве координаты z точки. Полученная трехмерная поверхность имеет постоянную высоту на краях многоугольника и поднимается с постоянным наклоном от них, за исключением точек самого прямого каркаса, где встречаются участки поверхности под разными углами. Таким образом, прямой каркас может быть использован как набор коньковых линий крыши здания, основанный на стенах в виде исходного многоугольника.[2][14] Нижний рисунок на иллюстрации изображает поверхность, образованную таким образом из прямого каркаса.

Демейн, Демейн и Любив использовали прямой скелет как часть техники складывания листа бумаги так, чтобы данный многоугольник можно было вырезать из него одним прямым разрезом ( теорема о сложении и вырезании ) и связанные оригами проблемы дизайна.[15]

Barequet et al. использовать прямые скелеты в алгоритме поиска трехмерной поверхности, которая интерполируется между двумя заданными многоугольные цепи.[16]

Тэнасе и Вельткамп предлагают разложить вогнутые многоугольники в объединения выпуклых областей с использованием прямых скелетов в качестве этапа предварительной обработки для согласования формы при обработке изображений.[17]

Багери и Раззази используют прямые скелеты, чтобы направлять размещение вершин в рисунок графика алгоритм, в котором рисование графа ограничивается полигональной границей.[18]

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

Как и в случае с другими типами скелета, такими как медиальная ось, прямой каркас можно использовать для сжатия двумерной области до упрощенного одномерного представления области. Например, Хаунерт и Сестер описывают применение этого типа для прямых скелетов в географические информационные системы, в поиске осевых линий дорог.[21][22]

Каждый дерево без степень -две вершины могут быть реализованы как прямой каркас выпуклый многоугольник.[23] В выпуклый корпус формы крыши, соответствующей этому прямому каркасу, образует Реализация Стейница из График Халина формируется из дерева путем соединения его листьев в цикл.

Высшие измерения

Barequet et al. определил вариант прямых скелетов для трехмерных многогранники, описал алгоритмы его вычисления и проанализировал его сложность на нескольких различных типах многогранников.[24]

Huber et al. исследовал метрические пространства при котором соответствующие Диаграммы Вороного и прямые скелеты совпадают. Для двух измерений характеристика таких метрических пространств завершена. Для более высоких измерений этот метод можно интерпретировать как обобщение прямых скелетов определенных входных форм до произвольных размеров с помощью диаграмм Вороного.[25]

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

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

внешняя ссылка