Přímočará kostra

Přímočará kostra je metoda reprezentace mnohoúhelníku jeho topologickou kostrou . Přímočará kostra je v některých ohledech podobná středním osám , ale liší se v tom, že kostra se skládá z úseček, zatímco střední osy mnohoúhelníku mohou zahrnovat parabolické křivky.

Přímočaré skelety byly poprvé definovány pro jednoduché polygony Eichholzerem, Aurenhammerem, Albertsem a Gärtnerem [1] a zobecněny na rovinné přímočaré grafy Eichholzerem a Aurenhammerem [2] . Při interpretaci přímočarých skeletů jako průmětů povrchu střech se jimi intenzivně zabýval G. A. Peshka [3] .

Definice

Přímočará kostra mnohoúhelníku je definována jako proces nepřetržitého smršťování, při kterém se strany pohybují rovnoběžně se sebou konstantní rychlostí. Když se strany pohybují tímto způsobem, vrcholy, kde se protínají dvojice stran, se také pohybují rychlostí závislou na úhlu ve vrcholu. Pokud se jeden z těchto pohyblivých vrcholů srazí s nesousedící stranou, mnohoúhelník se rozdělí na dva a proces pokračuje pro každou část zvlášť. Přímočará kostra je soubor křivek, podél kterých procházejí vrcholy během procesu komprese. Na obrázku je znázorněn proces zmenšování mnohoúhelníku (horní obrázek), na prostředním obrázku je modře zvýrazněna přímočará kostra.

Algoritmy

Přímočarou kostru lze získat modelováním procesu komprese. Mnoho různých kostrových algoritmů dělá právě to, liší se ve vstupních datech a v datových strukturách , které používají k detekci kombinatorických změn ve vstupním polygonu během komprese.

Aplikace

Každý bod uvnitř vstupního polygonu lze zvednout (souřadnici z bodu) ve 3D prostoru za dobu, kterou trvá dosažení tohoto bodu během procesu zmenšení. Výsledný 3D povrch má konstantní výšku po stranách mnohoúhelníku a stoupá od nich pod konstantním úhlem, kromě bodů na samotné přímočaré kostře, kde se části povrchu setkávají pod různými úhly. Přímočarý skelet lze tedy použít jako soubor hřebenů pro střechu budovy podepřenou stěnami ve formě počátečního polygonu [1] [13] . Spodní obrázek na obrázku znázorňuje takto získaný povrch z přímočaré kostry.

Eric Demaine, Martin Demaine a Anna Lubiv použili přímočarou kostru jako součást techniky skládání listu papíru tak, aby bylo možné daný mnohoúhelník získat jediným přímým řezem ( Řezání polygonu jediným řezem ), a související problémy s origami [14] .

Barquet et al použili přímočaré kostry v algoritmu pro nalezení trojrozměrného povrchu, který je interpolací dvou daných polygonálních čar [15] .

Tanase a Weltkamp navrhli rozklad konkávních polygonů na konvexní oblasti pomocí přímočarých koster jako krok v přípravě na rozpoznávání tvaru při zpracování obrazu [16] .

Bagheri a Razzazi použili přímočaré kostry k umístění vrcholů v algoritmu vizualizace grafu s podmínkou, že celý graf musí ležet uvnitř polygonu [17] .

Přímočarou kostru lze použít ke konstrukci charakteristické křivky polygonových korekcí se zkosenými rohy, podobně jako konstrukci charakteristické křivky se zaoblenými rohy vytvořenými ze středních os. Tomoeda a Sugihara aplikovali tuto myšlenku na návrh (dopravních) značek, které jsou viditelné pod velkými úhly a se zjevnou trojrozměrností [18] . Podobně Asente a Carr použili lineární kostry k vývoji barevných přechodů pro obrysy písmen a jiných tvarů [19] .

Stejně jako u jiných druhů koster, jako jsou střední osy , lze k transformaci 2D oblasti do její 1D zjednodušené reprezentace použít přímočarou kostru. Například Hauntert a Sester popisují použití tohoto typu přímočarých koster v geografických informačních systémech k nalezení středové linie komunikací [20] [21] .

