|
Vector polygon overlay analysis is one of the most basic, crucial and complex analysis methods in geographic information systems (GIS). The method is usually the basic algorithm for the constitutions of many high-level spatial analysis models. With the extensive and in-depth applications of vector spatial data structures based on simple feature models, nontopological vector polygon overlay analysis algorithms have attracted more attention from scholars. Many different types of polygon clipping algorithms used for overlay analysis have emerged. The Vatti algorithm, GreinerHormann algorithm, Liu algorithm and Martinez algorithm are 4 acknowledged algorithms for arbitrary vector polygon clipping with reasonable time consumption. Most previous studies focused on the optimization and improvement methods of a single polygon clipping algorithm and lacked comprehensive analysis and comparison between them based on real spatial vector data. In this paper, the 4 polygon clipping algorithms mentioned above are implemented based on the Geospatial Data Abstraction Library (GDAL)/OpenGIS Simple Features Reference Implementation (OGR) model. The spatial complexity and time consumption of the 4 polygon clipping algorithms are tested and analyzed statistically using 4 different Boolean operations, including the intersection, union, difference and symmetrical difference. Experimental results show that: 1) Regarding the spatial complexity, Liu’s and Vatti’s algorithms are the lowest and the highest, respectively, while Greiner-Hormann’s and Martinez’s algorithms are between the other two. 2) Regarding the time complexity, Vatti’s algorithm is the highest as the square order, Martinez’s algorithm is the linear logarithmic order, and the time complexities of Liu’s and Greiner-Hormann’s algorithms are between the linear order and the square order. 3) Regarding the time consumption of these algorithms, when four Boolean operations are carried out between two polygon layers, Martinez’s algorithm takes the least time when the number of the subject layer polygons reaches 7495 and the number of the clipping layer rectangles exceeds 6400.
|
