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