Прямий кістяк

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

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

Перше визначення прямого кістяка для простих многокутників було розроблено в 1996 році[1] та узагальнено для планарних прямолінійних графів.[2] Інтерпретація задачі, як проекція поверхонь дахів, широко обговорювалась Ґ. А. Пешкою.[3]

Означення

Прямий кістяк многокутника визначається неперервним процесом усадки, в якому сторони многокутника рухаються всередину паралельно самим собі з постійною швидкістю. Через те, що сторони так рухаються, вершини, де пари ребер з'єднуються, також рухаються, але зі швидкістю, що залежить від кута цієї вершини. Якщо одна з цих вершин перетинається з несуміжним ребром, многокутник ділиться на дві частини цим перетином, та процес продовжується окремо для кожної частини. Креслення траєкторій руху вершин, при цьому процесі, утворює множину кривих, які і є прямим кістяком. На рисунку, найвища фігура показує процес усадки, а середня фігура зображує синім кольором прямий кістяк.

Алгоритми

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

  • Айшхользер[1][2] показав як вичислити прямий кістяк для довільного двомірного многокутника за час O(n3 log n)[4], або, більш точно, за час O((n2+f) log n), де n — кількість вершин, а f — число перетинів вершин із несуміжними сторонами під час будування. Найкраще відома оцінка для f — O(n3).
  • Алгоритм з найгіршим часом O(nr log n), або простіше O(n2 log n), був запропонований Губером та Гелдом, які аргументували, що їх підхід працюватиме майже за лінійний час для більшості випадків.[5][6]
  • Петр Фелькер та Степан Обджалек розробили алгоритм, що відомий оцінкою O(nr + n log r). Проте, відомо, що їх алгоритм є неправильним.[7][8]
  • Використовуючи структури для задачі найближчої пари точок, Епштейн та Еріксон показали, як побудувати прямий кістяк, використовуючи лінійне число оновлень структури даних задачі найближчої пари. Алгоритм структури найближчої пари базується на дереві квадрантів та передбачає оцінку часу O(nr + n log n), чи з істотно більш складною структурою даних, що забезпечує кращу оцінку асимптотики O(n1 + ε + n8/11 + εr9/11 + ε), де ε — будь-яка константа більша за нуль.[9] Цей алгоритм залишається найкращим за оцінкою для прямого кістяку без умов на вхідні дані, але він складний і ще не був реалізований.
  • Для простих многокутників, задача побудови прямого кістяка простіша. Ченґ на Віґнерон показали як вичислити прямий кістяк для простих многокутників з n вершинами, r з яких мають кути більші ніж Пі, за час O(n log2 n + r3/2 log r).[10] В найкращому випадку r може бути лінійною, тоді оцінка часу може бути спрощена до O(n3/2 log n).
  • Монотонний многокутник по відношенню до L — це многокутник зі властивістю, що кожна лінія перпендикулярна до L перетинає многокутник в одинарному інтервалі. Коли вхідний многокутник є монотонним, його прямий кістяк може бути побудований за час O(n log n).[11]

Використання

Кожна точка всередині вхідного многокутника може бути піднята у тривимірний простір з використанням того часу, за який процес стиснення досягає цієї точки, як координату z. В результаті, тривимірна площина має постійну висоту на границі многокутника, та піднімається з постійним кутом по відношенню до них, крім точок самого прямого кістяка, де частини площини з'єднуються під різними кутами. Таким чином, прямий кістяк може бути використаний як множина ребер для будівництва даху, розміщений на стінах у формі початкового многокутника.[1][12] Найнижча фігура на ілюстрації показує площину, побудовану з прямого кістяка цим способом.

Демаін та Лубів використовували прямий кістяк як частину техніки для складання листа паперу таким чином, що даний многокутник може бути розрізаний одним прямим розрізом (теорема оріґамі про вирізання многокутника), та пов'язана з проблемами проектування оріґамі.[13]

Бареквет, використовує прямий кістяк в алгоритмі для знаходження тривимірної площини, що інтерполює між двома даними ламаними.[14]

Танас та Велткамп пропонують розкласти неопуклі многокутники на об'єднання опуклих зон, використовуючи прямий кістяк, при зіставленні форм у обробці зображень як крок попередньої обробки.[15]

Баджері та Раззарі використовують прямий кістяк, щоб показати укладку вершин у алгоритмі візуалізації графу, де малюнок графу обмежений границею многокутника.[16]

Прямий кістяк може також бути використаний для побудови паралельної кривої многокутника, аналогічний до побудови паралельної кривої з закругленими кутами утворених від серединної осі. Томоеда та Суґіхара застосували цю ідею до розробки вивіски, яку видно з ширших кутів, з ілюзією видимості глибини.[17] Точно так же, Ацент та Карр використовують прямі кістяки для розробки кольорових градієнтів, що відповідають контурам літер чи іншим фігурам.[18]

Разом з іншими типами кістяків, таких як медіальна вісь, прямий кістяк може бути використаний для згортання двомірної області до спрощеного одномірного представлення. Наприклад, Ганерт та Сестер описують використання цього типа прямого кістяка в географічних інформаційних системах для знаходження осьових ліній доріг.[19]

Кожне дерево без жодної вершини другої степені може бути реалізовано як прямий кістяк опуклого многокутника.[20] Опукла оболонка площини даху співвідноситься з його прямим кістяком, формуючи реалізацію Штейніца графу Халіна, сформований з дерева приєднанням його листків у циклі.

Більші виміри

