Envelope generation and simplification of polylines using Delaunay triangulation. Issue 2 (1st February 2017)

• Record Type: Journal Article
• Authors: Ai, Tinghua; Ke, Shu; Yang, Min; Li, Jingzhong
• Is Part Of: International journal of geographical information science. Volume 31:Issue 2(2017)
• Page Start: 297
• Page End: 319
• Publication Date: 2017-02-01
• Subjects: Map generalization -- polyline simplification -- Perkal's proposal -- Delaunay triangulation; Geography -- Data processing -- Periodicals; Information storage and retrieval systems -- Periodicals; Géomatique -- Périodiques; Systèmes d'information -- Périodiques; 910.285
• DOI: 10.1080/13658816.2016.1197399
• Languages: English
• ISSNs: 1365-8816

Abstract

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.