Schelet rectiliniu

Un schelet rectiliniu este o metodă de reprezentare a unui poligon prin scheletul său topologic . Scheletul rectiliniu este similar în anumite privințe cu axele mediane , dar diferă prin faptul că scheletul constă din segmente de linie, în timp ce axele mediane ale unui poligon pot include curbe parabolice.

Scheletele rectilinii au fost definite pentru poligoane simple de către Eichholzer, Aurenhammer, Alberts și Gärtner [1] și generalizate la grafuri rectilinii plane Eichholzer și Aurenhammer [2] . În interpretarea scheletelor rectilinii ca proiecții ale suprafeței acoperișurilor, acestea au fost discutate intens de G. A. Peshka [3] .

Definiție

Scheletul rectiliniu al unui poligon este definit ca un proces de contracție continuă în care laturile se mișcă paralel cu ele însele cu o viteză constantă. Când laturile se mișcă în acest fel, vârfurile în care se intersectează perechi de laturi se mișcă și ele cu o viteză dependentă de unghiul de la vârf. Dacă unul dintre aceste vârfuri în mișcare se ciocnește cu o latură neadiacentă, poligonul se împarte în două și procesul continuă pentru fiecare parte separat. Un schelet rectiliniu este un set de curbe de-a lungul cărora trec vârfurile în timpul procesului de compresie. Ilustrația prezintă procesul de micșorare a unui poligon (figura de sus), în figura din mijloc este evidențiat cu albastru un schelet rectiliniu.

Algoritmi

Un schelet rectiliniu poate fi obținut prin modelarea procesului de compresie. Mulți algoritmi de schelet diferiți fac exact asta, diferând în datele de intrare și în structurile de date pe care le folosesc pentru a detecta modificări combinatorii în poligonul de intrare în timpul compresiei.

Aplicații

Fiecare punct din interiorul poligonului de intrare poate fi ridicat (coordonata z a punctului) în spațiul 3D în timpul necesar pentru a ajunge la acel punct în timpul procesului de reducere. Suprafața 3D rezultată are o înălțime constantă pe părțile laterale ale poligonului și se ridică la un unghi constant față de acestea, cu excepția punctelor de pe scheletul rectiliniu însuși, unde părți ale suprafeței se întâlnesc în unghiuri diferite. Astfel, un schelet rectiliniu poate fi folosit ca ansamblu de coame pentru acoperișul unei clădiri susținute de pereți sub forma unui poligon inițial [1] [13] . Figura de jos din ilustrație arată suprafața obținută în acest fel dintr-un schelet rectiliniu.

Eric Demaine, Martin Demaine și Anna Lubiv au folosit scheletul rectiliniu ca parte a tehnicii de pliere a unei foi de hârtie, astfel încât un anumit poligon să poată fi obținut printr-o singură tăietură dreaptă ( Tăierea unui poligon cu o singură tăietură ), și probleme legate de origami [14] .

Barquet și colaboratorii au folosit schelete rectilinii într-un algoritm pentru găsirea unei suprafețe tridimensionale, care este o interpolare a două linii poligonale date [15] .

Tanase și Weltkamp au propus descompunerea poligoanelor concave în regiuni convexe folosind schelete rectilinii ca pas în pregătirea pentru recunoașterea formei în procesarea imaginilor [16] .

Bagheri și Razzazi au folosit schelete rectilinii pentru a poziționa vârfurile într-un algoritm de vizualizare a graficului, cu condiția ca întregul grafic să se afle în interiorul unui poligon [17] .

Scheletul rectiliniu poate fi folosit pentru a construi o curbă caracteristică a corecțiilor poligonului cu colțuri teșite, similară construcției unei curbe caracteristice cu colțuri rotunjite formate din axele mediane. Tomoeda și Sugihara au aplicat această idee pentru a proiecta semne (de trafic) care sunt vizibile la unghiuri mari și cu aparentă tridimensionalitate [18] . În mod similar, Asente și Carr au folosit schelete liniare pentru a dezvolta gradienți de culoare pentru contururile literelor și a altor forme [19] .

