Перегляд вихідного коду сторінки Булеві операції над многокутниками

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

[[Файл:Boolean_operations_on_shapes-ru.svg|міні|300x300пкс| Різні булеві операції над множинами, що належать двом фігурам ([[Діаграма Венна|діаграми Венна]]).]]
'''Бу́леві опера́ції над многоку́тниками''' або '''фігу́рами'''&nbsp;— це набір [[Алгебра логіки|булевих операцій]] (AND, OR, NOT, XOR, …) над одним або декількома наборами [[многокутник]]ів у комп'ютерній графіці. Ці набори операцій поширені в [[Машинна графіка|комп'ютерній графіці]], [[Система автоматизованого проєктування і розрахунку|САПР]] та в [[Програми проєктування електронних систем|проєктуванні електронних схем]] (фізичне розташування елементів [[Мікросхема|інтегральних схем]] та програми перевірки).

== Алгоритми ==
* {{Не перекладено|Алгоритм відсікання Ґрайнера — Горманна||en|Greiner–Hormann clipping algorithm}}
* {{Не перекладено|Алгоритм відсікання Ватті||en|Vatti clipping algorithm}}
* {{Не перекладено|Алгоритм Сазерленда — Годжмана||en|Sutherland–Hodgman algorithm}} (алгоритм для часткового випадку)
* [[Алгоритм Вайлера — Атертона]] (алгоритм для часткового випадку)

== Застосування в програмуванні ==
Ранні алгоритми булевих операцій із многокутниками ґрунтувалися на [[Бітова мапа|бітових мапах]]. Використання бітових мап у моделюванні багатокутних фігур та операціях над ними має багато недоліків. Один з недоліків&nbsp;— може знадобитися дуже багато пам'яті, оскільки роздільність малюнка многокутника пропорційна числу [[Піксель|пікселів]], що використовуються для подання багатокутників. Що більша роздільність зображення, то більше біт потрібно зберігати в пам'яті.

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

Булеві операції над [[Опуклий многокутник|опуклими]] та [[Монотонний многокутник|монотонними многокутниками]] з однаковими напрямками можна здійснити за [[Часова складність|лінійний час]]{{Sfn|Katz, Overmars, Sharir|1992|с=223–234}}.

== Див. також ==
* [[Алгебра логіки]]
* [[Обчислювальна геометрія]]
* [[Конструктивна блокова геометрія|Конструктивна суцільна геометрія]]
* {{Не перекладено|General Polygon Clipper||en|}} (Загальне Відсікання Многокутника), бібліотека на C, що обчислює результат операції відсікання
* [[Конструктивна блокова геометрія]], метод визначення тривимірних фігур з використанням аналогічних операцій

== Примітки ==
{{примітки}}

== Література ==
{{Refbegin|colwidth=30em}}
* {{Стаття|author=Matthew J. Katz, Mark H. Overmars, Micha Sharir|ref=Katz, Overmars, Sharir|doi=10.1016/0925-7721(92)90024-M|issue=4|видання=Computational Geometry (journal)|pages=223–234|title=Efficient hidden surface removal for objects with small union size|том=2|рік=1992}}
* {{Книга
|автор = Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
|ref = de Berg, van Kreveld, Overmars, Schwarzkopf
|заголовок = Algorithms and Applications
|видання = Second Edition
|рік = 2000
}}
* {{Стаття|author=Jon Louis Bentley, Thomas A. Ottmann|ref=Bentley, Ottmann|url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1675432|title=Algorithms for Reporting and Counting Geometric Intersections|видання=IEEE Transactions on Computers|том=C-28|issue=9|рік=1979|pages=643–647}}
* {{Стаття|author=Jon Louis Bentley, Derick Wood|ref=Bentley, Wood|url=http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1675628|title=An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles|видання=IEEE Transactions on Computers|том=C-29|issue=7|рік=1980|pages=571–577}}
* {{Книга
|автор = Ulrich Lauther
|ref = Lauther
|посилання = http://portal.acm.org/citation.cfm?id=802358&jmp=abstract
|заголовок = 18th Design Automation Conference
|рік = 1981
|сторінки = 555–562
}}
* {{Книга
|автор = James A. Wilmore
|ref = Wilmore
|посилання = http://portal.acm.org/citation.cfm?id=802360
|заголовок = 18th Design Automation Conference
|рік = 1981
|сторінки = 571–579
}}
* {{Стаття|author=J. Nievergelt, F. P. Preparata|ref=Nievergelt, Preparata|title=Plane-Sweep Algorithms for Intersecting Geometric Figures|видання=Communications of the ACM|рік=1982|том=25|issue=10|pages=739–747|doi=10.1145/358656.358681}}
* {{Книга
|автор = =Thomas Ottmann, Peter Widmayer, and Derick Wood
|заголовок = Computer Vision, Graphics, and Image Processing
|том = 30
|рік = 1985
|сторінки = 249–268
}}
{{Refend}}

