Прямий кістяк: відмінності між версіями
| [перевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
Tolsai (обговорення | внесок) Функція пропозицій посилань: додано 3 посилання. |
||
Рядок 17:
== Використання ==
Кожна точка всередині вхідного многокутника може бути піднята у тривимірний простір з використанням того часу, за який процес стиснення досягає цієї точки, як координату z. В результаті, тривимірна площина має постійну висоту на границі многокутника, та піднімається з постійним кутом по відношенню до них, крім точок самого прямого кістяка, де частини площини з'єднуються під різними кутами. Таким чином, прямий кістяк може бути використаний як [[множина]] ребер для будівництва даху, розміщений на стінах у формі початкового многокутника.<ref name=":0" /><ref>{{Cite book|url=http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html|title=Designing Roofs of Buildings|last=Bélanger|first=David|year=2000|publisher=|location=|pages=|language=Англійською|isbn=|accessdate=28 травня 2017|archiveurl=https://web.archive.org/web/20120121022927/http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html|archivedate=21 січня 2012|deadurl=yes}}</ref> Найнижча фігура на ілюстрації показує площину, побудовану з прямого кістяка цим способом.
Демаін та Лубів використовували прямий кістяк як частину техніки для складання листа паперу таким чином, що даний многокутник може бути розрізаний одним прямим розрізом ([[теорема оригамі про вирізання многокутника]]), та пов'язана з проблемами проектування [[оригамі]].<ref>{{Cite book|url=http://link.springer.com/10.1007/b75044|title=Discrete and Computational Geometry {{!}} SpringerLink|language=en-gb|doi=10.1007/b75044}}</ref>
Рядок 23:
Бареквет, використовує прямий кістяк в алгоритмі для знаходження тривимірної площини, що інтерполює між двома даними [[Ламана|ламаними]].<ref>{{Cite book|title=Straight-skeleton based contour interpolation|last=Barequet|first=Gill|last2=Goodrich, Michael T|last3=Levi-Steiner, Aya|last4=Steiner, Dvir|year=2003|publisher=|location=Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms|pages=119–127|language=Англійською|isbn=}}</ref>
Танас та Велткамп пропонують розкласти неопуклі многокутники на об'єднання опуклих зон, використовуючи прямий кістяк, при зіставленні форм у [[Обробка зображень|обробці зображень]] як крок попередньої обробки.<ref>{{Cite news|url=http://doi.acm.org/10.1145/777792.777802|title=Polygon Decomposition Based on the Straight Line Skeleton|last=Tanase|first=Mirela|last2=Veltkamp|first2=Remco C.|date=2003|publisher=ACM|pages=58–67|work=Proceedings of the Nineteenth Annual Symposium on Computational Geometry|doi=10.1145/777792.777802|isbn=1581136633|accessdate=2017-05-28}}</ref>
Баджері та Раззарі використовують прямий кістяк, щоб показати укладку вершин у алгоритмі [[Візуалізація графів|візуалізації графу]], де малюнок графу обмежений границею многокутника.<ref>{{Cite book|title=Drawing free trees inside simple polygons using polygon skeleton|last=Bagheri|first=Alireza|last2=Razzazi|first2=Mohammadreza|year=2004|publisher=|location=|pages=239–254|language=|isbn=|mr=2165282}}</ref>
Рядок 31:
Разом з іншими типами кістяків, таких як медіальна вісь, прямий кістяк може бути використаний для згортання двомірної області до спрощеного одномірного представлення. Наприклад, Ганерт та Сестер описують використання цього типа прямого кістяка в [[Геоінформаційна система|географічних інформаційних системах]] для знаходження осьових ліній доріг.<ref>{{Cite news|url=https://link.springer.com/article/10.1007/s10707-007-0028-x|title=Area Collapse and Road Centerlines based on Straight Skeletons|last=Haunert|first=Jan-Henrik|last2=Sester|first2=Monika|date=2008-06-01|pages=169–191|language=en|work=GeoInformatica|volume=12|doi=10.1007/s10707-007-0028-x|issn=1384-6175|issue=2|accessdate=2017-05-28}}</ref>
Кожне [[Дерево (теорія графів)|дерево]] без жодної вершини другої степені може бути реалізовано як прямий кістяк [[Опуклий многокутник|опуклого многокутника]].<ref>{{Cite book|url=http://2012.cccg.ca/papers/paper30.pdf|title=What makes a tree a straight skeleton?|last=Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej|first=|year=2012|publisher=Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)|location=|pages=|language=|isbn=}}</ref> [[Опукла оболонка]] площини даху співвідноситься з його прямим кістяком, формуючи [[Теорема Штайніца|реалізацію Штайніца]] [[Граф Халіна|графу Халіна]], сформований з дерева приєднанням його листків у циклі.
== Більші виміри ==
| |||