A new algorithm for computing Boolean operations on polygons

TitleA new algorithm for computing Boolean operations on polygons
Publication TypeJournal Article
Year of Publication2009
AuthorsMartínez, Francisco, Rueda Antonio Jesús, and Feito Francisco Ramón
JournalComputers & Geosciences
Volume35
Number6
Pagination1177 - 1185
ISSN0098-3004
KeywordsBoolean operations polygons, Polygon clipping, Polygon overlay
Abstract

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.

URLhttp://www.sciencedirect.com/science/article/pii/S0098300408002793
DOI10.1016/j.cageo.2008.08.009