Jakýkoli strom bez vrcholů stupně dva lze realizovat jako přímočarou kostru konvexního polygonu [22] . Konvexní trup střechy odpovídající této přímočaré kostře tvoří Steinitzovu realizaci Halinova grafu vytvořeného ze stromu spojením jeho listů do cyklu.

Vyšší rozměry

Burket, Eppstein, Goodrich a Waksman definovali verzi přímočarých koster pro 3D mnohostěny , popsali algoritmus pro jejich výpočet a analyzovali složitost algoritmu na několika typech polygonů [23] .

Huber, Eichholzer, Hackl a Vogtenhuber zkoumali metrické prostory , ve kterých se odpovídající Voronoiovy diagramy a přímočaré kostry shodují. Pro dvourozměrné prostory existuje úplný popis takových metrik. Pro vyšší dimenze lze tuto metodu chápat jako zobecnění přímočarých koster na nějakou formu objektů v libovolné dimenzi pomocí Voronoiových diagramů [24] .

Poznámky

  1. ↑ 1 2 3 Aichholzer, Aurenhammer, Alberts, Gärtner, 1995 , str. 752–761.
  2. ↑ 1 2 Aichholzer, Aurenhammer, 1996 , str. 117–126.
  3. ↑ Peschka, 1877 .
  4. ↑ Huber, Held, 2010 .
  5. ↑ Huber, Held, 2011 , str. 171–178.
  6. ↑ FSI (Felkel, Obdržálek) .
  7. ↑ Felkel, Obdržálek, 1998 , str. 210–218.
  8. ↑ Huber, 2012 .
  9. ↑ Yakersberg, 2004 .
  10. ↑ Eppstein a Erickson 1999 , str. 569–592.
  11. ↑ Cheng, Vigneron, 2002 , str. 156–165.
  12. ↑ ( Biedl, Held, Huber, Kaaser, Palfrader 2015 ). Jak poznamenali Beadle et al., algoritmus dříve publikovaný Das et al. není správný, jak je popsáno, a funguje dobře pouze pro vstupy v obecné poloze , když nedochází k žádným událostem mezi vertexy ( Das, Mukhopadhyay, Nandy, Patil, Rao 2010 )
  13. ↑ David Belanger .
  14. ↑ Demaine, Demaine, Lubiw, 1998 , str. 104–117.
  15. ↑ Barequet, Goodrich, Levi-Steiner, Steiner, 2003 , str. 119–127.
  16. ↑ Tănase, Veltkamp, ​​​​2003 , s. 58–67.
  17. ↑ Bagheri, Razzazi, 2004 , str. 239–254.
  18. ↑ Tomoeda, Sugihara, 2012 , str. 144–147.
  19. ↑ Asente, Carr, 2013 , str. 63–66.
  20. ↑ Haunert, Sester, 2008 , str. 169–191.
  21. ↑ David Raleigh, 2008 .
  22. ↑ Aichholzer, Cheng, Devadoss, Hackl, Huber, Li, Risteski, 2012 .
  23. ↑ Barequet, Eppstein, Goodrich, Vaxman, 2008 , str. 148–160.
  24. ↑ Huber, Aichholzer, Hackl, Vogtenhuber, 2014 .

Literatura

Oswin Aichholzer, Howard Cheng, Satyan L. Devadoss, Thomas Hackl, Stefan Huber, Brian Li, Andrej Risteski. Sborník příspěvků z 24. kanadské konference o výpočetní geometrii (CCCG'12). — 2012. Gill Barequet, David Eppstein, Michael T. Goodrich, Amir Vaxman. Proč. 16. evropské sympozium o algoritmech. - Springer-Verlag, 2008. - T. 5193. - S. 148-160. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-87744-8_13 .

Stefan Huber, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber. Proč. 26. kanadská konference o výpočetní geometrii (CCCG'14). — 2014.

Odkazy