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

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

Различные булевы операции над множествами принадлежащими двум фигурам (диаграммы Венна)

Алгоритмы

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

Применение в программировании

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

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

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

См. также

Примечания

Литература

  • Matthew J. Katz, Mark H. Overmars, Micha Sharir. Efficient hidden surface removal for objects with small union size // Computational Geometry (journal). — 1992. Т. 2, вып. 4. С. 223–234. doi:10.1016/0925-7721(92)90024-M.
  • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Algorithms and Applications. — Second Edition. — 2000.
  • Jon Louis Bentley, Thomas A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections // IEEE Transactions on Computers. — 1979. Т. C-28, вып. 9. С. 643–647.
  • Jon Louis Bentley, Derick Wood. An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles // IEEE Transactions on Computers. — 1980. Т. C-29, вып. 7. С. 571–577.
  • Ulrich Lauther. 18th Design Automation Conference. — 1981. — С. 555–562.
  • James A. Wilmore. 18th Design Automation Conference. — 1981. — С. 571–579.
  • J. Nievergelt, F. P. Preparata. Plane-Sweep Algorithms for Intersecting Geometric Figures // Communications of the ACM. — 1982. Т. 25, вып. 10. С. 739–747. doi:10.1145/358656.358681.
  • =Thomas Ottmann, Peter Widmayer, and Derick Wood. Computer Vision, Graphics, and Image Processing. — 1985. — Т. 30. — С. 249–268.

Ссылки

Алгоритмы и программы
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.