Polygon triangulace - Polygon triangulation

Polygon triangulace.

v výpočetní geometrie, polygon triangulace je rozklad a polygonální oblast (jednoduchý mnohoúhelník ) P do sady trojúhelníky,[1] tj. nalezení sady trojúhelníků s párovými neprotínajícími se interiéry, jejichž svaz je P.

Na trojúhelníky lze pohlížet jako na zvláštní případy rovinné přímkové grafy. Pokud nejsou žádné díry nebo přidané body, vytvoří se triangulace maximální vnější rovinné grafy.

Polygon triangulace bez dalších vrcholů

V průběhu času bylo navrženo několik algoritmů pro triangulaci mnohoúhelníku.

Speciální případy

42 možných triangulací pro a konvexní sedmiúhelník (7stranný konvexní mnohoúhelník). Toto číslo je dáno 5. Katalánské číslo.

Je triviální libovolně triangulovat konvexní mnohoúhelník v lineární čas do triangulace ventilátoru přidáním úhlopříček z jednoho vrcholu ke všem ostatním vrcholům.

Celkový počet způsobů, jak triangulovat konvexní n-gon neprotínajícími se úhlopříčkami je (n−2) nd Katalánské číslo, což se rovná , řešení nalezeno Leonhard Euler.[2]

A monotónní mnohoúhelník lze triangulovat v lineárním čase buď s algoritmem A. Fournier a D.Y. Montuno,[3] nebo algoritmus Godfried Toussaint.[4]

Metoda ořezávání uší

Mnohoúhelníkové ucho

Jeden způsob, jak triangulovat jednoduchý mnohoúhelník, je založen na věta o dvou uších, protože skutečnost, že jakýkoli jednoduchý mnohoúhelník s nejméně 4 vrcholy bez děr má alespoň dva 'uši ', což jsou trojúhelníky, jejichž dvě strany jsou hranami mnohoúhelníku a třetí zcela v něm.[5] Algoritmus pak spočívá v nalezení takového ucha, jeho odstranění z polygonu (což má za následek nový polygon, který stále splňuje podmínky) a opakování, dokud nezbude jen jeden trojúhelník.

Tento algoritmus je snadno implementovatelný, ale pomalejší než některé jiné algoritmy a funguje pouze na polygony bez děr. Bude spuštěna implementace, která udržuje samostatné seznamy konvexních a konkávních vrcholů Ó(n2) čas. Tato metoda je známá jako ořezávání uší a někdy ořezávání uší. Efektivní algoritmus pro odříznutí uší objevili Hossam ElGindy, Hazel Everett a Godfried Toussaint.[6]

Monotónní polygonová triangulace

Rozdělení mnohoúhelníku na monotónní mnohoúhelníky

Jednoduchý mnohoúhelník je monotónní vzhledem k přímce L, pokud existuje přímka kolmá na L protíná polygon maximálně dvakrát. Monotónní mnohoúhelník lze rozdělit na dva monotónní řetězy. Polygon, který je monotónní vzhledem k ose y, se nazývá y-monotónní. Monotónní mnohoúhelník s n vrcholy lze triangulovat dovnitř Ó(n) čas. Za předpokladu, že daný polygon je y-monotónní, je chamtivý algoritmus začíná chůzí po jednom řetězci mnohoúhelníku shora dolů a přidáním úhlopříček, kdykoli je to možné.[1] Je snadné vidět, že algoritmus lze použít na jakýkoli monotónní polygon.

Triangulace nemonotónního polygonu

Pokud mnohoúhelník není monotónní, lze jej rozdělit na monotónní subpolygony v Ó(n log n) čas pomocí a zametací linie Algoritmus nevyžaduje, aby byl mnohoúhelník jednoduchý, takže jej lze použít na polygony s otvory. Obecně může tento algoritmus triangulovat rovinné dělení s n vrcholy v Ó(n log n) čas pomocí Ó(n) prostor.[1]

Duální graf triangulace

Užitečný graf, který je často spojen s triangulací mnohoúhelníku P je duální graf. Vzhledem k triangulaci TP z P, jeden definuje graf G(TP) jako graf, jehož vrcholem jsou trojúhelníky TP, dva vrcholy (trojúhelníky) sousedí právě tehdy, pokud sdílejí úhlopříčku. Je snadné to pozorovat G(TP) je strom s maximálním stupněm 3.

Výpočetní složitost

Do roku 1988, ať už a jednoduchý mnohoúhelník lze triangulovat rychleji než Ó(n log n) čas byl otevřeným problémem ve výpočetní geometrii.[1] Pak, Tarjan & Van Wyk (1988) objevil Ó(n log log n)-časový algoritmus pro triangulaci,[7] později zjednodušeno o Kirkpatrick, Klawe & Tarjan (1992).[8] Několik vylepšených metod se složitostí Ó(n log* n) (v praxi k nerozeznání od lineární čas ) následoval.[9][10][11]

