Булеві операції над многокутниками
Бу́леві опера́ції над многоку́тниками або фігу́рами — це набір булевих операцій (AND, OR, NOT, XOR, …) над одним або декількома наборами многокутників у комп'ютерній графіці. Ці набори операцій поширені в комп'ютерній графіці, САПР та в проєктуванні електронних схем (фізичне розташування елементів інтегральних схем та програми перевірки).
- Алгоритм відсікання Ґрайнера — Горманна[en]
- Алгоритм відсікання Ватті[en]
- Алгоритм Сазерленда — Годжмана[en] (алгоритм для часткового випадку)
- Алгоритм Вайлера — Атертона (алгоритм для часткового випадку)
Ранні алгоритми булевих операцій із многокутниками ґрунтувалися на бітових мапах. Використання бітових мап у моделюванні багатокутних фігур та операціях над ними має багато недоліків. Один з недоліків — може знадобитися дуже багато пам'яті, оскільки роздільність малюнка многокутника пропорційна числу пікселів, що використовуються для подання багатокутників. Що більша роздільність зображення, то більше біт потрібно зберігати в пам'яті.
Сучасне втілення булевих операцій над многокутниками використовує алгоритми замітання площини (або алгоритм замітання прямою). Список статей, що використовують алгоритм замітання прямою для булевих операцій над многокутниками, наведено в списку літератури.
Булеві операції над опуклими та монотонними многокутниками з однаковими напрямками можна здійснити за лінійний час[1].
- Алгебра логіки
- Обчислювальна геометрія
- Конструктивна суцільна геометрія
- General Polygon Clipper[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.
- UIUC Computational Geometry Pages
- Constructive planar geometry від Дейва Еберлі (Dave Eberly).
- Алгоритми та програми
- Михайло Леонов склав порівняння алгоритмів відсікання багатокутників. (англ.)
- Ангус Джонсон склав також порівняння трьох бібліотек відсікання. (англ.)
- Компанія SINED GmbH склала порівняння продуктивності та використання пам'яті трьох алгоритмів відсікання. (англ.)
- Порівняння 5 бібліотек відсікання rogue-modron.blogspot.com (англ.)
- sgCore C++/C# Бібліотека — комерційна бібліотека для 3-вимірних булевих операцій.
- comp.graphics.algorithms FAQ — розв'язування математичних задач із дво- та тривимірними многокутниками.
- gfxpoly Маттіаса Крамма — вільно поширювана бібліотека на C для 2D многокутників (ліцензія BSD).
- Boolean Клааса Голверда — бібліотека на C++ для 2D многокутників.
- Polypack Девіда Кеннісона — бібліотека на Фортрані, заснована на алгоритмі Ватті.
- Clippoly Кламера Шатте — програма відсікання многокутника, написана на C++.
- poly_Boolean Михайла Леонова — бібліотека на C++, що розширює алгоритм Шатта.
- Clipper Ангуса Джонсона — вільно поширювана бібліотека з відкритим кодом (написана на Delphi, C++ і C#), заснована на алгоритмі відсікання Ватті[en].
- GeoLib — комерційна бібліотека, доступна на C++ та C#.
- GPC Алана Марта — бібліотека «Загальне відсікання многокутника».
- PolygonLib — бібліотеки на C++ та COM для 2D-многокутників (оптимізована для великих множин многокутників, вбудовано просторовий індекс).