Булевы операции над многоугольниками

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

• Алгоритм отсечения Грайнера – Хорманна^[англ.]
• Алгоритм отсечения Ватти^[англ.]
• Алгоритм Сазерленда – Ходжмана^[англ.] (алгоритм для частного случая)
• Алгоритм Уайлера — Атертона (алгоритм для частного случая)

Ранние алгоритмы булевых операций с многоугольниками основывались на битовых картах. Использование битовых карт в моделировании многоугольных фигур и операциях над ними имеет много недостатков. Один из недостатков — может потребоваться очень много памяти, поскольку разрешение рисунка многоугольника пропорционально числу пикселей, используемых для представления многоугольников. Чем больше разрешение изображения, тем большее число бит требуется хранить в памяти.

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

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

• Алгебра логики
• Вычислительная геометрия
• Конструктивная сплошная геометрия
• General Polygon Clipper^[англ.] (Общее Отсечение Многоугольника), библиотека на 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-многоугольников (оптимизирована для больших множеств многоугольников, встроенный пространственный индекс).

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (8 марта 2017) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (8 марта 2017) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.