Boole-műveletek sokszögeken
A sokszögekre vagy alakzatokra vonatkozó logikai műveletek logikai műveletek halmaza (ÉS, VAGY, NEM, XOR, ...) a számítógépes grafika egy vagy több sokszöghalmazán . Ezeket a műveletsorokat széles körben használják a számítógépes grafikában , a CAD -ben és az elektronikus áramkörök tervezésében (az integrált áramköri elemek fizikai elrendezése és az ellenőrző programok).
Algoritmusok
- Greiner–Hormann vágóalgoritmus
- Watti vágási algoritmus
- Sutherland–Hodgman algoritmus (algoritmus speciális esetre)
- Wyler-Atherton algoritmus (algoritmus speciális esetre)
Alkalmazások a programozásban
A poligonokon végzett logikai műveletek korai algoritmusai bittérképeken alapultak . A sokszög alakzatok modellezésében és az azokon végzett műveletekben a bittérképek használata számos hátránnyal jár. Egyik hátránya, hogy sok memóriát igényelhet, mivel a sokszögmintázat felbontása arányos a sokszögek ábrázolásához használt pixelek számával. Minél nagyobb a képfelbontás, annál több bitet kell tárolni a memóriában.
A poligonokon végzett logikai műveletek modern megtestesülése síkseprő algoritmusokat (vagy söprővonal-algoritmusokat ) használ. Az alábbi bibliográfiában található azoknak a dolgozatoknak a listája, amelyek a sweeping line algoritmust használják a sokszögeken végzett logikai műveletekhez.
Konvex sokszögeken és monoton polinomokon azonos irányú logikai műveletek végrehajthatók lineáris időben [1] .
Lásd még
Jegyzetek
- ↑ Katz, Overmars, Sharir, 1992 , p. 223–234.
Irodalom
- Matthew J. Katz, Mark H. Overmars, Micha Sharir. Hatékony rejtett felület eltávolítása kis unióméretű objektumok esetén // Számítógépes geometria (napló). - 1992. - 2. kötet , szám. 4 . – S. 223–234 . - doi : 10.1016/0925-7721(92)90024-M .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algoritmusok és alkalmazások. - Második kiadás. – 2000.
- Jon Louis Bentley, Thomas A. Ottmann. Algoritmusok a geometriai metszéspontok jelentéséhez és számlálásához // IEEE-tranzakciók számítógépeken. - 1979. - T. C-28 , sz. 9 . – S. 643–647 .
- Jon Louis Bentley, Derick Wood. Optimális legrosszabb eset algoritmus a téglalapok metszéspontjainak jelentéséhez // IEEE-tranzakciók számítógépeken. - 1980. - T. C-29 , sz. 7 . – S. 571–577 .
- Ulrich Lauther. 18. Tervezőautomatizálási Konferencia. - 1981. - S. 555-562.
- James A. Wilmore. 18. Tervezőautomatizálási Konferencia. - 1981. - S. 571-579.
- J. Nievergelt, F. P. Preparata. Plane-Sweep Algorithms for Intersecting Geometric Figures // Az ACM kommunikációja. - 1982. - T. 25 , sz. 10 . – S. 739–747 . - doi : 10.1145/358656.358681 .
- = Thomas Ottmann, Peter Widmayer és Derick Wood. Számítógépes látás, grafika és képfeldolgozás. - 1985. - T. 30. - S. 249-268.
Linkek
Algoritmusok és programok
- Mikhail Leonov összeállította a sokszögkivágási algoritmusok összehasonlítását .
- Angus Johnson összeállította a három vágókönyvtár összehasonlítását is .
- A SINED GmbH három vágóalgoritmus teljesítményének és memóriahasználatának összehasonlítását állította össze .
- 5 vágókönyvtár összehasonlítása rogue-modron.blogspot.com
- Kereskedelmi könyvtár 3D logikai műveletekhez: sgCore C++/C# .
- comp.graphics.algorithms GYIK , Matematikai feladatok megoldása 2D és 3D sokszögekkel.
- gfxpoly, Matthias Kramm, egy ingyenes C-könyvtár 2D poligonokhoz (BSD licenc).
- Klaas Holwerd logikai könyvtára , C++ könyvtár 2D sokszögekhez.
- David Kennison Polypack, egy Watti algoritmusán alapuló Fortran könyvtár.
- Clippoly , Clamer Schatte, egy C++ nyelven írt sokszögvágó program.
- Mihail Leonov poly_Boolean, a Shutt algoritmust kiterjesztő C++ könyvtár.
- Angus Johnson Clipper , egy ingyenes nyílt forráskódú könyvtár (Delphi, C++ és C# nyelven írva), amely Watti vágóalgoritmusán alapul .
- GeoLib , egy C++ és C# nyelven elérhető kereskedelmi könyvtár.
- Alan Marth GPC , Common Polygon Clipping Library.
- PolygonLib , C++ és COM könyvtárak 2D poligonokhoz (nagy poligonkészletekhez optimalizálva, beépített térbeli index).