Booleske operationer på polygoner
Boolske operationer på polygoner eller former er et sæt boolske operationer (AND, OR, NOT, XOR, ...) på et eller flere sæt polygoner i computergrafik. Disse sæt operationer er meget brugt i computergrafik , CAD og i elektronisk kredsløbsdesign (det fysiske layout af integrerede kredsløbselementer og verifikationsprogrammer).
Algoritmer
- Greiner-Hormann klipningsalgoritme
- Watti clipping algoritme
- Sutherland–Hodgman algoritme (algoritme for et særligt tilfælde)
- Wyler-Atherton algoritme (algoritme til et særligt tilfælde)
Applikationer i programmering
Tidlige algoritmer for booleske operationer på polygoner var baseret på bitmaps . Brugen af bitmaps i modelleringen af polygonale former og operationer på dem har mange ulemper. En ulempe er, at det kan tage meget hukommelse, fordi opløsningen af polygonmønsteret er proportional med antallet af pixels , der bruges til at repræsentere polygonerne. Jo højere billedopløsningen er, jo flere bits skal der gemmes i hukommelsen.
Den moderne inkarnation af booleske operationer på polygoner bruger plane sweeping algoritmer (eller sweeping line algoritmer ). En liste over papirer, der anvender algoritmen for fejende linje til booleske operationer på polygoner, kan findes i bibliografien nedenfor.
Booleske operationer på konvekse polygoner og monotone polynomier med samme retninger kan udføres i lineær tid [1] .
Se også
Noter
- ↑ Katz, Overmars, Sharir, 1992 , s. 223-234.
Litteratur
- Matthew J. Katz, Mark H. Overmars, Micha Sharir. Effektiv fjernelse af skjult overflade for objekter med lille unionsstørrelse // Computational Geometry (journal). - 1992. - Vol. 2 , udgave. 4 . — S. 223–234 . - doi : 10.1016/0925-7721(92)90024-M .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algoritmer og applikationer. - Anden version. - 2000.
- Jon Louis Bentley, Thomas A. Ottmann. Algoritmer til rapportering og optælling af geometriske kryds // IEEE-transaktioner på computere. - 1979. - T. C-28 , no. 9 . — S. 643–647 .
- Jon Louis Bentley, Derick Wood. En Optimal Worst Case-algoritme til rapportering af skæringspunkter mellem rektangler // IEEE-transaktioner på computere. - 1980. - T. C-29 , no. 7 . — S. 571–577 .
- Ulrich Lauther. 18. Design Automation Conference. - 1981. - S. 555-562.
- James A. Wilmore. 18. Design Automation Conference. - 1981. - S. 571-579.
- J. Nievergelt, F. P. Preparata. Plane-sweep-algoritmer til krydsende geometriske figurer // Kommunikation af ACM. - 1982. - T. 25 , no. 10 . — S. 739–747 . - doi : 10.1145/358656.358681 .
- =Thomas Ottmann, Peter Widmayer og Derick Wood. Computersyn, grafik og billedbehandling. - 1985. - T. 30. - S. 249-268.
Links
Algoritmer og programmer
- Mikhail Leonov kompilerede en sammenligning af polygonklipningsalgoritmer .
- Angus Johnson kompilerede også en sammenligning af de tre udklipningsbiblioteker .
- SINED GmbH har udarbejdet en sammenligning af ydeevnen og hukommelsesforbruget af tre clipping-algoritmer .
- Sammenligning af 5 udskæringsbiblioteker rogue-modron.blogspot.com
- Kommercielt bibliotek til 3D booleske operationer: sgCore C++/C# .
- comp.graphics.algorithms FAQ , Løsning af matematiske problemer med 2D og 3D polygoner.
- gfxpoly af Matthias Kramm, et gratis C-bibliotek til 2D-polygoner (BSD-licens).
- Boolean bibliotek af Klaas Holwerd, C++ bibliotek for 2D polygoner.
- Polypack af David Kennison, et Fortran-bibliotek baseret på Wattis algoritme.
- Clippoly af Clamer Schatte, et polygon klipningsprogram skrevet i C++.
- poly_Boolean af Mikhail Leonov, et C++-bibliotek, der udvider Shutt-algoritmen.
- Clipper af Angus Johnson, et gratis open source-bibliotek (skrevet i Delphi, C++ og C#) baseret på Wattis klippealgoritme .
- GeoLib , et kommercielt bibliotek tilgængeligt i C++ og C#.
- Alan Marth GPC , Common Polygon Clipping Library.
- PolygonLib , C++ og COM biblioteker til 2D polygoner (optimeret til store polygonsæt, indbygget rumligt indeks).