Прямолинейный скелет

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

Прямолинейный скелет — это метод представления многоугольника его топологическим скелетом. Прямолинейный скелет подобен в некотором роде срединным осям, но отличается тем, что скелет состоит из отрезков, в то время как срединные оси многоугольника могут включать параболические кривые.

Прямолинейные скелеты впервые определили для простых многоугольников Айхгольцер, Ауренхаммер, Альбертс и Гэртнер[1] и обобщили до планарных прямолинейных графов[англ.] Айхгольцер и Ауренхаммер[2]. В интерпретации прямолинейных скелетов как проекции поверхности крыш их интенсивно обсуждал Г. А. Пешка[3].

Определение

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

Алгоритмы

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

  • Айхгольцер и др.[1][2] показали, каким образом можно вычислить прямолинейные скелеты для произвольных двумерных многоугольников за время O(n3 log n), или, более точно, за время O((n2+f) log n), где n — число вершин входного многоугольника, а f — число событий перевёртывания во время построения. Лучшая известная оценка для f — O(n3).
  • Алгоритм со временем работы в наихудшем случае O(nr log n), или просто O(n2 log n), дали Хубер и Хелд, и они утверждают, что их алгоритм работает практически за линейное время для большинства исходных данных[4][5].
  • Пётр Фелькель и Степан Обдржалек разработали алгоритм, который, по их словам, имеет эффективность O(nr + n log r)[6][7]. Однако поступали сообщения, что их алгоритм неверен[8][9].
  • Используя структуру данных для задачи о ближайшей паре точек двух цветов, Эппштейн[англ.] и Эриксон показали, каким образом построить прямолинейные скелеты при помощи линейного числа обновлений структуры данных ближайших пар точек. Структура данных ближайших пар точек, основанная на дереве квадрантов, даёт алгоритм со временем работы O(nr + n log n), а существенно более сложная структура данных приводит к лучшей асимптотической границе времени работы O(n1 + ε + n8/11 + εr9/11 + ε), или, проще, O(n17/11 + ε), где ε — любая константа, большая нуля[10]. Это остаётся лучшей (для худшего случая) границей времени работы для построения прямолинейного скелета без ограничений входных данных, но алгоритм сложен и имплементирован не был.
  • Для простых многоугольников задача построения прямолинейного скелета проще. Ченг и Вингерон показали, каким образом вычислить прямолинейный скелет простого многоугольника с n вершинами, из которых r имеют углы, большие , за время O(n log2 n + r3/2 log r)[11]. В худшем случае r может быть линейно и время работы упрощается до O(n3/2 log n).
  • Монотонный многоугольник[англ.] по отношению к прямой L — это многоугольник со свойством, что пересечение любой ортогональной L прямой с многоугольником представляет собой один отрезок. Если на вход принимается монотонный многоугольник, его прямолинейный скелет можно построить за время O(n log n)[12].

Приложения

Каждая точка внутри входного многоугольника может быть поднята (z-координата точки) в трёхмерном пространстве на время, за которое в процессе сокращения достигается эта точка. Получающаяся трёхмерная поверхность имеет постоянную высоту на сторонах многоугольника и поднимается под постоянным углом от них, за исключением точек самого прямолинейного скелета, где части поверхности встречаются под разными углами. Таким образом, прямолинейный скелет можно использовать как набор хребтов крыши здания, опирающейся на стены в форме начального многоугольника[1][13]. Нижняя фигура на иллюстрации показывает поверхность, полученную таким образом из прямолинейного скелета.

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

Баркет и др. использовали прямолинейные скелеты в алгоритме поиска трёхмерной поверхности, являющейся интерполяцией двух заданных ломаных[15].

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

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

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

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

Любое дерево без вершин степени два можно реализовать как прямолинейный скелет выпуклого многоугольника[22]. Выпуклая оболочка крыши, соответствующей этому прямолинейному скелету, образует реализацию Штайница графа Халина, образованного из дерева путём соединения его листьев в цикл.

Более высокие размерности

Баркет, Эппштейн, Гуудрих и Ваксман определили версию прямолинейных скелетов для трёхмерных многогранников, описали алгоритм для их вычисления и проанализировали сложность алгоритма на нескольких типах многоугольников[23].

Хубер, Айхгольцер, Хакл и Фогтенхубер исследовали метрические пространства, в которых соответствующие диаграммы Вороного и прямолинейные скелеты совпадают. Для двумерных пространств существует полное описание таких метрик. Для более высоких размерностей этот метод можно понимать как обобщение прямолинейных скелетов на некоторые формы объектов в произвольной размерности с помощью диаграмм Вороного[24].

