Булевы операции над многоугольниками
Логические операции над многоугольниками — это набор логических операций (И, ИЛИ, НЕ, исключающее ИЛИ, ...), действующих над одним или несколькими наборами многоугольников в компьютерной графике. Эти наборы операций широко используются в компьютерной графике , САПР и в EDA (в программном обеспечении для физического проектирования и проверки интегральных схем ).
Алгоритмы [ править ]
- Алгоритм отсечения Грейнера – Хормана
- Алгоритм отсечения Ватти
- Алгоритм Сазерленда – Ходжмана (алгоритм особого случая)
- Алгоритм отсечения Вейлера – Атертона (алгоритм особого случая)
Использование в программном обеспечении [ править ]
Ранние алгоритмы логических операций над многоугольниками были основаны на использовании растровых изображений . Использование растровых изображений при моделировании полигональных форм имеет множество недостатков. Одним из недостатков является то, что использование памяти может быть очень большим, поскольку разрешение полигонов пропорционально количеству бит, используемых для представления полигонов. Чем выше желаемое разрешение, тем большее количество бит требуется.
Современные реализации логических операций над многоугольниками, как правило, используют алгоритмы развертки плоскости (или алгоритмы развертки линии ). Список статей, использующих алгоритмы прогонки плоскости для логических операций над многоугольниками, можно найти в разделе «Ссылки» ниже.
Булевы операции над выпуклыми многоугольниками и монотонными многоугольниками одного направления могут выполняться за линейное время . [1]
См. также [ править ]
- Булева алгебра
- Вычислительная геометрия
- Конструктивная твердотельная геометрия — метод определения трехмерных фигур с использованием аналогичного набора операций.
- Обработка геометрии
- General Polygon Clipper — библиотека C, которая вычисляет результаты операций обрезки.
Примечания [ править ]
- ^ Кац, Мэтью Дж.; Овермарс, Марк Х.; Шарир, Миха (1992), «Эффективное удаление скрытых поверхностей для объектов с небольшим размером объединения», Вычислительная геометрия: теория и приложения , 2 (4): 223–234, doi : 10.1016/0925-7721(92)90024-M .
Библиография [ править ]
- Марк де Берг, Марк ван Кревельд, Марк Овермарс и Отфрид Шварцкопф, Вычислительная геометрия - алгоритмы и приложения, второе издание, 2000 г.
- Джон Луис Бентли и Томас А. Оттманн, Алгоритмы сообщения и подсчета геометрических пересечений , Транзакции IEEE на компьютерах, Том. C-28, № 9, сентябрь 1979 г., стр. 643–647.
- Джон Луи Бентли и Дерик Вуд , Оптимальный алгоритм наихудшего случая для сообщения о пересечениях прямоугольников , Транзакции IEEE на компьютерах, Vol. С-29. № 7, июль 1980 г., стр. 571–577.
- Ульрих Лаутер, Алгоритм O (N log N) для операций с булевой маской , 18-я конференция по автоматизации проектирования, 1981, стр. 555–562.
- Джеймс А. Уилмор, Эффективные логические операции над масками ИС , 18-я конференция по автоматизации проектирования, 1981, стр. 571–579.
- Нивергельт, Дж.; Препарата, ФП (октябрь 1982 г.). «Алгоритмы прогонки плоскости для пересекающихся геометрических фигур». Коммуникации АКМ . 25 (10): 739–747. CiteSeerX 10.1.1.83.3275 . дои : 10.1145/358656.358681 . S2CID 16606107 .
- Томас Оттманн, Питер Видмайер и Дерик Вуд, « Быстрый алгоритм решения логической проблемы маскировки », Компьютерное зрение, графика и обработка изображений, 30, 1985, стр. 249–268.
Внешние ссылки [ править ]
- Программное обеспечение
- Михаил Леонов составил сравнение полигональных клипсаторов .
- Ангус Джонсон также сравнил три библиотеки обрезки .
- Компания SINED GmbH сравнила производительность и использование памяти трех машин для обрезки полигонов . Архивировано 16 ноября 2012 г. на Wayback Machine .
- Сравнение 5 библиотек обрезки на rogue-modron.blogspot.com.
- Коммерческая библиотека для трехмерных логических операций: библиотека sgCore C++/C# .
- , FAQ по comp.graphics.algorithms решения математических задач с 2D и 3D полигонами.
- Маттиаса Крамма gfxpoly , бесплатная библиотека C для 2D-полигонов (лицензия BSD).
- Клааса Холверды Boolean — библиотека C++ для 2D-полигонов.
- Дэвида Кеннисона Polypack — библиотека FORTRAN, основанная на алгоритме Ватти.
- от Klamer Schutte Clippoly — инструмент для обрезки полигонов, написанный на C++.
- Михаила Леонова Poly_Boolean — библиотека C++, расширяющая алгоритм Шутте.
- Ангуса Джонсона Clipper — бесплатная библиотека с открытым исходным кодом (написанная на Delphi, C++ и C#), основанная на алгоритме Ватти .
- clipper2 crate — безопасная оболочка Rust для библиотеки Clipper2 Ангуса Джонсона.
- GeoLib — коммерческая библиотека, доступная на C++ и C#.
- Алана Мурты. GPC Архивировано 27 февраля 2011 г. в Wayback Machine , библиотека General Polygon Clipper.
- PolygonLib. Архивировано 16 ноября 2012 г. в Wayback Machine , библиотеках C++ и COM для 2D-полигонов (оптимизировано для больших наборов полигонов, встроенные пространственные индексы).