Бу́леві опера́ції над многоку́тниками або фігу́рами — це набір булевих операцій (AND, OR, NOT, XOR, …) над одним або декількома наборами многокутників у комп'ютерній графіці. Ці набори операцій поширені в комп'ютерній графіці, САПР та в проєктуванні електронних схем (фізичне розташування елементів інтегральних схем та програми перевірки).
Алгоритми
- [en]
- [en]
- [en] (алгоритм для часткового випадку)
- (алгоритм для часткового випадку)
Застосування в програмуванні
Ранні алгоритми булевих операцій із многокутниками ґрунтувалися на бітових мапах. Використання бітових мап у моделюванні багатокутних фігур та операціях над ними має багато недоліків. Один з недоліків — може знадобитися дуже багато пам'яті, оскільки роздільність малюнка многокутника пропорційна числу пікселів, що використовуються для подання багатокутників. Що більша роздільність зображення, то більше біт потрібно зберігати в пам'яті.
Сучасне втілення булевих операцій над многокутниками використовує алгоритми замітання площини (або алгоритм замітання прямою). Список статей, що використовують алгоритм замітання прямою для булевих операцій над многокутниками, наведено в списку літератури.
Булеві операції над опуклими та монотонними многокутниками з однаковими напрямками можна здійснити за лінійний час.
Див. також
- Алгебра логіки
- Обчислювальна геометрія
- Конструктивна суцільна геометрія
- [en] (Загальне Відсікання Многокутника), бібліотека на C, що обчислює результат операції відсікання
- Конструктивна блокова геометрія, метод визначення тривимірних фігур з використанням аналогічних операцій
Примітки
- Katz, Overmars, Sharir, 1992, с. 223–234.
Література
- Matthew J. Katz, Mark H. Overmars, Micha Sharir. Efficient hidden surface removal for objects with small union size // Computational Geometry (journal). — 1992. — Т. 2, вип. 4. — С. 223–234. — DOI: .
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algorithms and Applications. — Second Edition. — 2000.
- Jon Louis Bentley, Thomas A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections // IEEE Transactions on Computers. — 1979. — Т. C-28, вип. 9. — С. 643–647.
- Jon Louis Bentley, Derick Wood. An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles // IEEE Transactions on Computers. — 1980. — Т. C-29, вип. 7. — С. 571–577.
- Ulrich Lauther. 18th Design Automation Conference. — 1981. — С. 555–562.
- James A. Wilmore. 18th Design Automation Conference. — 1981. — С. 571–579.
- J. Nievergelt, F. P. Preparata. Plane-Sweep Algorithms for Intersecting Geometric Figures // Communications of the ACM. — 1982. — Т. 25, вип. 10. — С. 739–747. — DOI: .
- =Thomas Ottmann, Peter Widmayer, and Derick Wood. Computer Vision, Graphics, and Image Processing. — 1985. — Т. 30. — С. 249–268.
Посилання
- від Дейва Еберлі (Dave Eberly).
- Алгоритми та програми
- Михайло Леонов склав . (англ.)
- Ангус Джонсон склав також порівняння трьох бібліотек відсікання. (англ.)
- Компанія SINED GmbH склала порівняння продуктивності та використання пам'яті трьох алгоритмів відсікання. (англ.)
- Порівняння 5 бібліотек відсікання rogue-modron.blogspot.com (англ.)
- sgCore C++/C# Бібліотека — комерційна бібліотека для 3-вимірних булевих операцій.
- comp.graphics.algorithms FAQ — розв'язування математичних задач із дво- та тривимірними многокутниками.
- gfxpoly Маттіаса Крамма — вільно поширювана бібліотека на C для 2D многокутників (ліцензія BSD).
- Boolean Клааса Голверда — бібліотека на C++ для 2D многокутників.
- Девіда Кеннісона — бібліотека на Фортрані, заснована на алгоритмі Ватті.
- Clippoly Кламера Шатте — програма відсікання многокутника, написана на C++.
- Михайла Леонова — бібліотека на C++, що розширює алгоритм Шатта.
- Clipper Ангуса Джонсона — вільно поширювана бібліотека з відкритим кодом (написана на Delphi, C++ і C#), заснована на [en].
- GeoLib — комерційна бібліотека, доступна на C++ та C#.
- GPC Алана Марта — бібліотека «Загальне відсікання многокутника».
- PolygonLib — бібліотеки на C++ та COM для 2D-многокутників (оптимізована для великих множин многокутників, вбудовано просторовий індекс).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Bu levi opera ciyi nad mnogoku tnikami abo figu rami ce nabir bulevih operacij AND OR NOT XOR nad odnim abo dekilkoma naborami mnogokutnikiv u komp yuternij grafici Ci nabori operacij poshireni v komp yuternij grafici SAPR ta v proyektuvanni elektronnih shem fizichne roztashuvannya elementiv integralnih shem ta programi perevirki Rizni bulevi operaciyi nad mnozhinami sho nalezhat dvom figuram diagrami Venna Algoritmi en en en algoritm dlya chastkovogo vipadku algoritm dlya chastkovogo vipadku Zastosuvannya v programuvanniRanni algoritmi bulevih operacij iz mnogokutnikami gruntuvalisya na bitovih mapah Vikoristannya bitovih map u modelyuvanni bagatokutnih figur ta operaciyah nad nimi maye bagato nedolikiv Odin z nedolikiv mozhe znadobitisya duzhe bagato pam yati oskilki rozdilnist malyunka mnogokutnika proporcijna chislu pikseliv sho vikoristovuyutsya dlya podannya bagatokutnikiv Sho bilsha rozdilnist zobrazhennya to bilshe bit potribno zberigati v pam yati Suchasne vtilennya bulevih operacij nad mnogokutnikami vikoristovuye algoritmi zamitannya ploshini abo algoritm zamitannya pryamoyu Spisok statej sho vikoristovuyut algoritm zamitannya pryamoyu dlya bulevih operacij nad mnogokutnikami navedeno v spisku literaturi Bulevi operaciyi nad opuklimi ta monotonnimi mnogokutnikami z odnakovimi napryamkami mozhna zdijsniti za linijnij chas Div takozhAlgebra logiki Obchislyuvalna geometriya Konstruktivna sucilna geometriya en Zagalne Vidsikannya Mnogokutnika biblioteka na C sho obchislyuye rezultat operaciyi vidsikannya Konstruktivna blokova geometriya metod viznachennya trivimirnih figur z vikoristannyam analogichnih operacijPrimitkiKatz Overmars Sharir 1992 s 223 234 LiteraturaMatthew J Katz Mark H Overmars Micha Sharir Efficient hidden surface removal for objects with small union size Computational Geometry journal 1992 T 2 vip 4 S 223 234 DOI 10 1016 0925 7721 92 90024 M Mark de Berg Marc van Kreveld Mark Overmars Otfried Schwarzkopf Algorithms and Applications Second Edition 2000 Jon Louis Bentley Thomas A Ottmann Algorithms for Reporting and Counting Geometric Intersections IEEE Transactions on Computers 1979 T C 28 vip 9 S 643 647 Jon Louis Bentley Derick Wood An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles IEEE Transactions on Computers 1980 T C 29 vip 7 S 571 577 Ulrich Lauther 18th Design Automation Conference 1981 S 555 562 James A Wilmore 18th Design Automation Conference 1981 S 571 579 J Nievergelt F P Preparata Plane Sweep Algorithms for Intersecting Geometric Figures Communications of the ACM 1982 T 25 vip 10 S 739 747 DOI 10 1145 358656 358681 Thomas Ottmann Peter Widmayer and Derick Wood Computer Vision Graphics and Image Processing 1985 T 30 S 249 268 Posilannyavid Dejva Eberli Dave Eberly Algoritmi ta programi Mihajlo Leonov sklav angl Angus Dzhonson sklav takozh porivnyannya troh bibliotek vidsikannya angl Kompaniya SINED GmbH sklala porivnyannya produktivnosti ta vikoristannya pam yati troh algoritmiv vidsikannya angl Porivnyannya 5 bibliotek vidsikannya rogue modron blogspot com angl sgCore C C Biblioteka komercijna biblioteka dlya 3 vimirnih bulevih operacij comp graphics algorithms FAQ rozv yazuvannya matematichnih zadach iz dvo ta trivimirnimi mnogokutnikami gfxpoly Mattiasa Kramma vilno poshiryuvana biblioteka na C dlya 2D mnogokutnikiv licenziya BSD Boolean Klaasa Golverda biblioteka na C dlya 2D mnogokutnikiv Devida Kennisona biblioteka na Fortrani zasnovana na algoritmi Vatti Clippoly Klamera Shatte programa vidsikannya mnogokutnika napisana na C Mihajla Leonova biblioteka na C sho rozshiryuye algoritm Shatta Clipper Angusa Dzhonsona vilno poshiryuvana biblioteka z vidkritim kodom napisana na Delphi C i C zasnovana na en GeoLib komercijna biblioteka dostupna na C ta C GPC Alana Marta biblioteka Zagalne vidsikannya mnogokutnika PolygonLib biblioteki na C ta COM dlya 2D mnogokutnikiv optimizovana dlya velikih mnozhin mnogokutnikiv vbudovano prostorovij indeks