Journal
COMPUTERS & GEOSCIENCES
Volume 35, Issue 6, Pages 1177-1185Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cageo.2008.08.009
Keywords
Polygon clipping; Boolean operations polygons; Polygon overlay
Funding
- Ministerio de Ciencia y Tecnologia of Spain
- European Union [TIN2007-67474-CO3-03]
- Conserjeria de Innovacion
- Ciencia y Empresa of the Junta de Andalucia
- European Union
- ERDF [P06-TIC-01403, P07-TIC-02773]
Ask authors/readers for more resources
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 algorithm works with concave polygons with holes, and with regions composed of polygon sets. Furthermore, it can be easily adapted to work with self-intersecting polygons. (C) 2008 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available