Retlineært skelet

Et retlinet skelet er en metode til at repræsentere en polygon ved dets topologiske skelet . Det retlinede skelet ligner på nogle måder medianakserne , men adskiller sig ved, at skelettet består af linjestykker, mens en polygons medianakser kan omfatte parabolske kurver.

Retlinede skeletter blev først defineret for simple polygoner af Eichholzer, Aurenhammer, Alberts og Gärtner [1] og generaliseret til plane retlinede grafer Eichholzer og Aurenhammer [2] . I fortolkningen af ​​retlinede skeletter som projektioner af overfladen af ​​tage, blev de intensivt diskuteret af G. A. Peshka [3] .

Definition

Det retlinede skelet af en polygon er defineret som en proces med kontinuerlig sammentrækning, hvor siderne bevæger sig parallelt med sig selv med en konstant hastighed. Når siderne bevæger sig på denne måde, bevæger de hjørner, hvor sidepar krydser hinanden, sig også med en hastighed, der afhænger af vinklen ved toppunktet. Hvis et af disse bevægelige hjørner kolliderer med en ikke-tilstødende side, opdeles polygonen i to, og processen fortsætter for hver del separat. Et retlinet skelet er et sæt kurver, langs hvilke hjørnerne passerer under kompressionsprocessen. Illustrationen viser processen med at krympe en polygon (øverste figur), i den midterste figur er et retlinet skelet fremhævet med blåt.

Algoritmer

Et retlinet skelet kan opnås ved at modellere kompressionsprocessen. Mange forskellige skeletalgoritmer gør netop det, idet de adskiller sig i inputdata og i de datastrukturer, de bruger til at detektere kombinatoriske ændringer i inputpolygonen under komprimering.

• Eichholzer et al. [1] [2] viste, hvordan man kan beregne lineære skeletter for vilkårlige 2D polygoner i O( n 3  log  n ), eller mere præcist, i O(( n 2 + f ) log  n ) tid , hvor n er antallet af input polygon-hjørner, og f er antallet af flip-begivenheder under konstruktion. Det bedst kendte estimat for f er O( n 3 ).
• En algoritme med en worst-case køretid på O( nr  log n), eller blot O( n 2  log n), blev givet af Huber og Held, og de hævder, at deres algoritme kører i næsten lineær tid for de fleste input [4 ] [5] .
• Piotr Völkel og Stjepan Obdrzalek har udviklet en algoritme, som de siger har en effektivitet på O(nr + n log r) [6] [7] . Der har dog været rapporter om, at deres algoritme er forkert [8] [9] .
• Ved at bruge datastrukturen for problemet med det tofarvede nærmeste par af punkter , viste Eppstein og Erickson, hvordan man konstruerer retlinede skeletter ved hjælp af et lineært antal opdateringer til datastrukturen af ​​nærmeste par af punkter. Datastrukturen for de nærmeste punktpar, baseret på quadtree , giver en algoritme med køretid O( nr  +  n  log  n ), mens en meget mere kompleks datastruktur fører til en bedre asymptotisk binding på køretid O( n 1 + ε + n 8/11 + εr 9/11 + ε ) , eller mere enkelt O( n 17/11 + ε ) , hvor ε er en konstant større end nul [10] . Dette er fortsat den bedste (worst case) køretid, der er bundet til at konstruere et retlinet skelet uden input-begrænsninger, men algoritmen er kompleks og er ikke blevet implementeret.
• For simple polygoner er opgaven med at konstruere et retlinet skelet lettere. Cheng og Wingeron viste, hvordan man beregner det retlinede skelet af en simpel polygon med n toppunkter, hvoraf r har vinkler større end , i tiden O( n log 2 n + r 3/2 log r ) [11] . I værste fald kan r være lineær og køretiden reduceres til O( n 3/2  log  n ).
• En monoton polygon i forhold til en linie L er en polygon med den egenskab, at skæringen af ​​en hvilken som helst linie vinkelret på L med polygonen er et enkelt segment. Hvis en monoton polygon tages som input, kan dens retlinede skelet konstrueres i O( n  log  n ) tid [12] .

Ansøgninger

Hvert punkt inde i inputpolygonen kan løftes (punktets z-koordinat) i 3D-rum med den tid, det tager at nå dette punkt under reduktionsprocessen. Den resulterende 3D-overflade har en konstant højde på polygonens sider og rejser sig i en konstant vinkel fra dem, undtagen på punkter på selve det retlinede skelet, hvor dele af overfladen mødes i forskellige vinkler. Et retlinet skelet kan således bruges som et sæt kamme til taget af en bygning understøttet af vægge i form af en indledende polygon [1] [13] . Den nederste figur i illustrationen viser overfladen opnået på denne måde fra et retlinet skelet.

Eric Demaine, Martin Demaine og Anna Lubiv brugte det retlinede skelet som en del af teknikken med at folde et ark papir, så en given polygon kunne opnås med et enkelt lige snit ( Cutting a polygon with a single cut ), og relaterede origami- problemer [14] .

