Envelope generation and simplification of polylines using Delaunay triangulation

ABSTRACT

As a basic and significant operator in map generalization, polyline simplification needs to work across scales. Perkal’s ε-circle rolling approach, in which a circle with diameter ε is rolled on both sides of the polyline so that the small bend features can be detected and removed, is considered as one of the few scale-driven solutions. However, the envelope computation, which is a key part of this method, has been difficult to implement. Here, we present a computational method that implements Perkal’s proposal. To simulate the effects of a rolling circle, Delaunay triangulation is used to detect bend features and further to construct the envelope structure around a polyline. Then, different connection methods within the enveloping area are provided to output the abstracted result, and a strategy to determine the best connection method is explored. Experiments with real land-use polygon data are implemented, and comparison with other algorithms is discussed. In addition to the scale-specificity inherited from Perkal’s proposal, the results show that the proposed algorithm can preserve the main shape of the polyline and meet the area-maintaining constraint during large-scale change. This algorithm is also free from self-intersection.

KEYWORDS:

• Map generalization
• polyline simplification
• Perkal’s proposal
• Delaunay triangulation

Acknowledgements

This work was supported by research grants from the National Natural Science Foundation of China [grant numbers 41531180 and 41401447]. Special thanks to the editor and anonymous reviewers for their constructive comments that substantially improved the quality of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by research grants from the National Natural Science Foundation of China [grant numbers 41531180 and 41401447].