A review of the algorithms of polygon overlays design
A review of thealgorithms of intersection, union and difference of polygons are given. These algorithms are compared of computer tolerance, complexity,working speed and software implementation simplicity. The paper gives both well known and new algorithms including unpublishedbut Internet available ones.
Download file
Counter downloads: 308
Keywords
Authors
| Name | Organization | |
| Chentsov O.V. | Khakass State University (Abakan) | |
| Skvortsov A.V. | Tomsk State University | skv74@mail.ru иskv@csd.tsu.ru |
References
Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989. 478 с.
Foley D.J., van Dam A., Feiner S.K., Hughes J.F. Computer graphics. Principles and practice. N.Y.: Addisson-Westey, 1991.
Роджерс Д. Алгоритмические основы машинной графики / Пер. с англ. М.: Мир, 1989. 512 с.
Weiler K., Atherton P. Hidden surface removing using polygon area sorting // Computer Graphics. 1977. V.11. P. 214-222.
Weiler K. Polygon comparison using graph representation // Computer Graphics. 1980. V.14. P. 10-18.
Schutte K. An edge labeling approach to concave polygon clipping // ACM Transactions on Graphics. 1995. P. 1-10.
Леонов М.В., Никитин А.Г. Эффективный алгоритм, реализующий замкнутый набор булевых операций над множествами многоугольников на плоскости / Препринт Института систем информатики СО РАН № 46. 1997. 20 с.
Sutherland I.E., Hodgman G.W. Reentrant polygon clipping // CACM. 1983. V.26. P. 868-877.
Clark J.H. A VLSI geometry Processor for Graphics // IEEE Computer. 1980. V.12 (7). P 59-68.
Margalit A., Knott G.D. An algorithm for computing the union, intersection or difference of two polygons // Computers & Graphics. 1989. V.13. No. 2. P. 167-183.
11. O'Rourke J., Chien C.B., Olson Т., Naddor D. A new linear algorithm for intersecting convex polygons // Computer Graphics and Image Processing. 1982. V.19. P. 384-391.
Holwerda K. Complete Boolean Description (http:// www.xs4all.nl/~kholwerd/bool.html).
Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции // Вычислительные методы и программирование. 2002. Т. 3. С. 116-123.
Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование. 2002. № 3. С. 82-92 (http://num-meth.srcc.msu.su).
Скворцов А.В. Линейно-узловой алгоритм построения оверлеев двух полигонов // Вестник ТГУ. 2002. № 275. С. 99-103.
