Envelope generation and simplification of polylines using Delaunay triangulation |
| |
| Authors: | Tinghua Ai Shu Ke Jingzhong Li |
| |
| Institution: | School of Resource and Environment Sciences, Wuhan University, Wuhan, China |
| |
| 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 |
|
|
