An algorithm for constructing the union, intersection and difference of arbitrary polygons on the basis of triangulation with linear-time complexity on average

Authors

  • A.V. Skvortsov

Keywords:

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

Abstract

The application of triangulation with constraints for constructing overlays of arbitrary polygons is considered. A comparison of a new algorithm with some others is given.

New computational technologies

Downloads

Published

2002-03-27

Issue

Vol. 3 (2002): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

A.V. Skvortsov

Tomsk Polytechnic University,
Institute of Applied Mathematics and Computer Science

References

  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.