Booleovské operace s polygony - Boolean operations on polygons

Booleovské operace s polygony jsou souborem Booleovské operace (AND, OR, NOT, XOR, ...) pracující na jedné nebo více sadách mnohoúhelníky v počítačové grafice. Tyto sady operací jsou široce používány v počítačová grafika, CAD a v EDA (v integrovaný obvod software pro fyzický návrh a ověření).

Různé logické operace

Algoritmy

Greiner – Hormann ořezový algoritmus
Vattiho ořezový algoritmus
Algoritmus Sutherland – Hodgman (speciální případový algoritmus)
Weiler – Athertonův ořezový algoritmus (speciální případový algoritmus)

Použití v softwaru

Rané algoritmy pro booleovské operace s polygony byly založeny na použití bitmapy. Použití bitmap v modelování polygonových tvarů má mnoho nevýhod. Jednou z nevýhod je, že využití paměti může být velmi velké, protože rozlišení polygonů je úměrné počtu bitů použitých k reprezentaci polygonů. Čím vyšší rozlišení je požadováno, tím více je požadován počet bitů.

Moderní implementace pro booleovské operace s polygony mají tendenci používat algoritmy tažení roviny (nebo Algoritmy tažení linky ). Seznam příspěvků využívajících algoritmy rovinného tažení pro booleovské operace s polygony najdete v odkazech níže.

Booleovské operace zapnuty konvexní polygony a monotónní polygony stejného směru lze provádět v lineární čas.^[1]

Viz také

Konstruktivní objemová geometrie, metoda definování trojrozměrných tvarů pomocí podobné sady operací

Poznámky

^ Katz, Matthew J .; Overmars, Mark H .; Sharir, Micha (1992), „Efektivní odstranění skrytého povrchu pro objekty s malou velikostí spojení“, Výpočetní geometrie: Teorie a aplikace, 2 (4): 223–234, doi:10.1016 / 0925-7721 (92) 90024-M.

Bibliografie

Mark de Berg, Marc van Kreveld, Mark Overmars a Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000
Jon Louis Bentley a Thomas A. Ottmann, Algoritmy pro hlášení a počítání geometrických průsečíků, IEEE Transaction on Computers, sv. C-28, č. 9, září 1979, s. 643–647
Jon Louis Bentley a Derick Wood, Optimální algoritmus nejhoršího případu pro hlášení průsečíků obdélníků, IEEE Transaction on Computers, sv. C-29. Č. 7, červenec 1980, str. 571–577
Ulrich Lauther, Algoritmus O (N log N) pro booleovské operace s maskami, 18. konference Design Automation Conference, 1981, s. 555–562
James A. Wilmore, Efektivní booleovské operace na IC maskách, 18. konference Design Automation Conference, 1981, s. 571–579
Nievergelt, J .; Preparata, F. P. (říjen 1982). "Algoritmy tažení rovinou pro protínající se geometrické obrazce". Komunikace ACM. 25 (10): 739–747. CiteSeerX 10.1.1.83.3275. doi:10.1145/358656.358681.
Thomas Ottmann, Peter Widmayer a Derick Wood, “Rychlý algoritmus pro booleovské maskování „Počítačové vidění, grafika a zpracování obrazu, 30, 1985, str. 249–268

Viz také

Booleova algebra
Výpočetní geometrie
Konstruktivní objemová geometrie
Zpracování geometrie
Obecné mnohoúhelník Clipper, knihovna C, která počítá výsledky operací ořezávání

externí odkazy

Stránky výpočetní geometrie UIUC
Konstrukční rovinná geometrie, od Davea Eberlyho.

Software

Michael Leonov sestavil a srovnání nůžek na mnohoúhelníky.
Angus Johnson má také porovnal tři ořezové knihovny.
SINED GmbH má porovnal výkon a využití paměti tří zastřihovačů mnohoúhelníků.
Porovnání 5 ořezových knihoven na rogue-modron.blogspot.com
Komerční knihovna pro 3D booleovské operace: Knihovna sgCore C ++ / C #.
The Nejčastější dotazy ke comp.graphics.algorithms, řešení matematických úloh s 2D a 3D polygony.
Matthias Kramm gfxpoly, bezplatná knihovna C pro 2D polygony (licence BSD).
Klaase Holwerdy Booleovský, knihovna C ++ pro 2D polygony.
David Kennison Polypack, knihovna FORTRAN založená na algoritmu Vatti.
Klamer Schutte Clippoly, stroj na stříhání mnohoúhelníků napsaný v C ++.
Michael Leonov poly_Boolean, knihovna C ++, která rozšiřuje Schutteův algoritmus.
Angus Johnson Klipr, open-source freewarová knihovna (napsaná v Delphi, C ++ a C #), která je založena na Vattiho algoritmus.
GeoLib, komerční knihovna dostupná v C ++ a C #.
Alan Murta GPC, Obecná knihovna Polygon Clipper.
PolygonLib, C ++ a COM knihovny pro 2D polygony (optimalizované pro velké množiny polygonů, vestavěné prostorové indexy).

[1] Katz, Matthew J .; Overmars, Mark H .; Sharir, Micha (1992), „Efektivní odstranění skrytého povrchu pro objekty s malou velikostí spojení“, Výpočetní geometrie: Teorie a aplikace, 2 (4): 223–234, doi:10.1016 / 0925-7721 (92) 90024-M.

[1]