Примечания

  1. ↑ 1 2 3 Aichholzer, Aurenhammer, Alberts, Gärtner, 1995, с. 752–761.
  2. ↑ 1 2 Aichholzer, Aurenhammer, 1996, с. 117–126.
  3. ↑ Peschka, 1877.
  4. ↑ Huber, Held, 2010.
  5. ↑ Huber, Held, 2011, с. 171–178.
  6. ↑ FME (Felkel, Obdržálek).
  7. ↑ Felkel, Obdržálek, 1998, с. 210–218.
  8. ↑ Huber, 2012.
  9. ↑ Yakersberg, 2004.
  10. ↑ Eppstein, Erickson, 1999, с. 569–592.
  11. ↑ Cheng, Vigneron, 2002, с. 156–165.
  12. ↑ (Biedl, Held, Huber, Kaaser, Palfrader 2015). Как заметил Бидл с соавторами, алгоритм, который ранее опубликовал Дас с соавторами, не является корректным в том виде, в каком он описан, и работает хорошо только для входных данных в общем положении, когда не возникает событий вершина-вершина (Das, Mukhopadhyay, Nandy, Patil, Rao 2010)
  13. ↑ David Bélanger.
  14. ↑ Demaine, Demaine, Lubiw, 1998, с. 104–117.
  15. ↑ Barequet, Goodrich, Levi-Steiner, Steiner, 2003, с. 119–127.
  16. ↑ Tănase, Veltkamp, 2003, с. 58–67.
  17. ↑ Bagheri, Razzazi, 2004, с. 239–254.
  18. ↑ Tomoeda, Sugihara, 2012, с. 144–147.
  19. ↑ Asente, Carr, 2013, с. 63–66.
  20. ↑ Haunert, Sester, 2008, с. 169–191.
  21. ↑ David Raleigh, 2008.
  22. ↑ Aichholzer, Cheng, Devadoss, Hackl, Huber, Li, Risteski, 2012.
  23. ↑ Barequet, Eppstein, Goodrich, Vaxman, 2008, с. 148–160.
  24. ↑ Huber, Aichholzer, Hackl, Vogtenhuber, 2014.

Литература

  • Oswin Aichholzer, Franz Aurenhammer, David Alberts, Bernd Gärtner. A novel type of skeleton for polygons // Journal of Universal Computer Science. — 1995. — Т. 1, вып. 12. — С. 752—761. — doi:10.1007/978-3-642-80350-5_65.
  • Oswin Aichholzer, Franz Aurenhammer. Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96). — Springer-Verlag, 1996. — Т. 1090. — С. 117—126. — (Lecture Notes in Computer Science).
  • Gustav A. Peschka. Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge. — Brno: Buschak & Irrgang, 1877.
  • Stefan Huber, Martin Held. Proceedings of the 22nd Canadian Conference on Computational Geometry. — 2010.
  • Stefan Huber, Martin Held. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. — 2011. — С. 171—178.
  • Petr Felkel, Štěpán Obdržálek. FME Transformers. CenterLineReplacer. Safe Software. Дата обращения: 9 марта 2017.
  • Petr Felkel, Štěpán Obdržálek. SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics. — 1998. — С. 210—218.
  • Stefan Huber. Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice. — Shaker Verlag, 2012. — ISBN 978-3-8440-0938-5.
  • Evgeny Yakersberg. Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation. — Israel Institute of Technology, 2004.
  • David Eppstein, Jeff Erickson. Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions // Discrete and Computational Geometry. — 1999. — Т. 22, вып. 4. — С. 569—592. — doi:10.1007/PL00009479.
  • Siu-Wing Cheng, Antoine Vigneron. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. — 2002. — С. 156—165.
  • Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader. A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons // Information Processing Letters. — 2015. — Т. 115, вып. 2. — С. 243—247. — doi:10.1016/j.ipl.2014.09.021.
  • Gautam K. Das, Asish Mukhopadhyay, Subhas C. Nandy, Sangameswar Patil, S. V. Rao. Proceedings of the 22nd Canadian Conference on Computational Geometry. — 2010.
  • David Bélanger. Designing Roofs of Buildings. Дата обращения: 8 марта 2017. Архивировано из оригинала 21 января 2012 года.
  • Erik Demaine, Martin Demaine, Anna Lubiw. Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98). — Springer-Verlag, 1998. — Т. 1763. — С. 104—117. — doi:10.1007/b75044.
  • Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, Dvir Steiner. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2003. — С. 119—127.
  • Mirela Tănase, Remco C. Veltkamp. Proceedings of the 19th Annual ACM Symposium on Computational Geometry. — 2003. — С. 58—67. — doi:10.1145/777792.777802.
  • Alireza Bagheri, Mohammadreza Razzazi. Drawing free trees inside simple polygons using polygon skeleton // Computing and Informatics. — 2004. — Т. 23, вып. 3. — С. 239—254.
  • Akiyasu Tomoeda, Kokichi Sugihara. Ninth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012). — 2012. — С. 144—147. — doi:10.1109/ISVD.2012.26.
  • Paul Asente, Nathan Carr. Proceedings of the Symposium on Computational Aesthetics (CAE '13, Anaheim, California). — New York, NY, USA: ACM, 2013. — С. 63—66. — ISBN 978-1-4503-2203-4. — doi:10.1145/2487276.2487283.
  • Jan-Henrik Haunert, Monika Sester. Area collapse and road centerlines based on straight skeletons // Geoinformatica. — 2008. — Т. 12, вып. 2. — С. 169—191. — doi:10.1007/s10707-007-0028-x.
  • David Baring Raleigh. Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia. — Ohio State University, Geodetic Science and Surveying, 2008.

Oswin Aichholzer, Howard Cheng, Satyan L. Devadoss, Thomas Hackl, Stefan Huber, Brian Li, Andrej Risteski. Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12). — 2012.Gill Barequet, David Eppstein, Michael T. Goodrich, Amir Vaxman. Proc. 16th European Symposium on Algorithms. — Springer-Verlag, 2008. — Т. 5193. — С. 148—160. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-87744-8_13.

Stefan Huber, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber. Proc. 26th Canadian Conference on Computational Geometry (CCCG'14). — 2014.

Ссылки