Булевы операции над многоугольниками или фигурами — это набор булевых операций (AND, OR, NOT, XOR, ...) с одним или несколькими наборами многоугольников в компьютерной графике. Эти наборы операций широко используются в компьютерной графике, САПР и в проектировании электронных схем (физическое расположение элементов интегральных схем и программы проверки).
Алгоритмы
- Алгоритм отсечения Грайнера – Хорманна
- Алгоритм отсечения Ватти
- Алгоритм Сазерленда – Ходжмана (алгоритм для частного случая)
- Алгоритм Уайлера — Атертона (алгоритм для частного случая)
Применение в программировании
Ранние алгоритмы булевых операций с многоугольниками основывались на битовых картах. Использование битовых карт в моделировании многоугольных фигур и операциях над ними имеет много недостатков. Один из недостатков — может потребоваться очень много памяти, поскольку разрешение рисунка многоугольника пропорционально числу пикселей, используемых для представления многоугольников. Чем больше разрешение изображения, тем большее число бит требуется хранить в памяти.
Современная воплощение булевых операций над многоугольниками использует алгоритмы заметания плоскости (или алгоритмы заметающей прямой). Список статей, использующих алгоритм заметающей прямой для булевых операций над многоугольниками, можно найти ниже в списке литературы.
Булевы операции над выпуклыми многоугольниками и монотонными многочленами с одинаковыми направлениями можно осуществить за линейное время.