Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции

Авторы

  • А.В. Скворцов

Ключевые слова:

триангуляция Делоне
вычислительная устойчивость
вычислительная геометрия
машинная графика
геоинформационные системы
многоугольники
системы автоматизированного проектирования

Аннотация

Рассматривается применение триангуляции с ограничениями для построения оверлеев произвольных многоугольников. Приводится сравнение с другими алгоритмами.

Новые вычислительные технологии

Загрузки

Опубликован

2002-03-27

Выпуск

Том 3 (2002): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

А.В. Скворцов

Томский государственный университет,
Институт прикладной математики и компьютерных наук
пр. Ленина, 3, 634050, г. Томск

Библиографические ссылки

  1. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  2. Роджерс Д., Адамс Дж. Математические основы машинной графики. М.: Машиностроение, 1980.
  3. Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование. 2002. 3, № 1. 86-96 (http://num-meth.srcc.msu.su).
  4. Скворцов А.В., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Вып. 1. Томск: Изд-во Томск. ун-та, 1998. 127-138.
  5. Margalit A., Knott G.D. An algorithm for computing the union, intersection of difference of two polygons // Computers & Graphics. 1989. 13, N 2. 167-183.
  6. O’Rourke J., Chien C.-B., Olson T., Naddor D. A new linear algorithm for intersecting convex polygons // Computer Graphics and Image Processing. 1982. 19. 384-391.
  7. Sutherland I.E., Hodgman G.W. Reentrant polygon clipping // CACM. 1983. 26. 868-877.
  8. Weiler K., Atherton P. Hidden surface removal using polygon area sorting // Computer Graphics. 1977. 11. 214-222.