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

Алгоритми

(алгоритм для часткового випадку) Алгоритм Вайлера — Атертона (алгоритм для часткового випадку)

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

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

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

Див. також Алгебра логіки Обчислювальна геометрія Конструктивна суцільна геометрія (Загальне Відсікання Многокутника), бібліотека на 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#), заснована на . GeoLib — комерційна бібліотека, доступна на C++ та C#. GPC Алана Марта — бібліотека «Загальне відсікання многокутника». PolygonLib — бібліотеки на C++ та COM для 2D-многокутників (оптимізована для великих множин многокутників, вбудовано просторовий індекс).