Envelope generation and simplification of polylines using Delaunay triangulation
Envelope generation and simplification of polylines using Delaunay triangulation
复制标题
使用 Delaunay 三角剖分生成包络线并简化折线
DOI：
10.1080/13658816.2016.1197399
复制
发表时间：
2017-01-01
影响因子：
5.7
通讯作者：
Li, Jingzhong
中科院分区：
文献类型：
--
作者：
Ai, Tinghua;Ke, Shu;Li, Jingzhong
折线化简是地图综合中最基本、最重要的一种操作，需要跨比例尺进行。Perkal的epsilon-circle轧制方法是在折线的两侧轧制一个直径为epsilon的圆，以检测和去除小弯曲特征，被认为是为数不多的尺度驱动解决方案之一。然而，该方法的关键部分包络计算一直难以实现。在这里，我们提出了一种实现Perkal建议的计算方法。为了模拟滚动圆的影响，采用Delaunay三角剖分法检测弯曲特征，并进一步构建围绕折线的包络结构。然后，在包络区域内提供不同的连接方法来输出抽象结果，并探索确定最佳连接方法的策略。在实际土地利用多边形数据上进行了实验，并与其他算法进行了比较。结果表明，该算法除了继承了Perkal算法的尺度特异性外，还能在大规模变化时保持折线的主要形状，满足面积保持约束。该算法不存在自交问题。
As a basic and significant operator in map generalization, polyline simplification needs to work across scales. Perkal's epsilon-circle rolling approach, in which a circle with diameter epsilon 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.