Barquet et al brugte retlinede skeletter i en algoritme til at finde en tredimensionel overflade, som er en interpolation af to givne polygonale linjer [15] .

Tanase og Weltkamp foreslog at nedbryde konkave polygoner i konvekse områder ved hjælp af retlinede skeletter som et trin i forberedelsen til formgenkendelse i billedbehandling [16] .

Bagheri og Razzazi brugte retlinede skeletter til at placere toppunkter i en grafvisualiseringsalgoritme med den betingelse, at hele grafen skal ligge inde i en polygon [17] .

Det retlinede skelet kan bruges til at konstruere en karakteristisk kurve af polygonkorrektioner med affasede hjørner, svarende til konstruktionen af ​​en karakteristisk kurve med afrundede hjørner dannet af medianakserne. Tomoeda og Sugihara anvendte denne idé til at designe (trafik)skilte, der er synlige i store vinkler og med tilsyneladende tredimensionalitet [18] . På samme måde brugte Asente og Carr lineære skeletter til at udvikle farvegradienter til konturerne af bogstaver og andre former [19] .

Som med andre slags skeletter, såsom medianakser , kan et retlinet skelet bruges til at transformere et 2D-område til dets 1D-forenklede repræsentation. For eksempel beskriver Hauntert og Sester brugen af ​​denne type retlinede skeletter i geografiske informationssystemer til at finde vejes midterlinje [20] [21] .

Ethvert træ uden hjørner af grad to kan realiseres som et retlinet skelet af en konveks polygon [22] . Tagets konvekse skrog , der svarer til dette retlinede skelet, danner Steinitz-realiseringen af ​​Halin-grafen dannet af et træ ved at forbinde dets blade til en cyklus.

Højere dimensioner

Burket, Eppstein, Goodrich og Waksman definerede en version af retlinede skeletter til 3D polyedre , beskrev en algoritme til at beregne dem og analyserede kompleksiteten af ​​algoritmen på flere typer polygoner [23] .

Huber, Eichholzer, Hackl og Vogtenhuber undersøgte metriske rum , hvor de tilsvarende Voronoi-diagrammer og retlinede skeletter falder sammen. For todimensionelle rum er der en komplet beskrivelse af sådanne metrikker. For højere dimensioner kan denne metode forstås som en generalisering af retlinede skeletter til en eller anden form for objekter i en vilkårlig dimension ved hjælp af Voronoi-diagrammer [24] .

Noter

1. ↑ 1 2 3 Aichholzer, Aurenhammer, Alberts, Gärtner, 1995 , s. 752-761.
2. ↑ 1 2 Aichholzer, Aurenhammer, 1996 , s. 117-126.
3. ↑ Peschka, 1877 .
4. ↑ Huber, Held, 2010 .
5. ↑ Huber, Held, 2011 , s. 171-178.
6. ↑ FME (Felkel, Obdrzalek) .
7. ↑ Felkel, Obdrzalek, 1998 , s. 210-218.
8. ↑ Huber, 2012 .
9. ↑ Yakersberg, 2004 .
10. ↑ Eppstein og Erickson 1999 , s. 569-592.
11. ↑ Cheng, Vigneron, 2002 , s. 156-165.
12. ↑ ( Biedl, Held, Huber, Kaaser, Palfrader 2015 ). Som bemærket af Beadle et al., er algoritmen tidligere udgivet af Das et al. ikke korrekt som beskrevet og fungerer kun godt til input i generel position, når der ikke forekommer toppunkt-til-vertex-hændelser ( Das, Mukhopadhyay, Nandy, Patil, Rao 2010 )
13. ↑ David Belanger .
14. ↑ Demaine, Demaine, Lubiw, 1998 , s. 104-117.
15. ↑ Barequet, Goodrich, Levi-Steiner, Steiner, 2003 , s. 119-127.
16. ↑ Tănase, Veltkamp, ​​2003 , s. 58-67.
17. ↑ Bagheri, Razzazi, 2004 , s. 239-254.
18. ↑ Tomoeda, Sugihara, 2012 , s. 144-147.
19. ↑ Asente, Carr, 2013 , s. 63-66.
20. ↑ Haunert, Sester, 2008 , s. 169-191.
21. ↑ David Raleigh, 2008 .
22. ↑ Aichholzer, Cheng, Devadoss, Hackl, Huber, Li, Risteski, 2012 .
23. ↑ Barequet, Eppstein, Goodrich, Vaxman, 2008 , s. 148-160.
24. ↑ Huber, Aichholzer, Hackl, Vogtenhuber, 2014 .

Litteratur

• Oswin Aichholzer, Franz Aurenhammer, David Alberts, Bernd Gärtner. En ny type skelet til polygoner // Journal of Universal Computer Science. - 1995. - Vol. 1 , udgave. 12 . - S. 752-761 . - doi : 10.1007/978-3-642-80350-5_65 .

