Булеві операції над многокутниками

Бу́леві опера́ції над многоку́тниками або фігу́рами — це набір булевих операцій (AND, OR, NOT, XOR, …) над одним або декількома наборами многокутників у комп'ютерній графіці. Ці набори операцій поширені в комп'ютерній графіці, САПР та в проєктуванні електронних схем (фізичне розташування елементів інтегральних схем та програми перевірки).

• Алгоритм відсікання Ґрайнера — Горманна^[en]
• Алгоритм відсікання Ватті^[en]
• Алгоритм Сазерленда — Годжмана^[en] (алгоритм для часткового випадку)
• Алгоритм Вайлера — Атертона (алгоритм для часткового випадку)

Ранні алгоритми булевих операцій із многокутниками ґрунтувалися на бітових мапах. Використання бітових мап у моделюванні багатокутних фігур та операціях над ними має багато недоліків. Один з недоліків — може знадобитися дуже багато пам'яті, оскільки роздільність малюнка многокутника пропорційна числу пікселів, що використовуються для подання багатокутників. Що більша роздільність зображення, то більше біт потрібно зберігати в пам'яті.

Сучасне втілення булевих операцій над многокутниками використовує алгоритми замітання площини (або алгоритм замітання прямою). Список статей, що використовують алгоритм замітання прямою для булевих операцій над многокутниками, наведено в списку літератури.

Булеві операції над опуклими та монотонними многокутниками з однаковими напрямками можна здійснити за лінійний час^[1].

• Алгебра логіки
• Обчислювальна геометрія
• Конструктивна суцільна геометрія
• General Polygon Clipper^[en] (Загальне Відсікання Многокутника), бібліотека на C, що обчислює результат операції відсікання
• Конструктивна блокова геометрія, метод визначення тривимірних фігур з використанням аналогічних операцій

• 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-многокутників (оптимізована для великих множин многокутників, вбудовано просторовий індекс).