Bernard Chazelle v roce 1991 ukázal, že jakýkoli jednoduchý polygon lze triangulovat v lineárním čase, ačkoli navrhovaný algoritmus je velmi složitý.[12] Je také známý jednodušší randomizovaný algoritmus s lineárním očekávaným časem.[13]

Seidelův rozkladový algoritmus a Chazellova triangulační metoda jsou podrobně popsány v Li & Klette (2011).[14]

The časová složitost triangulace an n-vrcholový polygon s díry má Ω (n log n) dolní mez algebraicky výpočetní strom modely výpočtu.[1] Je možné vypočítat počet odlišných triangulací jednoduchého polygonu v polynomiálním čase pomocí dynamické programování, a (na základě tohoto algoritmu počítání) vygenerovat rovnoměrně náhodně triangulace v polynomiálním čase.[15] Počítání triangulací mnohoúhelníku s otvory je však # P-kompletní, takže je nepravděpodobné, že by to mohlo být provedeno v polynomiálním čase.[16]

Související problémy

Viz také

Reference

  1. ^ A b C d E Mark de Berg, Marc van Kreveld, Mark Overmars, a Otfried Schwarzkopf (2000), Výpočetní geometrie (2. přepracované vydání), Springer-Verlag, ISBN  3-540-65620-0CS1 maint: více jmen: seznam autorů (odkaz) Kapitola 3: Polygon Triangulation: str. 45–61.
  2. ^ Pickover, Clifford A., Matematická kniha, Sterling, 2009: str. 184.
  3. ^ Fournier, A.; Montuno, D. Y. (1984), „Triangulace jednoduchých polygonů a ekvivalentní problémy“, Transakce ACM v grafice, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN  0730-0301, S2CID  33344266
  4. ^ Toussaint, Godfried T. (1984), "Nový lineární algoritmus pro triangulaci monotónních polygonů," Písmena pro rozpoznávání vzorů, 2 (Březen): 155–158.
  5. ^ Meisters, G. H., "Mnohoúhelníky mají uši "American Mathematical Monthly 82 (1975). 648–651
  6. ^ ElGindy, H .; Everett, H .; Toussaint, G. T. (1993). "Krájení ucha pomocí švestek a hledání". Písmena pro rozpoznávání vzorů. 14 (9): 719–722. doi:10.1016 / 0167-8655 (93) 90141-r.
  7. ^ Tarjan, Robert E.; Van Wyk, Christopher J. (1988), „An O (n log log n) -time algoritmus pro triangulaci jednoduchého mnohoúhelníku ", SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX  10.1.1.186.5949, doi:10.1137/0217010, PAN  0925194.
  8. ^ Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), „Polygon triangulace v O (n log log n) čas s jednoduchými datovými strukturami ", Diskrétní a výpočetní geometrie, 7 (4): 329–346, doi:10.1007 / BF02187846, PAN  1148949.
  9. ^ Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), „Rychlý algoritmus Las Vegas pro triangulaci jednoduchého mnohoúhelníku“, Diskrétní a výpočetní geometrie, 4 (5): 423–432, doi:10.1007 / BF02187741.
  10. ^ Seidel, Raimund (1991), „Jednoduchý a rychlý přírůstkový randomizovaný algoritmus pro výpočet trapézových rozkladů a pro trojúhelníkové polygony“, Výpočetní geometrie: Teorie a aplikace, 1: 51–64, doi:10.1016/0925-7721(91)90012-4
  11. ^ Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), „Randomizované paralelní algoritmy pro lichoběžníkové diagramy“, International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142 / S0218195992000081, PAN  1168952.
  12. ^ Chazelle, Bernard (1991), „Triangulace jednoduchého polygonu v lineárním čase“, Diskrétní a výpočetní geometrie, 6 (3): 485–524, doi:10.1007 / BF02574703, ISSN  0179-5376
  13. ^ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), „Randomizovaný algoritmus pro triangulaci jednoduchého polygonu v lineárním čase“, Diskrétní a výpočetní geometrie, 26 (2): 245–265, doi:10.1007 / s00454-001-0027-x, ISSN  0179-5376
  14. ^ Li, Fajie; Klette, Reinhard (2011), Euklidovské nejkratší cesty, Springer, doi:10.1007/978-1-4471-2256-2, ISBN  978-1-4471-2255-5.
  15. ^ Epstein, Peter; Pytel, Jörg-Rüdiger (1994), „Generování náhodných triangulací“, Transakce ACM na modelování a počítačové simulaci, 4 (3): 267–278, doi:10.1145/189443.189446, S2CID  14039662
  16. ^ Eppstein, David (2019), „Počítání polygonových triangulací je těžké“, Proc. 35. Int. Symp. Výpočetní geometrie„Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, s. 33: 1–33: 17, arXiv:1903.04737, doi:10.4230 / LIPIcs.SoCG.2019.33, S2CID  75136891

externí odkazy