Rättlinjigt skelett

Ett rätlinjigt skelett är en metod för att representera en polygon genom dess topologiska skelett . Det rätlinjiga skelettet liknar på vissa sätt medianaxlarna , men skiljer sig genom att skelettet består av linjesegment, medan en polygons medianaxlar kan inkludera paraboliska kurvor.

Rätlinjiga skelett definierades först för enkla polygoner av Eichholzer, Aurenhammer, Alberts och Gärtner [1] och generaliserades till plana rätlinjiga grafer Eichholzer och Aurenhammer [2] . I tolkningen av rätlinjiga skelett som projektioner av takytan diskuterades de intensivt av G. A. Peshka [3] .

Definition

Det rätlinjiga skelettet av en polygon definieras som en process av kontinuerlig sammandragning där sidorna rör sig parallellt med sig själva med konstant hastighet. När sidorna rör sig på det här sättet, rör sig även de hörn där sidorpar skär varandra med en hastighet som beror på vinkeln i spetsen. Om en av dessa rörliga hörn kolliderar med en icke-intilliggande sida delas polygonen i två och processen fortsätter för varje del separat. Ett rätlinjigt skelett är en uppsättning kurvor längs vilka topparna passerar under kompressionsprocessen. Illustrationen visar processen att krympa en polygon (övre figuren), i den mellersta figuren är ett rätlinjigt skelett markerat i blått.

Algoritmer

Ett rätlinjigt skelett kan erhållas genom att modellera kompressionsprocessen. Många olika skelettalgoritmer gör just det, skiljer sig åt i indata och i de datastrukturer de använder för att upptäcka kombinatoriska förändringar i indatapolygonen under komprimering.

Applikationer

Varje punkt inuti inmatningspolygonen kan lyftas (punktens z-koordinat) i 3D-rymden med den tid det tar att nå den punkten under reduktionsprocessen. Den resulterande 3D-ytan har en konstant höjd på polygonens sidor och reser sig i en konstant vinkel från dem, förutom vid punkter på själva det rätlinjiga skelettet, där delar av ytan möts i olika vinklar. Således kan ett rätlinjigt skelett användas som en uppsättning åsar för taket på en byggnad uppburen av väggar i form av en initial polygon [1] [13] . Den nedre figuren i illustrationen visar ytan som erhålls på detta sätt från ett rätlinjigt skelett.

Eric Demaine, Martin Demaine och Anna Lubiv använde det rätlinjiga skelettet som en del av tekniken att vika ett pappersark så att en given polygon kunde erhållas med ett enda rakt snitt ( Cutting a polygon with a single cut ), och relaterade origamiproblem [ 14] .

Barquet et al använde rätlinjiga skelett i en algoritm för att hitta en tredimensionell yta, vilket är en interpolation av två givna polygonala linjer [15] .

Tanase och Weltkamp föreslog att sönderdela konkava polygoner i konvexa regioner med hjälp av rätlinjiga skelett som ett steg i förberedelse för formigenkänning i bildbehandling [16] .

Bagheri och Razzazi använde rätlinjiga skelett för att placera hörn i en grafvisualiseringsalgoritm , med villkoret att hela grafen måste ligga inuti en polygon [17] .

Det rätlinjiga skelettet kan användas för att konstruera en karakteristisk kurva av polygonkorrigeringar med avfasade hörn, liknande konstruktionen av en karakteristisk kurva med rundade hörn bildade från medianaxlarna. Tomoeda och Sugihara tillämpade denna idé för att designa (trafik)skyltar som är synliga i stora vinklar och med uppenbar tredimensionalitet [18] . På liknande sätt använde Asente och Carr linjära skelett för att utveckla färggradienter för konturerna av bokstäver och andra former [19] .

Som med andra typer av skelett, såsom medianaxlar , kan ett rätlinjigt skelett användas för att omvandla en 2D-region till dess förenklade 1D-representation. Till exempel beskriver Hauntert och Sester användningen av denna typ av rätlinjiga skelett i geografiska informationssystem för att hitta vägarnas mittlinje [20] [21] .

Vilket träd som helst utan hörn av grad två kan realiseras som ett rätlinjigt skelett av en konvex polygon [22] . Takets konvexa skrov som motsvarar detta rätlinjiga skelett bildar Steinitz-förverkligandet av Halin-grafen som bildas av ett träd genom att förena dess löv till en cykel.

Högre dimensioner

Burket, Eppstein, Goodrich och Waksman definierade en version av rätlinjiga skelett för 3D- polyedrar , beskrev en algoritm för att beräkna dem och analyserade komplexiteten hos algoritmen på flera typer av polygoner [23] .

Huber, Eichholzer, Hackl och Vogtenhuber undersökte metriska utrymmen , där motsvarande Voronoi-diagram och rätlinjiga skelett sammanfaller. För tvådimensionella utrymmen finns en fullständig beskrivning av sådana mått. För högre dimensioner kan denna metod förstås som en generalisering av rätlinjiga skelett till någon form av objekt i en godtycklig dimension med hjälp av Voronoi-diagram [24] .

Anteckningar

  1. ↑ 1 2 3 Aichholzer, Aurenhammer, Alberts, Gärtner, 1995 , sid. 752–761.
  2. ↑ 1 2 Aichholzer, Aurenhammer, 1996 , sid. 117–126.
  3. ↑ Peschka, 1877 .
  4. ↑ Huber, Held, 2010 .
  5. ↑ Huber, Held, 2011 , sid. 171–178.
  6. ↑ FME (Felkel, Obdrzalek) .
  7. ↑ Felkel, Obdrzalek, 1998 , sid. 210–218.
  8. ↑ Huber, 2012 .
  9. ↑ Yakersberg, 2004 .
  10. ↑ Eppstein och Erickson 1999 , sid. 569–592.
  11. ↑ Cheng, Vigneron, 2002 , sid. 156–165.
  12. ↑ ( Biedl, Held, Huber, Kaaser, Palfrader 2015 ). Som noterat av Beadle et al., är algoritmen som tidigare publicerats av Das et al. inte korrekt enligt beskrivningen, och fungerar endast bra för indata i allmän position när inga hörn-till-vertex-händelser inträffar ( Das, Mukhopadhyay, Nandy, Patil, Rao 2010 )
  13. ↑ David Belanger .
  14. ↑ Demaine, Demaine, Lubiw, 1998 , sid. 104–117.
  15. ↑ Barequet, Goodrich, Levi-Steiner, Steiner, 2003 , sid. 119–127.
  16. ↑ Tănase, Veltkamp, ​​2003 , sid. 58–67.
  17. ↑ Bagheri, Razzazi, 2004 , sid. 239–254.
  18. ↑ Tomoeda, Sugihara, 2012 , sid. 144–147.
  19. ↑ Asente, Carr, 2013 , sid. 63–66.
  20. ↑ Haunert, Sester, 2008 , sid. 169–191.
  21. ↑ David Raleigh, 2008 .
  22. ↑ Aichholzer, Cheng, Devadoss, Hackl, Huber, Li, Risteski, 2012 .
  23. ↑ Barequet, Eppstein, Goodrich, Vaxman, 2008 , sid. 148–160.
  24. ↑ Huber, Aichholzer, Hackl, Vogtenhuber, 2014 .

Litteratur

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:e europeiska symposiet om algoritmer. - Springer-Verlag, 2008. - T. 5193. - S. 148-160. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-540-87744-8_13 .

Stefan Huber, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber. Proc. 26:e kanadensiska konferensen om beräkningsgeometri (CCCG'14). — 2014.

Länkar