Бареквет описав версію прямого кістяка для тривимірного многогранника, алгоритм для його обчислення та проаналізував його складність для декількох видів многогранників.[21]

Губер досліджував метричні простори в яких відповідні діаграми Вороного та прямі кістяки збігаються. Для двох вимірів, характеристика таких метричних вимірів завершена. Для більших вимірів, цей метод може бути інтерпретований як узагальнення прямих кістяків для певних вхідних фігур для довільних вимірів за допомогою діаграм Вороного.[22]

Примітки
  1. Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd (1996). У Maurer, Prof Dr Hermann; Calude, Prof Dr Cristian; Salomaa, Prof Dr Arto. A Novel Type of Skeleton for Polygons. J.UCS The Journal of Universal Computer Science (англ.). Springer Berlin Heidelberg. с. 752–761. ISBN 9783642803529. doi:10.1007/978-3-642-80350-5_65.
  2. Aichholzer, Oswin; Aurenhammer, Franz (1998). У Samoilenko, A.M. [www.igi.tugraz.at/auren/psfiles/aa-ssgpf-98.ps.gz Straight skeletons for general polygonal figures in the plane] Перевірте схему |url= (довідка) (Англійською).
  3. Peschka, Gustav A (1877). Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vorträge (Німецькою).
  4. Felkel, Petr; Obdržálek, Štěpán (1998). Straight skeleton implementation. SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics. с. 210–218.
  5. Huber, Stefan; Held, Martin (2010). Computing straight skeletons of planar straight-line graphs based on motorcycle graphs. Proceedings of the 22nd Canadian Conference on Computational Geometry.
  6. Huber, Stefan; Held, Martin (June 13–15, 2011). Theoretical and practical results on straight skeletons of planar straight-line graphs (Англійською). Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), Paris, France. с. 171–178.
  7. Stefan., Huber, (2012). Computing straight skeletons and motorcycle graphs : theory and practice.. Shaker Verlag Gmbh, Germa. ISBN 9783844009385. OCLC 936085820.
  8. Yakersberg, Evgeny (2004). Morphing Between Geometric Shapes Using Straight-Skeleton-Based Interpolation. Israel Institute of Technology.
  9. Eppstein, D.; Erickson, J. (1 грудня 1999). Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete & Computational Geometry (англ.) 22 (4). с. 569–592. ISSN 0179-5376. doi:10.1007/PL00009479. Процитовано 28 травня 2017.
  10. Cheng, Siu-Wing; Vigneron, Antoine (2002). Motorcycle graphs and straight skeletons. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. с. 156–165.
  11. Biedl, Therese; Held, Martin; Huber, Stefan; Kaaser, Dominik; Palfrader, Peter (1 лютого 2015). A simple algorithm for computing positively weighted straight skeletons of monotone polygons. Information Processing Letters 115 (2). с. 243–247. PMC PMC4308025. PMID 25648376. doi:10.1016/j.ipl.2014.09.021. Процитовано 28 травня 2017.
  12. Bélanger, David (2000). Designing Roofs of Buildings (Англійською). Архів оригіналу за 21 січня 2012. Процитовано 28 травня 2017.
  13. Discrete and Computational Geometry | SpringerLink (en-gb). doi:10.1007/b75044.
  14. Barequet, Gill; Goodrich, Michael T; Levi-Steiner, Aya; Steiner, Dvir (2003). Straight-skeleton based contour interpolation (Англійською). Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. с. 119–127.
  15. Tanase, Mirela; Veltkamp, Remco C. (2003). Polygon Decomposition Based on the Straight Line Skeleton. Proceedings of the Nineteenth Annual Symposium on Computational Geometry (ACM). с. 58–67. ISBN 1581136633. doi:10.1145/777792.777802. Процитовано 28 травня 2017.
  16. Bagheri, Alireza; Razzazi, Mohammadreza (2004). Drawing free trees inside simple polygons using polygon skeleton. с. 239–254. MR 2165282.
  17. Tomoeda, A.; Sugihara, K. (1 червня 2012). Computational Creation of a New Illusionary Solid Sign. 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering. с. 144–147. doi:10.1109/ISVD.2012.26. Процитовано 28 травня 2017.
  18. Asente, Paul; Carr, Nathan (2013). Creating Contour Gradients Using 3D Bevels. Proceedings of the Symposium on Computational Aesthetics (ACM). с. 63–66. ISBN 9781450322034. doi:10.1145/2487276.2487283. Процитовано 28 травня 2017.
  19. Haunert, Jan-Henrik; Sester, Monika (1 червня 2008). Area Collapse and Road Centerlines based on Straight Skeletons. GeoInformatica (англ.) 12 (2). с. 169–191. ISSN 1384-6175. doi:10.1007/s10707-007-0028-x. Процитовано 28 травня 2017.
  20. Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012). What makes a tree a straight skeleton?. Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12).
  21. Barequet, Gill; Eppstein, David; Goodrich, Michael T.; Vaxman, Amir (15 вересня 2008). Straight Skeletons of Three-Dimensional Polyhedra. Algorithms - ESA 2008 (англ.) (Springer, Berlin, Heidelberg). с. 148–160. doi:10.1007/978-3-540-87744-8_13. Процитовано 28 травня 2017.
  22. Huber, Stefan; Aichholzer, Oswin; Hackl, Thomas; Vogtenhuber, Birgit (2014). Straight skeletons by means of Voronoi diagrams under polyhedral distance functions. Proc. 26th Canadian Conference on Computational Geometry (CCCG'14).

Джерела
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.