Логички оператори на полигонима
Логички оператори на полигонима обухватају операторе Булове алгебре (АНД, ОР, НОТ, XОР, ...) који се примењују на једном или висе многоуглова у рацунарској графици. Ови оператори се користе у рачунарској графици, ЦАД (цомпутер-аидед десигн) и у ЕДА (у интегрисаном колу физичког дизајна и вертификацији софтвера).
Алгоритми[уреди | уреди извор]
- Ватти цлиппинг алгоритхм
- Сутхерланд–Ходгман алгоритхм (алгоритам за специјални случај)
- Wеилер–Атхертон цлиппинг алгоритхм (алгоритам за специјални случај)
Употреба код софтвера[уреди | уреди извор]
Први алгоритми за логичке операторе на многоугловима базирају се на употреби битмапс. Употреба битмапс у моделирању полигонских облика има много недостатака. Један од недостатака је то што се троши пуно меморије, пошто је резолуција многоугла пропорционална броју битова употребљеном за приказ полигона. Што већу резолуцију желимо, више битова је потребно.
Модерне имплементатције теже да користе плане сwееп алгоритхмс (или Сwееп лине алгоритхмс). Списак радова који користе плане сwееп алгоритхмс могу се наћи у референцама.
Булове операције на конвексним многоугловима и монотоним многоугловима у истом правцу могу се извршити у линеарном времену.
Литература[уреди | уреди извор]
- Марк де Берг, Марц ван Кревелд, Марк Овермарс, анд Отфриед Сцхwарзкопф, Цомпутатионал Геометрy - Алгоритхмс анд Апплицатионс, Сецонд Едитион, 2000
- Јон Лоуис Бентлеy анд Тхомас А. Оттманн, Алгоритхмс фор Репортинг анд Цоунтинг Геометриц Интерсецтионс, ИЕЕЕ Трансацтионс он Цомпутерс, Вол. C-28, Но. 9, Септембер 1979. пп. 643–647
- Јон Лоуис Бентлеy анд Дерицк Wоод, Ан Оптимал Wорст Цасе Алгоритхм фор Репортинг Интерсецтионс оф Рецтанглес, ИЕЕЕ Трансацтионс он Цомпутерс, Вол. C-29. Но. 7, Јулy 1980. пп. 571–577
- Улрицх Лаутхер, Ан О(Н лог Н) Алгоритхм фор Боолеан Маск Оператионс, 18тх Десигн Аутоматион Цонференце, 1981. пп. 555–562
- Јамес А. Wилморе, Еффициент Боолеан Оператионс он ИЦ Маскс, 18тх Десигн Аутоматион Цонференце, 1981. пп. 571–579
- Ниевергелт, Ј.; Препарата, Ф. П. (1982). „Плане-Сwееп Алгоритхмс фор Интерсецтинг Геометриц Фигурес”. Цоммуницатионс оф тхе АЦМ. 25 (10): 739—747. ЦитеСеерX: 10
.1 .1 .83 .3275. - Тхомас Оттманн, Петер Wидмаyер, анд Дерицк Wоод, "А Фаст Алгоритхм фор тхе Боолеан Маскинг Проблем," Цомпутер Висион, Грапхицс, анд Имаге Процессинг, 30, 1985. пп. 249–268
- Францисцо Мартíнез, Антонио Јесúс Руеда, Францисцо Рамóн Феито, А неw алгоритхм фор цомпутинг Боолеан оператионс он полyгонс, Цомпутерс & Геосциенцес, Волуме 35, Иссуе 6, Јуне 2009, Пагес 1177-1185, ИССН 0098-3004
Види још[уреди | уреди извор]
- Софтwаре
- Мицхаел Леонов хас цомпилед а цомпарисон оф полyгон цлипперс.
- Ангус Јохнсон хас алсо цомпаред тхрее цлиппинг либрариес.
- СИНЕД ГмбХ хас цомпаред перформанце анд меморy утилизатион оф тхрее полyгон цлипперс Архивирано на сајту Wayback Machine (16. новембар 2012).
- А цомпарисон оф 5 цлиппинг либрариес ат рогуе-модрон.блогспот.цом
- А цоммерциал либрарy фор 3Д Боолеан оператионс: сгЦоре C++/C# либрарy.
- Тхе цомп.грапхицс.алгоритхмс ФАQ, солутионс то матхематицал проблемс wитх 2Д анд 3Д Полyгонс.
- Маттхиас Крамм'с гфxполy, а фрее C либрарy фор 2Д полyгонс (БСД лиценсе).
- Клаас Холwерда'с Боолеан, а C++ либрарy фор 2Д полyгонс.
- Давид Кеннисон'с Полyпацк, а ФОРТРАН либрарy басед он тхе Ватти алгоритхм.
- Кламер Сцхутте'с Цлипполy, а полyгон цлиппер wриттен ин C++.
- Мицхаел Леонов'с полy_Боолеан, а C++ либрарy, wхицх еxтендс тхе Сцхутте алгоритхм.
- Ангус Јохнсон'с Цлиппер, ан опен-соурце фрееwаре либрарy (wриттен ин Делпхи, C++ анд C#) тхат'с басед он тхе Ватти алгоритхм.
- ГеоЛиб, а цоммерциал либрарy аваилабле ин C++ анд C#.
- Алан Мурта'с ГПЦ Архивирано на сајту Wayback Machine (27. фебруар 2011), Генерал Полyгон Цлиппер либрарy.
- ПолyгонЛиб Архивирано на сајту Wayback Machine (16. новембар 2012), C++ анд ЦОМ либрариес фор 2Д полyгонс (оптимизед фор ларге полyгон сетс, буилт-ин спатиал индицес).