Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Прямий кістяк це геометричний метод представлення многокутника за допомогою топологічного кістяка Він в деякому сенсі сх

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

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

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

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

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

Означення

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

Алгоритми

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

  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. doi:10.1007/978-3-642-80350-5_65. ISBN .
  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). (PDF). Proceedings of the 22nd Canadian Conference on Computational Geometry. Архів оригіналу (PDF) за 11 серпня 2017. Процитовано 28 травня 2017.
  6. Huber, Stefan; Held, Martin (June 13–15, 2011). Theoretical and practical results on straight skeletons of planar straight-line graphs (PDF) (Англійською) . 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 . 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. doi:10.1007/PL00009479. ISSN 0179-5376. Процитовано 28 травня 2017.
  10. Cheng, Siu-Wing; Vigneron, Antoine (2002). Motorcycle graphs and straight skeletons (PDF). 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. doi:10.1016/j.ipl.2014.09.021. PMC 4308025. PMID 25648376. Процитовано 28 травня 2017.{{}}: Обслуговування CS1: Сторінки з PMC з іншим форматом ()
  12. Bélanger, David (2000). (Англійською) . Архів оригіналу за 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. doi:10.1145/777792.777802. ISBN . Процитовано 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. doi:10.1145/2487276.2487283. ISBN . Процитовано 28 травня 2017.
  19. Haunert, Jan-Henrik; Sester, Monika (1 червня 2008). Area Collapse and Road Centerlines based on Straight Skeletons. GeoInformatica (англ.). Т. 12, № 2. с. 169—191. doi:10.1007/s10707-007-0028-x. ISSN 1384-6175. Процитовано 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? (PDF). 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 (PDF). Proc. 26th Canadian Conference on Computational Geometry (CCCG'14).

Джерела

  • Erickson, Jeff. . Архів оригіналу за 11 грудня 2006. Процитовано 28 травня 2017.
  • 2D Straight Skeleton in , the Computational Geometry Algorithms Library
  • Straight Skeleton for polygon with holes Straight Skeleton builder implemented in java.
  • Amit Parnerkar, Sarnath Ramnath. Engineering an efficient algorithm for finding the straight skeleton of a simple polygon in O(n log n).

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Pryamij kistyak ce geometrichnij metod predstavlennya mnogokutnika za dopomogoyu topologichnogo kistyaka Vin v deyakomu sensi shozhij na seredinnu vis ale vidriznyayetsya tim sho kistyak skladayetsya z pryamih linij todi yak seredinna vis mnogokutnika vklyuchaye parabolichni krivi Proces usadki pryamij kistyak sinim ta model dahu Pershe viznachennya pryamogo kistyaka dlya prostih mnogokutnikiv bulo rozrobleno v 1996 roci ta uzagalneno dlya planarnih pryamolinijnih grafiv Interpretaciya zadachi yak proyekciya poverhon dahiv shiroko obgovoryuvalas G A Peshkoyu OznachennyaPryamij kistyak mnogokutnika viznachayetsya neperervnim procesom usadki v yakomu storoni mnogokutnika ruhayutsya vseredinu paralelno samim sobi z postijnoyu shvidkistyu Cherez te sho storoni tak ruhayutsya vershini de pari reber z yednuyutsya takozh ruhayutsya ale zi shvidkistyu sho zalezhit vid kuta ciyeyi vershini Yaksho odna z cih vershin peretinayetsya z nesumizhnim rebrom mnogokutnik dilitsya na dvi chastini cim peretinom ta proces prodovzhuyetsya okremo dlya kozhnoyi chastini Kreslennya trayektorij ruhu vershin pri comu procesi utvoryuye mnozhinu krivih yaki i ye pryamim kistyakom Na risunku najvisha figura pokazuye proces usadki a serednya figura zobrazhuye sinim kolorom pryamij kistyak AlgoritmiPryamij kistyak mozhe buti obchislenij simulyaciyeyu procesu usadki yakij opisano u navedenomu vishe oznachenni bulo zaproponovano dekilka variantiv algoritmiv dlya obchislennya sho vidriznyayutsya v pripushennyah yaki roblyat dlya vhidnih danih ta v strukturah danih yaki voni vikoristovuyut dlya viyavlennya kombinatornih zmin vhidnogo mnogokutnika v procesi jogo stisnennya Ajshholzer pokazav yak vichisliti pryamij kistyak dlya dovilnogo dvomirnogo mnogokutnika za chas O n3 log n abo bilsh tochno za chas O n2 f log n de n kilkist vershin a f chislo peretiniv vershin iz nesumizhnimi storonami pid chas buduvannya Najkrashe vidoma ocinka dlya f O n3 Algoritm z najgirshim chasom O nr log n abo prostishe O n2 log n buv zaproponovanij Guberom ta Geldom yaki argumentuvali sho yih pidhid pracyuvatime majzhe za linijnij chas dlya bilshosti vipadkiv Petr Felker ta Stepan Obdzhalek rozrobili algoritm sho vidomij ocinkoyu O nr n log r Prote vidomo sho yih algoritm ye nepravilnim Vikoristovuyuchi strukturi dlya zadachi najblizhchoyi pari tochok Epshtejn ta Erikson pokazali yak pobuduvati pryamij kistyak vikoristovuyuchi linijne chislo onovlen strukturi danih zadachi najblizhchoyi pari Algoritm strukturi najblizhchoyi pari bazuyetsya na derevi kvadrantiv ta peredbachaye ocinku chasu O nr n log n chi z istotno bilsh skladnoyu strukturoyu danih sho zabezpechuye krashu ocinku asimptotiki O n1 e n8 11 er9 11 e de e bud yaka konstanta bilsha za nul Cej algoritm zalishayetsya najkrashim za ocinkoyu dlya pryamogo kistyaku bez umov na vhidni dani ale vin skladnij i she ne buv realizovanij Dlya prostih mnogokutnikiv zadacha pobudovi pryamogo kistyaka prostisha Cheng na Vigneron pokazali yak vichisliti pryamij kistyak dlya prostih mnogokutnikiv z n vershinami r z yakih mayut kuti bilshi nizh Pi za chas O n log2n r3 2 log r V najkrashomu vipadku r mozhe buti linijnoyu todi ocinka chasu mozhe buti sproshena do O n3 2 log n Monotonnij mnogokutnik po vidnoshennyu do L ce mnogokutnik zi vlastivistyu sho kozhna liniya perpendikulyarna do L peretinaye mnogokutnik v odinarnomu intervali Koli vhidnij mnogokutnik ye monotonnim jogo pryamij kistyak mozhe buti pobudovanij za chas O n log n VikoristannyaKozhna tochka vseredini vhidnogo mnogokutnika mozhe buti pidnyata u trivimirnij prostir z vikoristannyam togo chasu za yakij proces stisnennya dosyagaye ciyeyi tochki yak koordinatu z V rezultati trivimirna ploshina maye postijnu visotu na granici mnogokutnika ta pidnimayetsya z postijnim kutom po vidnoshennyu do nih krim tochok samogo pryamogo kistyaka de chastini ploshini z yednuyutsya pid riznimi kutami Takim chinom pryamij kistyak mozhe buti vikoristanij yak mnozhina reber dlya budivnictva dahu rozmishenij na stinah u formi pochatkovogo mnogokutnika Najnizhcha figura na ilyustraciyi pokazuye ploshinu pobudovanu z pryamogo kistyaka cim sposobom Demain ta Lubiv vikoristovuvali pryamij kistyak yak chastinu tehniki dlya skladannya lista paperu takim chinom sho danij mnogokutnik mozhe buti rozrizanij odnim pryamim rozrizom teorema origami pro virizannya mnogokutnika ta pov yazana z problemami proektuvannya origami Barekvet vikoristovuye pryamij kistyak v algoritmi dlya znahodzhennya trivimirnoyi ploshini sho interpolyuye mizh dvoma danimi lamanimi Tanas ta Veltkamp proponuyut rozklasti neopukli mnogokutniki na ob yednannya opuklih zon vikoristovuyuchi pryamij kistyak pri zistavlenni form u obrobci zobrazhen yak krok poperednoyi obrobki Badzheri ta Razzari vikoristovuyut pryamij kistyak shob pokazati ukladku vershin u algoritmi vizualizaciyi grafu de malyunok grafu obmezhenij graniceyu mnogokutnika Pryamij kistyak mozhe takozh buti vikoristanij dlya pobudovi paralelnoyi krivoyi mnogokutnika analogichnij do pobudovi paralelnoyi krivoyi z zakruglenimi kutami utvorenih vid seredinnoyi osi Tomoeda ta Sugihara zastosuvali cyu ideyu do rozrobki viviski yaku vidno z shirshih kutiv z ilyuziyeyu vidimosti glibini Tochno tak zhe Acent ta Karr vikoristovuyut pryami kistyaki dlya rozrobki kolorovih gradiyentiv sho vidpovidayut konturam liter chi inshim figuram Razom z inshimi tipami kistyakiv takih yak medialna vis pryamij kistyak mozhe buti vikoristanij dlya zgortannya dvomirnoyi oblasti do sproshenogo odnomirnogo predstavlennya Napriklad Ganert ta Sester opisuyut vikoristannya cogo tipa pryamogo kistyaka v geografichnih informacijnih sistemah dlya znahodzhennya osovih linij dorig Kozhne derevo bez zhodnoyi vershini drugoyi stepeni mozhe buti realizovano yak pryamij kistyak opuklogo mnogokutnika Opukla obolonka ploshini dahu spivvidnositsya z jogo pryamim kistyakom formuyuchi realizaciyu Shtajnica grafu Halina sformovanij z dereva priyednannyam jogo listkiv u cikli Bilshi vimiriBarekvet opisav versiyu pryamogo kistyaka dlya trivimirnogo mnogogrannika algoritm dlya jogo obchislennya ta proanalizuvav jogo skladnist dlya dekilkoh vidiv mnogogrannikiv Guber doslidzhuvav metrichni prostori v yakih vidpovidni diagrami Voronogo ta pryami kistyaki zbigayutsya Dlya dvoh vimiriv harakteristika takih metrichnih vimiriv zavershena Dlya bilshih vimiriv cej metod mozhe buti interpretovanij yak uzagalnennya pryamih kistyakiv dlya pevnih vhidnih figur dlya dovilnih vimiriv za dopomogoyu diagram Voronogo PrimitkiAichholzer Oswin Aurenhammer Franz Alberts David Gartner Bernd 1996 Maurer Prof Dr Hermann Calude Prof Dr Cristian Salomaa Prof Dr Arto red A Novel Type of Skeleton for Polygons J UCS The Journal of Universal Computer Science angl Springer Berlin Heidelberg s 752 761 doi 10 1007 978 3 642 80350 5 65 ISBN 9783642803529 Aichholzer Oswin Aurenhammer Franz 1998 Samoilenko A M red www igi tugraz at auren psfiles aa ssgpf 98 ps gz Straight skeletons for general polygonal figures in the plane Anglijskoyu a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Perevirte shemu url dovidka Peschka Gustav A 1877 Kotirte Ebenen Kotirte Projektionen und deren Anwendung Vortrage Nimeckoyu Felkel Petr Obdrzalek Stepan 1998 Straight skeleton implementation SCCG 98 Proceedings of the 14th Spring Conference on Computer Graphics s 210 218 Huber Stefan Held Martin 2010 PDF Proceedings of the 22nd Canadian Conference on Computational Geometry Arhiv originalu PDF za 11 serpnya 2017 Procitovano 28 travnya 2017 Huber Stefan Held Martin June 13 15 2011 Theoretical and practical results on straight skeletons of planar straight line graphs PDF Anglijskoyu Proceedings of the Twenty Seventh Annual Symposium on Computational Geometry SCG 11 Paris France s 171 178 Stefan Huber 2012 Computing straight skeletons and motorcycle graphs theory and practice Shaker Verlag Gmbh Germa ISBN 9783844009385 OCLC 936085820 Yakersberg Evgeny 2004 Morphing Between Geometric Shapes Using Straight Skeleton Based Interpolation Israel Institute of Technology Eppstein D Erickson J 1 grudnya 1999 Raising Roofs Crashing Cycles and Playing Pool Applications of a Data Structure for Finding Pairwise Interactions Discrete amp Computational Geometry angl T 22 4 s 569 592 doi 10 1007 PL00009479 ISSN 0179 5376 Procitovano 28 travnya 2017 Cheng Siu Wing Vigneron Antoine 2002 Motorcycle graphs and straight skeletons PDF Proceedings of the 13th Annual ACM SIAM Symposium on Discrete Algorithms s 156 165 Biedl Therese Held Martin Huber Stefan Kaaser Dominik Palfrader Peter 1 lyutogo 2015 A simple algorithm for computing positively weighted straight skeletons of monotone polygons Information Processing Letters T 115 2 s 243 247 doi 10 1016 j ipl 2014 09 021 PMC 4308025 PMID 25648376 Procitovano 28 travnya 2017 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite news title Shablon Cite news cite news a Obslugovuvannya CS1 Storinki z PMC z inshim formatom posilannya Belanger David 2000 Anglijskoyu Arhiv originalu za 21 sichnya 2012 Procitovano 28 travnya 2017 Discrete and Computational Geometry SpringerLink en gb doi 10 1007 b75044 Barequet Gill Goodrich Michael T Levi Steiner Aya Steiner Dvir 2003 Straight skeleton based contour interpolation Anglijskoyu Proceedings of the Fourteenth Annual ACM SIAM Symposium on Discrete Algorithms s 119 127 Tanase Mirela Veltkamp Remco C 2003 Polygon Decomposition Based on the Straight Line Skeleton Proceedings of the Nineteenth Annual Symposium on Computational Geometry ACM s 58 67 doi 10 1145 777792 777802 ISBN 1581136633 Procitovano 28 travnya 2017 Bagheri Alireza Razzazi Mohammadreza 2004 Drawing free trees inside simple polygons using polygon skeleton s 239 254 MR 2165282 Tomoeda A Sugihara K 1 chervnya 2012 Computational Creation of a New Illusionary Solid Sign 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering s 144 147 doi 10 1109 ISVD 2012 26 Procitovano 28 travnya 2017 Asente Paul Carr Nathan 2013 Creating Contour Gradients Using 3D Bevels Proceedings of the Symposium on Computational Aesthetics ACM s 63 66 doi 10 1145 2487276 2487283 ISBN 9781450322034 Procitovano 28 travnya 2017 Haunert Jan Henrik Sester Monika 1 chervnya 2008 Area Collapse and Road Centerlines based on Straight Skeletons GeoInformatica angl T 12 2 s 169 191 doi 10 1007 s10707 007 0028 x ISSN 1384 6175 Procitovano 28 travnya 2017 Aichholzer Oswin Cheng Howard Devadoss Satyan L Hackl Thomas Huber Stefan Li Brian Risteski Andrej 2012 What makes a tree a straight skeleton PDF Proceedings of the 24th Canadian Conference on Computational Geometry CCCG 12 Barequet Gill Eppstein David Goodrich Michael T Vaxman Amir 15 veresnya 2008 Straight Skeletons of Three Dimensional Polyhedra Algorithms ESA 2008 angl Springer Berlin Heidelberg s 148 160 doi 10 1007 978 3 540 87744 8 13 Procitovano 28 travnya 2017 Huber Stefan Aichholzer Oswin Hackl Thomas Vogtenhuber Birgit 2014 Straight skeletons by means of Voronoi diagrams under polyhedral distance functions PDF Proc 26th Canadian Conference on Computational Geometry CCCG 14 DzherelaErickson Jeff Arhiv originalu za 11 grudnya 2006 Procitovano 28 travnya 2017 2D Straight Skeleton in the Computational Geometry Algorithms Library Straight Skeleton for polygon with holes Straight Skeleton builder implemented in java Amit Parnerkar Sarnath Ramnath Engineering an efficient algorithm for finding the straight skeleton of a simple polygon in O n log n

Дата публікації:
Топ