• Oswin Aichholzer, Franz Aurenhammer. Proc. 2. Ann. Int. Konf. Computing and Combinatorics (COCOON '96). - Springer-Verlag, 1996. - T. 1090. - S. 117-126. — (Forelæsningsnotater i datalogi).
• Gustav A. Peschka. Kotirte Ebenen: Kotirte Projektionen und deren Anwendung; Vortrage. — 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), juni 13-15, 2011, Paris, Frankrig. - 2011. - S. 171-178.
• Petr Felkel, Štěpán Obdrzalek. F.M.E. Transformers . CenterLineReplacer . Sikker software . Hentet: 9. marts 2017. (ubestemt)
• Petr Felkel, Štěpán Obdrzalek. SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics. - 1998. - S. 210-218.
• Stephen Huber. Beregning af lige skeletter og motorcykelgrafer: teori og praksis. - Shaker Verlag, 2012. - ISBN 978-3-8440-0938-5 .
• Evgeny Yakersberg. Forvandling mellem geometriske former ved hjælp af lige skeletbaseret interpolation. — Israel Institute of Technology, 2004.
• David Eppstein, Jeff Erickson. Forhøjelse af tage, styrtende cyklusser og spille pool: anvendelser af en datastruktur til at finde parvise interaktioner // Diskret og beregningsgeometri . - 1999. - T. 22 , no. 4 . - S. 569-592 . - doi : 10.1007/PL00009479 .
• Siu-Wing Cheng, Antoine Vigneron. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algoritms. - 2002. - S. 156-165.
• Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader. En simpel algoritme til beregning af positivt vægtede lige skeletter af monotone polygoner // Informationsbehandlingsbogstaver. - 2015. - T. 115 , no. 2 . - S. 243-247 . - doi : 10.1016/j.ipl.2014.09.021 .
• Gautam K. Das, Asish Mukhopadhyay, Subhas C. Nandy, Sangameswar Patil, SV Rao. Proceedings of the 22nd canadian Conference on Computational Geometry. – 2010.
• David Belanger. Design af bygningers tag (ikke tilgængeligt link) . Hentet 8. marts 2017. Arkiveret fra originalen 21. januar 2012. (ubestemt) 
• Erik Demaine, Martin Demaine, Anna Lubiw. Reviderede papirer fra Japan Conference on Discrete and Computational Geometry (JCDCG'98). - Springer-Verlag, 1998. - T. 1763 . - S. 104-117 . - doi : 10.1007/b75044 .
• Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, Dvir Steiner. Proceedings af det fjortende årlige ACM-SIAM-symposium om diskrete algoritmer. - 2003. - S. 119-127.
• Mirela Tănase, Remco C. Veltkamp. Proceedings of the 19th Annual ACM Symposium on Computational Geometry . - 2003. - S. 58-67. doi : 10.1145/ 777792.777802 .
• Alireza Bagheri, Mohammadreza Razzazi. Tegning af frie træer inde i simple polygoner ved hjælp af polygonskelet // Computing and Informatics. - 2004. - T. 23 , no. 3 . - S. 239-254 .
• Akiyasu Tomoeda, Kokichi Sugihara. Niende internationale symposium om Voronoi-diagrammer i videnskab og teknik (ISVD 2012). - 2012. - S. 144-147. - doi : 10.1109/ISVD.2012.26 .
• Paul Asente, Nathan Carr. Proceedings of the Symposium on Computational Aesthetics (CAE '13, Anaheim, Californien). - New York, NY, USA: ACM, 2013. - S. 63-66. — ISBN 978-1-4503-2203-4 . - doi : 10.1145/2487276.2487283 .
• Jan-Henrik Haunert, Monika Sester. Områdekollaps og vejmidterlinjer baseret på lige skeletter // Geoinformatica. - 2008. - T. 12 , no. 2 . - S. 169-191 . - doi : 10.1007/s10707-007-0028-x .
• David Baring Raleigh. Straight Skeleton Survey Justering af vejmidterlinjer fra gps grove indsamlingsdata: et casestudie i 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. 16. europæiske symposium om algoritmer. - Springer-Verlag, 2008. - T. 5193. - S. 148-160. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-540-87744-8_13 .

Stefan Huber, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber. Proc. 26. canadiske konference om beregningsgeometri (CCCG'14). – 2014.

Links

• Erickson, Jeff. Lige skelet af en simpel polygon (utilgængeligt link) . Hentet 9. marts 2017. Arkiveret fra originalen 11. december 2006. (ubestemt) 
• 2D Straight Skeleton i CGAL , Computational Geometry Algorithms Library
• Lige skelet til polygon med huller Lige skelet builder implementeret i java.
• Amit Parnerkar, Sarnath Ramnath. Konstruere en effektiv algoritme til at finde det lige skelet af en simpel polygon i O(n log n) . (ubestemt)