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 Tomsk Polytechnic University

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.

Author Biography

A.V. Skvortsov

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.

Published

27-03-2002

How to Cite

Скворцов А.В. An Algorithm for Constructing the Union, Intersection and Difference of Arbitrary Polygons on the Basis of Triangulation With Linear-Time Complexity on Average // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2002. 3. 116-123

Issue

Section

Section 1. Numerical methods and applications