Booleovské operace na polygonech

Booleovské operace na mnohoúhelnících nebo tvarech jsou sadou booleovských operací (AND, OR, NOT, XOR, ...) na jedné nebo více sadách mnohoúhelníků v počítačové grafice. Tyto sady operací jsou široce používány v počítačové grafice , CADu a v návrhu elektronických obvodů (fyzické rozložení prvků integrovaných obvodů a verifikačních programů).

Algoritmy

• Algoritmus ořezávání Greiner–Hormann
• Wattiho ořezový algoritmus
• Sutherland–Hodgman algorithm (algoritmus pro speciální případ)
• Wyler-Athertonův algoritmus (algoritmus pro speciální případ)

Aplikace v programování

Rané algoritmy pro booleovské operace na polygonech byly založeny na bitmapách . Použití bitmap při modelování polygonálních tvarů a operací s nimi má mnoho nevýhod. Jednou nevýhodou je, že může zabírat hodně paměti, protože rozlišení polygonového vzoru je úměrné počtu pixelů použitých k reprezentaci polygonů. Čím vyšší je rozlišení obrazu, tím více bitů je potřeba uložit do paměti.

Moderní inkarnace booleovských operací na mnohoúhelnících používá algoritmy plošného zametání (nebo algoritmy zametání čar ). Seznam článků používajících algoritmus sweeping line pro booleovské operace na polygonech lze nalézt v seznamu literatury níže.

Booleovské operace na konvexních polygonech a monotónních polynomech se stejnými směry lze provádět v lineárním čase [1] .

Viz také

• Algebra logiky
• Výpočetní geometrie
• Konstruktivní geometrie těles
• General Polygon Clipper (General Polygon Clipping), knihovna C, která vypočítává výsledek operace oříznutí
• Konstruktivní tělesová geometrie , metoda pro definování trojrozměrných obrazců pomocí podobných operací

Poznámky

1. ↑ Katz, Overmars, Sharir, 1992 , str. 223–234.

Literatura

• Matthew J. Katz, Mark H. Overmars, Micha Sharir. Efektivní odstranění skrytého povrchu pro objekty s malou sjednocenou velikostí // Computational Geometry (žurnál). - 1992. - Vol. 2 , vydání. 4 . — S. 223–234 . - doi : 10.1016/0925-7721(92)90024-M .
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algoritmy a aplikace. - Druhé vydání. — 2000.
• Jon Louis Bentley, Thomas A. Ottmann. Algoritmy pro hlášení a počítání geometrických průniků // IEEE transakce na počítačích. - 1979. - T. C-28 , no. 9 . — S. 643–647 .
• Jon Louis Bentley, Derick Wood. Algoritmus optimálního nejhoršího případu pro hlášení průniků obdélníků // IEEE transakce na počítačích. - 1980. - T. C-29 , no. 7 . — S. 571–577 .
• Ulrich Lauther. 18. konference Design Automation. - 1981. - S. 555-562.
• James A. Wilmore. 18. konference Design Automation. - 1981. - S. 571-579.
• J. Nievergelt, F. P. Preparata. Algoritmy rovinného rozmítání pro protínající se geometrické obrazce // Komunikace ACM. - 1982. - T. 25 , no. 10 . — S. 739–747 . - doi : 10.1145/358656.358681 .
• =Thomas Ottmann, Peter Widmayer a Derick Wood. Počítačové vidění, grafika a zpracování obrazu. - 1985. - T. 30. - S. 249-268.

Odkazy

• Stránky výpočetní geometrie UIUC
• Konstruktivní rovinná geometrie od Davea Eberlyho.

• Michail Leonov sestavil srovnání polygonových ořezových algoritmů .
• Angus Johnson také sestavil srovnání tří knihoven výstřižků .
• Společnost SINED GmbH sestavila srovnání výkonu a využití paměti tří ořezových algoritmů .
• Srovnání 5 ořezových knihoven rogue-modron.blogspot.com
• Komerční knihovna pro 3D booleovské operace: sgCore C++/C# .
• comp.graphics.algorithms FAQ , Řešení matematických problémů s 2D a 3D polygony.
• gfxpoly od Matthiase Kramma, bezplatná knihovna C pro 2D polygony (licence BSD).
• Booleovská knihovna od Klaase Holwerda, C++ knihovna pro 2D polygony.
• Polypack od Davida Kennisona, Fortranská knihovna založená na Wattiho algoritmu.
• Clippoly od Clamera Schatte, program pro ořezávání mnohoúhelníků napsaný v C++.
• poly_Boolean od Michaila Leonova, knihovna C++ rozšiřující Shuttův algoritmus.
• Clipper od Anguse Johnsona, bezplatná open source knihovna (napsaná v Delphi, C++ a C#) založená na Wattiho ořezávacím algoritmu .
• GeoLib , komerční knihovna dostupná v C++ a C#.
• Alan Marth GPC , Common Polygon Clipping Library.
• Knihovny PolygonLib , C++ a COM pro 2D polygony (optimalizované pro velké sady polygonů, vestavěný prostorový index).