Ca și în cazul altor tipuri de schelete, cum ar fi axele mediane , un schelet rectiliniu poate fi utilizat pentru a transforma o regiune 2D în reprezentarea sa simplificată 1D. De exemplu, Hauntert și Sester descriu utilizarea acestui tip de schelete rectilinii în sistemele de informații geografice pentru a găsi linia centrală a drumurilor [20] [21] .

Orice arbore fără vârfuri de gradul doi poate fi realizat ca un schelet rectiliniu al unui poligon convex [22] . Corpul convex al acoperișului corespunzător acestui schelet rectiliniu formează realizarea lui Steinitz a graficului Halin format dintr-un copac prin unirea frunzelor acestuia într-un ciclu.

Dimensiuni mai mari

Burket, Eppstein, Goodrich și Waksman au definit o versiune de schelete rectilinii pentru poliedre 3D , au descris un algoritm pentru calcularea acestora și au analizat complexitatea algoritmului pe mai multe tipuri de poligoane [23] .

Huber, Eichholzer, Hackl și Vogtenhuber au investigat spațiile metrice , în care coincid diagramele Voronoi și scheletele rectilinii corespunzătoare. Pentru spațiile bidimensionale, există o descriere completă a unor astfel de metrici. Pentru dimensiuni mai mari, această metodă poate fi înțeleasă ca o generalizare a scheletelor rectilinii la o anumită formă de obiecte într-o dimensiune arbitrară folosind diagramele Voronoi [24] .

Note

  1. ↑ 1 2 3 Aichholzer, Aurenhammer, Alberts, Gärtner, 1995 , p. 752–761.
  2. ↑ 1 2 Aichholzer, Aurenhammer, 1996 , p. 117–126.
  3. ↑ Peschka, 1877 .
  4. ↑ Huber, Held, 2010 .
  5. ↑ Huber, Held, 2011 , p. 171–178.
  6. ↑ FME (Felkel, Obdrzalek) .
  7. ↑ Felkel, Obdrzalek, 1998 , p. 210–218.
  8. ↑ Huber, 2012 .
  9. ↑ Yakersberg, 2004 .
  10. ↑ Eppstein și Erickson 1999 , p. 569–592.
  11. ↑ Cheng, Vigneron, 2002 , p. 156–165.
  12. ↑ ( Biedl, Held, Huber, Kaaser, Palfrader 2015 ). După cum au observat de către Beadle și colab., algoritmul publicat anterior de Das și colab. nu este corect așa cum este descris și funcționează bine doar pentru intrările în poziție generală atunci când nu au loc evenimente de la vârf la vârf ( Das, Mukhopadhyay, Nandy, Patil, Rao 2010 )
  13. ↑ David Belanger .
  14. ↑ Demaine, Demaine, Lubiw, 1998 , p. 104–117.
  15. ↑ Barequet, Goodrich, Levi-Steiner, Steiner, 2003 , p. 119–127.
  16. ↑ Tănase, Veltkamp, ​​​​2003 , p. 58–67.
  17. ↑ Bagheri, Razzazi, 2004 , p. 239–254.
  18. ↑ Tomoeda, Sugihara, 2012 , p. 144–147.
  19. ↑ Asente, Carr, 2013 , p. 63–66.
  20. ↑ Haunert, Sester, 2008 , p. 169–191.
  21. ↑ David Raleigh, 2008 .
  22. ↑ Aichholzer, Cheng, Devadoss, Hackl, Huber, Li, Risteski, 2012 .
  23. ↑ Barequet, Eppstein, Goodrich, Vaxman, 2008 , p. 148–160.
  24. ↑ Huber, Aichholzer, Hackl, Vogtenhuber, 2014 .

Literatură

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. Al 16-lea Simpozion European de Algoritmi. - Springer-Verlag, 2008. - T. 5193. - S. 148-160. — (Note de curs în Informatică). - doi : 10.1007/978-3-540-87744-8_13 .

Stefan Huber, Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber. Proc. A 26-a Conferință canadiană privind geometria computațională (CCCG'14). — 2014.

Link -uri