A new algorithm for computing Boolean operations on polygons
作者： Francisco Martínez , Antonio Jesús Rueda , Francisco Ramón Feito
DOI: 10.1016/J.CAGEO.2008.08.009
关键词:
摘要: This paper presents a new algorithm for computing Boolean operations on polygons. These kind of operations are frequently used in the geosciences in order to get spatial information from spatial data modeled as polygons. The presented algorithm is simple and easy to understand and implement. Let n be the total number of edges of all the polygons involved in a Boolean operation and k be the number of intersections of all the polygon edges. Our algorithm computes the Boolean operation in time O ((n+ k) log (n)). Finally, the proposed …
acm.org
harvard.edu
elsevier.com
researchgate.net 
sci-hub.se 参考文章(11)
James D. Foley, Computer Graphics: Principles and Practice ,(1995)
Philip J. Schneider, David Eberly, Geometric Tools for Computer Graphics ,(2002)
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
Kevin Weiler, Polygon comparison using a graph representation Proceedings of the 7th annual conference on Computer graphics and interactive techniques - SIGGRAPH '80. ,vol. 14, pp. 10- 18 ,(1980) , 10.1145/800250.807462
Rumen D. Andreev, Algorithm for Clpping Arbitrary Polygons Computer Graphics Forum. ,vol. 8, pp. 183- 191 ,(1989) , 10.1111/J.1467-8659.1989.TB00484.X
You-Dong Liang, Brian A. Barsky, An analysis and algorithm for polygon clipping Communications of the ACM. ,vol. 26, pp. 868- 877 ,(1983) , 10.1145/182.358439
Günther Greiner, Kai Hormann, Efficient clipping of arbitrary polygons ACM Transactions on Graphics. ,vol. 17, pp. 71- 83 ,(1998) , 10.1145/274363.274364
Yong Kui Liu, Xiao Qiang Wang, Shu Zhe Bao, Matej Gomboši, Borut Žalik, An algorithm for polygon clipping, and for determining polygon intersections and unions Computers & Geosciences. ,vol. 33, pp. 589- 598 ,(2007) , 10.1016/J.CAGEO.2006.08.008
Bala R. Vatti, A generic solution to polygon clipping Communications of the ACM. ,vol. 35, pp. 56- 63 ,(1992) , 10.1145/129902.129906
Ivan E. Sutherland, Gary W. Hodgman, Reentrant polygon clipping Communications of The ACM. ,vol. 17, pp. 32- 42 ,(1974) , 10.1145/360767.360802