Minimizing uncertainty in complete automation of Douglas-Peucker Algorithm for geospatial mapping

Rong Wang, Muhammad Shafeeque, Haowen Yan, Xiaoming LuResearch 2021 · DOI

TL;DR

This paper introduces a method to fully automate the Douglas-Peucker (DP) algorithm for geospatial mapping by quantifying the relationship between map scale changes and optimal distance thresholds. By leveraging spatial similarity theories, the researchers developed a quadratic model that eliminates the need for manual parameter input, significantly reducing uncertainty in automated map generalization.

What Problem Does This Paper Address?

In cartography, "generalization" is the process of simplifying complex geographic features (like winding rivers or jagged coastlines) so they remain clear and accurate when a map's scale changes (e.g., moving from a 1:5,000 scale to 1:50,000). The Douglas-Peucker (DP) algorithm is the industry standard for this task, but it has a major flaw: it requires a human operator to manually input a "distance threshold" ($T$).

If $T$ is too small, the map remains cluttered; if it's too large, vital geographic character is lost. Because the "optimal" $T$ varies depending on how much the scale is changing ($C$) and the specific geography of the area, achieving complete automation has been a "black box" problem. This paper seeks to replace human intuition with a robust mathematical relationship between $T$ and $C$.

Methods

The authors approached the problem by first defining what makes a simplified line "similar" to its original. They moved beyond simple distance metrics to create a Spatial Similarity Evaluation Model based on four key indices:

  1. Sinuosity: How much the line curves.
  2. Mean-Hausdorff Distance (MHD): A stable metric for measuring the distance between two sets of points.
  3. Shape (Cumulative Turning Function): A method to compare the "character" of polylines by looking at how their angles change.
  4. Buffer-Overlapped Area: Measuring the spatial "footprint" overlap between the original and simplified lines.

Using these indices, they performed two groups of control experiments. They used regression analysis and the least-squares method to test various candidate functions (linear, power, exponential, etc.) to see which best described the relationship between scale change ($C$) and the optimal threshold ($T$).

Datasets

The study utilized 38 groups of multi-scale datasets featuring rivers and roads across three major geographic regions in China:

  • Northeast China Plain
  • North China Plain (specifically the Huaibei Plain)
  • Yangtze Plain (including the Jianghuai Plain and Yangtze River Delta)

The data spanned scales from 1:10,000 to 1:500,000, derived from GF-2 satellite imagery and the National Geomatics Center of China (NGCC). This variety allowed the researchers to test if their model held true across different types of terrain and features.

Key Insights and Ideas

  • The Quadratic Connection: The most significant finding was that a unary quadratic function ($T = aC^2 + bC + d$) provides the best fit for determining the optimal distance threshold. This outperformed linear and logarithmic models.
  • Geography Matters: While the type of function (quadratic) remains the same across different regions, the coefficients change. This means you cannot use the same exact formula for a mountain range as you would for a flat plain, but you can use the same formula for all rivers and roads within that specific plain.
  • Similarity is the North Star: The "optimal" threshold is mathematically defined as the point where the spatial similarity between the simplified line and a standard target-scale reference line reaches its maximum.

Key Results

  • Improved Accuracy: The proposed evaluation model showed an accuracy improvement of 4.16% to 11.52% over existing models (like Yan 2014).
  • High Correlation: The quadratic fitting for the distance threshold achieved $R^2$ values as high as 0.9585, indicating an extremely strong relationship.
  • Geometric Integrity: Validation tests (using Length Ratio and Sinuosity Ratio) proved that the automated results maintained the "character" of the geographic features as well as, or better than, manual generalization.

Limitations and Future Work

The authors acknowledge a primary limitation of the DP algorithm itself: feature interference. Because the algorithm simplifies individual polylines in isolation, simplified lines that are near each other (like adjacent contour lines or a road running parallel to a river) might accidentally intersect.

Future work is suggested to expand this automated model to "group objects"—treating clusters of related features (like a whole drainage network or a city's road grid) as a single unit to ensure they don't overlap during the simplification process.

Summary updated

Abstract

Abstract It is qualitatively evident that the greater the map scale change, the greater the optimal distance threshold of the Douglas-Peucker Algorithm, which is used in polyline simplification. However, no specific quantitative relationships between them are known by far, causing uncertainties in complete automation of the algorithm. To fill this gap, the current paper constructs quantitative relationships based on the spatial similarity theories of polylines. A quantitative spatial similarity relationship model was proposed and evaluated by setting two groups of control experiments and taking <C, T> as coordinates. In order to realize the automatic generalization of the polyline, we verified whether these quantitative relationships could be fitted using the same function with the same coefficients. The experiments revealed that the unary quadratic function is the best, whether the polylines were derived from different or the same geographical feature area(s). The results also show that using the same optimal distance threshold is unreasonable to simplify all polylines from different geographical feature areas. On the other hand, the same geographical feature area polylines could be simplified using the same optimal distance threshold. The uncertainties were assessed by evaluating the automated generalization results for position and geometric accuracy perspectives using polylines from the same geographic feature areas. It is demonstrated that in addition to maintaining the geographical features, the proposed model maintains the shape characteristics of polylines. Limiting the uncertainties would support the realization of completely automatic generalization of polylines and the construction of vector map geodatabases.
BibTeX
@inproceedings{wang2021minimizing,
  author = {Rong Wang and Muhammad Shafeeque and Haowen Yan and Xiaoming Lu},
  title = {{Minimizing uncertainty in complete automation of Douglas-Peucker Algorithm for geospatial mapping}},
  booktitle = {Research},
  year = {2021},
  doi = {10.21203/rs.3.rs-1162837/v1},
}

Loading related content...

Figure