Comparative Study on the Effect of Shape Complexity on the Efficiency of Different Overlay Analysis Algorithms

Peng Zhang, Junfu Fan, Panpan Zhang, Zhikun Zhang, Zheng Chen, Liusheng HanIEEE Access 2021 · DOI

Abstract

Polygon shape is a critical factor influencing the efficiency of vector polygon overlay analysis in Geographic Information Systems (GIS). However, accurately measuring shape complexity and understanding how different algorithms respond to it remains a challenge. This study evaluates 27 shape variables to develop complexity models for three prominent algorithms: Vatti, Greiner-Hormann, and Martinez. Using multiple linear regression, the research demonstrates that the Greiner-Hormann algorithm is the most predictable, with its performance model achieving an R² of 0.99.

Introduction: The Challenge of Overlay Analysis

Overlay analysis—the process of performing Boolean operations (intersection, union, difference) on spatial data layers—is a fundamental task in GIS. While it is well-understood that complex geometries slow down these operations, a precise, quantitative relationship between shape complexity and computational performance has been lacking. This paper addresses this gap by modeling how specific geometric attributes impact the processing time of industry-standard algorithms like Vatti, Greiner-Hormann, and Martinez.

Methodology: Modeling Complexity

The researchers identified 27 geometric variables categorized into spatial relationships, attributes (e.g., number of vertices), morphology (e.g., concavity), and auxiliary metrics. These variables were used to build Multiple Linear Regression (MLR) models to predict the computation time for three algorithms:

  1. Vatti: Utilizes a "scanbeam" approach to process edges.
  2. Greiner-Hormann: Employs doubly linked lists to manage intersections.
  3. Martinez: An advanced plane-sweep algorithm designed for robustness.
The scanbeam approach, as used in the Vatti algorithm, divides the polygon into horizontal strips to process intersections.

The stepwise screening process in the MLR allowed the authors to isolate the most significant predictors of performance while eliminating redundant variables.

Datasets: Real-World Complexity

To validate the models, the study utilized extensive real-world vector datasets, ensuring the findings were applicable beyond idealized geometric shapes:

  • Global Administrative Areas: ~255,000 county-level boundary polygons.
  • OpenStreetMap (China): ~509,000 land patches and ~222,000 water system polygons.
Complex landpatch data from China used to test the sensitivity of overlay algorithms to irregular geometries.

These datasets provided a diverse range of "computational nightmares," including jagged coastlines and polygons with numerous internal holes, which are typical in high-resolution GIS work.

Key Insights and Results

The study revealed several critical findings regarding algorithm performance:

  • The Dominance of Vertices: The Number of Vertices (NOV) is the primary driver of computation time across all algorithms, with standardized coefficients ranging from 0.91 to 0.97. Simplifying geometry remains the most effective way to improve performance.
  • Algorithm Predictability: The Greiner-Hormann algorithm's performance is almost entirely explained by geometric complexity (R² = 0.99). In contrast, the Martinez algorithm showed more variance (R² = 0.87), likely due to its use of complex data structures like priority queues which are sensitive to specific topological arrangements.
  • Operator Invariance: The sensitivity of an algorithm to a specific shape remains consistent regardless of the Boolean operation (Intersection, Union, or Difference) being performed.
  • Secondary Factors: Beyond vertices, metrics such as "average nearest neighbor" and "frequency of vibration" (concave/convex switching) were significant for the Vatti and Martinez models.

Conclusion and Future Directions

This research provides a quantitative framework for predicting GIS algorithm performance based on data complexity. While the current study focuses on individual polygon clipping, future work will scale these models to "coarse-grained" analysis involving entire map layers. Understanding the interplay between internal data structures and geometric complexity remains a key area for optimizing spatial analysis tools.

Summary updated

Abstract

Polygon shape is an important factor affecting the efficiency of vector polygon overlay analysis. Aiming at the problems that polygon shape is difficult to accurately measure and different algorithms have different sensitivities to the same polygon in vector polygon overlay analysis, 27 shape variables are selected from literature to establish the shape complexity models for Vatti, Greiner-Hormann and Martinez algorithms by multiple linear regression analysis in this paper. These three algorithms are suitable for arbitrary polygon clipping and include intersection, union, difference and symmetric difference operators. The experimental results show that the calculated performances of the intersection, union, difference and symmetric difference operators belonging to the same algorithm are similar to their sensitivity to the same polygon shape. The fitting correlation coefficient R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> of the shape complexity model based on the Greiner-Hormann algorithm is the highest among the three algorithms, which can explain 99% of the performance of this algorithm.
BibTeX
@inproceedings{zhang2021comparative,
  author = {Peng Zhang and Junfu Fan and Panpan Zhang and Zhikun Zhang and Zheng Chen and Liusheng Han},
  title = {{Comparative Study on the Effect of Shape Complexity on the Efficiency of Different Overlay Analysis Algorithms}},
  booktitle = {IEEE Access},
  year = {2021},
  doi = {10.1109/access.2021.3121753},
}

Loading related content...

Figure