== Посилання ==
* [https://web.archive.org/web/20111106212300/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ UIUC Computational Geometry Pages]
* [https://web.archive.org/web/20081219103233/http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html Constructive planar geometry] від Дейва Еберлі (Dave Eberly).

;Алгоритми та програми

* Михайло Леонов склав [https://web.archive.org/web/20110720075903/http://www.complex-a5.ru/polyboolean/comp.html порівняння алгоритмів відсікання багатокутників]. {{Ref-en}}
* Ангус Джонсон склав також [http://angusj.com/delphi/clipper.php#features порівняння трьох бібліотек відсікання]. {{Ref-en}}
* Компанія SINED GmbH склала [http://www.ulybin.de/products/polygonlib.php?lang=en#comparison порівняння продуктивності та використання пам'яті трьох алгоритмів відсікання]. {{Ref-en}}
* Порівняння 5 бібліотек відсікання [http://rogue-modron.blogspot.com/2011/04/polygon-clipping-wrapper-benchmark.html rogue-modron.blogspot.com] {{Ref-en}}
* [http://www.geometros.com sgCore C++/C# Бібліотека]&nbsp;— комерційна бібліотека для 3-вимірних булевих операцій.
* [http://www.faqs.org/faqs/graphics/algorithms-faq/ comp.graphics.algorithms FAQ]&nbsp;— розв'язування математичних задач із дво- та тривимірними многокутниками.
* [http://gfxpoly.quiss.org/ gfxpoly] Маттіаса Крамма&nbsp;— вільно поширювана бібліотека на C для 2D многокутників (ліцензія BSD).
* [http://boolean.klaasholwerda.nl/bool.html Boolean] Клааса Голверда&nbsp;— бібліотека на C++ для 2D многокутників.
* [https://web.archive.org/web/20081103090937/http://www.dkrz.de/ngdoc/ng/supplements/polypack/ Polypack] Девіда Кеннісона&nbsp;— бібліотека на Фортрані, заснована на алгоритмі Ватті.
* [http://clippoly.sourceforge.net/ Clippoly] Кламера Шатте&nbsp;— програма відсікання многокутника, написана на C++.
* [https://web.archive.org/web/20110720075903/http://www.complex-a5.ru/polyboolean/comp.html poly_Boolean] Михайла Леонова&nbsp;— бібліотека на C++, що розширює алгоритм Шатта.
* [http://sourceforge.net/projects/polyclipping/ Clipper] Ангуса Джонсона&nbsp;— вільно поширювана бібліотека з відкритим кодом (написана на Delphi, C++ і C#), заснована на {{Не перекладено|Алгоритм відсікання Ватті|алгоритмі відсікання Ватті|en|Vatti clipping algorithm}}.
* [http://www.geolib.co.uk/index.htm GeoLib]&nbsp;— комерційна бібліотека, доступна на C++ та C#.
* [http://www.cs.man.ac.uk/~toby/alan/software/ GPC] Алана Марта&nbsp;— бібліотека «Загальне відсікання многокутника».
* [http://www.ulybin.de/products/polygonlib.php?lang=en PolygonLib]&nbsp;— бібліотеки на C++ та COM для 2D-многокутників (оптимізована для великих множин многокутників, вбудовано просторовий індекс).

[[Категорія:Геометричні алгоритми]]

Шаблони, використані на цій сторінці:

Шаблон:-. (переглянути вихідний код) (захищено)
Шаблон:Column-width (переглянути вихідний код) (частково захищено)
Шаблон:Delink (переглянути вихідний код) (захищено)
Шаблон:Main other (переглянути вихідний код) (захищено)
Шаблон:Nobr (переглянути вихідний код) (захищено)
Шаблон:Ref-en (переглянути вихідний код) (захищено)
Шаблон:Ref-info/styles.css (переглянути вихідний код) (захищено)
Шаблон:Ref-lang (переглянути вихідний код) (захищено)
Шаблон:Refbegin (переглянути вихідний код) (захищено)
Шаблон:Refbegin/styles.css (переглянути вихідний код) (захищено)
Шаблон:Refend (переглянути вихідний код) (захищено)
Шаблон:Reflist (переглянути вихідний код) (захищено)
Шаблон:Reflist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Sfn (переглянути вихідний код) (частково захищено)
Шаблон:Str endswith (переглянути вихідний код) (захищено)
Шаблон:Str len (переглянути вихідний код) (захищено)
Шаблон:±. (переглянути вихідний код) (захищено)
Шаблон:Бскор (переглянути вихідний код) (частково захищено)
Шаблон:Книга (переглянути вихідний код) (захищено)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Шаблон:Примітки (переглянути вихідний код) (захищено)
Шаблон:Стаття (переглянути вихідний код) (частково захищено)
Модуль:Arguments (переглянути вихідний код) (захищено)
Модуль:Check for unknown parameters (переглянути вихідний код) (захищено)
Модуль:Delink (переглянути вихідний код) (захищено)
Модуль:Footnotes (переглянути вихідний код) (частково захищено)
Модуль:Lang (переглянути вихідний код) (захищено)
Модуль:Lang/ISO 639 synonyms (переглянути вихідний код) (захищено)
Модуль:Lang/data (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana languages (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana regions (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana scripts (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana suppressed scripts (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana variants (переглянути вихідний код) (захищено)
Модуль:Lang/data/languages abbr. (переглянути вихідний код) (захищено)
Модуль:Ref-info (переглянути вихідний код) (захищено)
Модуль:Ref-lang (переглянути вихідний код) (захищено)
Модуль:String (переглянути вихідний код) (захищено)
Модуль:Unicode data (переглянути вихідний код) (захищено)
Модуль:Yesno (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)

Повернення до сторінки «Булеві операції над многокутниками».

Отримано з https://uk.wikipedia.org/wiki/Булеві_операції_над_многокутниками