Booleska operationer på polygoner

Booleska operationer på polygoner eller former är en uppsättning booleska operationer (AND, OR, NOT, XOR, ...) på en eller flera uppsättningar polygoner i datorgrafik. Dessa uppsättningar av operationer används ofta i datorgrafik , CAD och i elektronisk kretsdesign (den fysiska layouten av integrerade kretselement och verifieringsprogram).

Algoritmer

• Greiner–Hormann urklippsalgoritm
• Watti urklippsalgoritm
• Sutherland–Hodgman algorithm (algoritm för ett specialfall)
• Wyler-Atherton- algoritm (algoritm för ett specialfall)

Applikationer i programmering

Tidiga algoritmer för booleska operationer på polygoner baserades på bitmappar . Användningen av bitmappar vid modellering av polygonala former och operationer på dem har många nackdelar. En nackdel är att det kan ta mycket minne eftersom upplösningen av polygonmönstret är proportionell mot antalet pixlar som används för att representera polygonerna. Ju högre bildupplösning, desto fler bitar måste lagras i minnet.

Den moderna inkarnationen av booleska operationer på polygoner använder plansvepningsalgoritmer (eller svepande linjealgoritmer ). En lista över papper som använder den svepande linjealgoritmen för booleska operationer på polygoner finns i bibliografin nedan.

Booleska operationer på konvexa polygoner och monotona polynom med samma riktningar kan utföras i linjär tid [1] .

Se även

• Algebra av logik
• Beräkningsgeometri
• Konstruktiv solid geometri
• General Polygon Clipper (General Polygon Clipping), ett C-bibliotek som beräknar resultatet av en klippning
• Konstruktiv solid geometri , en metod för att definiera tredimensionella figurer med liknande operationer

Anteckningar

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

Litteratur

• Matthew J. Katz, Mark H. Overmars, Micha Sharir. Effektiv borttagning av dold yta för objekt med liten unionsstorlek // Computational Geometry (journal). - 1992. - Vol. 2 , nummer. 4 . — S. 223–234 . - doi : 10.1016/0925-7721(92)90024-M .
• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algoritmer och applikationer. - Andra upplagan. — 2000.
• Jon Louis Bentley, Thomas A. Ottmann. Algoritmer för rapportering och räkning av geometriska korsningar // IEEE-transaktioner på datorer. - 1979. - T. C-28 , nr. 9 . — S. 643–647 .
• Jon Louis Bentley, Derick Wood. En Optimal Worst Case-algoritm för att rapportera skärningspunkter mellan rektanglar // IEEE-transaktioner på datorer. - 1980. - T. C-29 , nr. 7 . — S. 571–577 .
• Ulrich Lauther. 18:e Design Automation Conference. - 1981. - S. 555-562.
• James A. Wilmore. 18:e Design Automation Conference. - 1981. - S. 571-579.
• J. Nievergelt, F. P. Preparata. Plane-sweep-algoritmer för korsande geometriska figurer // Kommunikation av ACM. - 1982. - T. 25 , nr. 10 . — S. 739–747 . - doi : 10.1145/358656.358681 .
• =Thomas Ottmann, Peter Widmayer och Derick Wood. Datorseende, grafik och bildbehandling. - 1985. - T. 30. - S. 249-268.

Länkar

• UIUC Computational Geometry Pages
• Konstruktiv plan geometri , av Dave Eberly.

• Mikhail Leonov sammanställde en jämförelse av polygonklippningsalgoritmer .
• Angus Johnson sammanställde också en jämförelse av de tre urklippsbiblioteken .
• SINED GmbH har sammanställt en jämförelse av prestanda och minnesanvändning för tre urklippsalgoritmer .
• Jämförelse av 5 urklippsbibliotek rogue-modron.blogspot.com
• Kommersiellt bibliotek för booleska 3D-operationer: sgCore C++/C# .
• comp.graphics.algorithms FAQ , Lösa matematiska problem med 2D- och 3D-polygoner.
• gfxpoly av Matthias Kramm, ett gratis C-bibliotek för 2D-polygoner (BSD-licens).
• Booleskt bibliotek av Klaas Holwerd, C++-bibliotek för 2D-polygoner.
• Polypack av David Kennison, ett Fortran-bibliotek baserat på Wattis algoritm.
• Clippoly av Clamer Schatte, ett polygonklippprogram skrivet i C++.
• poly_Boolean av Mikhail Leonov, ett C++-bibliotek som utökar Shutt-algoritmen.
• Clipper av Angus Johnson, ett gratis bibliotek med öppen källkod (skrivet i Delphi, C++ och C#) baserat på Wattis urklippsalgoritm .
• GeoLib , ett kommersiellt bibliotek tillgängligt i C++ och C#.
• Alan Marth GPC , Common Polygon Clipping Library.
• PolygonLib , C++ och COM bibliotek för 2D polygoner (optimerad för stora polygonuppsättningar, inbyggt rumsligt index).