Бу́левы опера́ции над многоуго́льниками и́ли фигу́рами — это набор булевых операций (AND, OR, NOT, XOR, ...) с одним или несколькими наборами многоугольников в компьютерной графике. Эти наборы операций широко используются в компьютерной графике, САПР и в проектировании электронных схем (физическое расположение элементов интегральных схем и программы проверки).
Алгоритмы
(алгоритм для частного случая) Алгоритм Уайлера — Атертона (алгоритм для частного случая)
Применение в программировании Ранние алгоритмы булевых операций с многоугольниками основывались на битовых картах. Использование битовых карт в моделировании многоугольных фигур и операциях над ними имеет много недостатков. Один из недостатков — может потребоваться очень много памяти, поскольку разрешение рисунка многоугольника пропорционально числу пикселей, используемых для представления многоугольников. Чем больше разрешение изображения, тем большее число бит требуется хранить в памяти.
Современная воплощение булевых операций над многоугольниками использует алгоритмы заметания плоскости (или алгоритмы заметающей прямой). Список статей, использующих алгоритм заметающей прямой для булевых операций над многоугольниками, можно найти ниже в списке литературы.
Булевы операции над выпуклыми многоугольниками и с одинаковыми направлениями можно осуществить за линейное время.
См. также Алгебра логики Вычислительная геометрия Конструктивная сплошная геометрия (Общее Отсечение Многоугольника), библиотека на C, вычисляющая результат операции отсечения Конструктивная сплошная геометрия, метод определения трёхмерных фигур с использованием аналогичных операций
Примечания
Литература
Ссылки UIUC Computational Geometry Pages Constructive planar geometry, by Dave Eberly.
Алгоритмы и программы Михаил Леонов составил сравнение алгоритмов отсечения многоугольников. Ангус Джонсон составил также сравнение трёх библиотек отсечения. Компания SINED GmbH составила сравнение производительности и использования памяти трёх алгоритмов отсечения. Сравнение 5 библиотек отсечения rogue-modron.blogspot.com Коммерческая библиотека для 3-мерных булевых операций: sgCore C++/C# Библиотека. comp.graphics.algorithms FAQ, решения математических задач с 2D- и 3D-многоугольниками. gfxpoly Маттиаса Крамма, свободно распространяемая библиотека на C для 2D-многоугольников (лицензия BSD). Библиотека Boolean Клааса Холверда, C++ библиотека для 2D-многоугольников. Polypack Дэвида Кеннисона, библиотека на Фортране, основанная на алгоритме Ватти. Clippoly Кламера Шатте, программа отсечения многоугольника, написанная на C++. poly_Boolean Михаила Леонова, C++ library, расширяющая алгоритм Шатта. Clipper Ангуса Джонсона, свободно распрстраняемая библиотека с открытым кодом (написанная на Delphi, C++ и C#), основанная на . GeoLib, коммерческая библиотека, доступная на C++ и C#. GPC Алана Марта, библиотека «Общее Отсечение Многоугольника». PolygonLib, C++ и COM библиотеки для 2D-многоугольников (оптимизирована для больших множеств многоугольников, встроенный пространственный индекс).
Категория:Геометрические алгоритмы