测绘学报 ›› 2020, Vol. 49 ›› Issue (11): 1485-1496.doi: 10.11947/j.AGCS.2020.20190406

• 地图学与地理信息 • 上一篇    下一篇

顾及Gestalt邻近与简化原则的平面点集形状重建

颜金彪1,2, 吴波1, 彭馨1   

  1. 1. 江西师范大学地理与环境学院, 江西 南昌 330022;
    2. 衡阳师范学院传统村镇文化数字化保护与创意利用技术国家地方联合工程实验室, 湖南 衡阳 421002
  • 收稿日期:2019-09-24 修回日期:2020-06-05 发布日期:2020-11-25
  • 通讯作者: 吴波 E-mail:wavelet778@sohu.com
  • 作者简介:颜金彪(1987-),男,博士生,研究方向为时空数据挖掘理论与应用。E-mail:jbyan@hynu.edu.cn
  • 基金资助:
    国家自然科学基金(41961055);湖南省教育厅优秀青年项目(19B078;19C0272);衡阳市社科基金(2018B(I)002);传统村镇文化数字化保护与创意利用技术国家地方联合工程实验室开放基金(CTCZ18K01);国家重点研发计划(2018YFE0207800)

A method to shape reconstruction from planar point sets with Gestalt proximity and simplification principle

YAN Jinbiao1,2, WU Bo1, PENG Xin1   

  1. 1. School of Geography and Environment, Jiangxi Normal University, Nanchang 330022, China;
    2. National-Local Joint Engineering Laboratory on Digital Preservation and Innovative Technologies for the Culture of Traditional Villages and Towns, Hengyang Normal University, Hengyang 421002, China
  • Received:2019-09-24 Revised:2020-06-05 Published:2020-11-25
  • Supported by:
    The National Natural Science Foundation of China (No. 41961055);The Outstanding Youth Project of Education Department of Hunan Province (Nos. 19B078;19C0272);The Hengyang Social Science Fund (No. 2018B (I) 002);The Open Fund Project of National-Local Joint Engineering Laboratory on Digital Preservation and Innovative Technologies for the Culture of Traditional Villages and Towns (No. CTCZ18K01);The National Key Research and Development Program of China (No. 2018YFE0207800)

摘要: 针对经典Delaunay三角网平面点集形状重构方法存在的经验参数确定和容易出现不符合实际情况的碎洞问题,提出了一种顾及Gestalt邻近与简化原则的Delaunay三角网平面点集形状重构的算法SRGT。首先根据邻近性原则,采用双极差粗差探测技术来识别和定位Delaunay三角网中的极长边,逐步细化三角网中的内外边界;然后基于简化性原则,将形状重构的碎洞优化转化为粗差探测问题,并利用3σ粗差探测原则来实现碎洞的剔除。采用模拟与真实数据验证了本文算法的有效性。与4种经典算法(α-shape、χ-shape、边长比约束法以及∂RGG)进行对照试验,表明本文算法的优越性。模拟数据表明SRGT在面状点集为均匀或随机分布时,无须设置先验参数即可有效提取复杂形状的内外边界,并且L2误差范数值明显低于其余4种方法。真实案例的试验结果也表明本文算法在工程实践中具有良好应用效果。

关键词: 平面点集, Delaunay三角网, Gestalt原则, 形状重建, 粗差探测

Abstract: The widely used shape reconstruction algorithms based on Delaunay triangulation are far from sophisticated,and some problems are to be further addressed. First of all, the current methods involve a few of user-defined parameters, obstructing the effective use of them in practice. Secondly, the current methods cannot guarantee the perfect shape reconstruction if a planar point set follows a randomly distribution. To overcome these aforementioned problems, a method for planar point set shape reconstruction, namely SRGT (shape reconstruction based on Gestalt) based on Gestalt proximity and simplification is developed. On the one hand, based on the proximity theory, the gross error detection technique is used to identify and locate the extreme long edges in the Delaunay triangulation network, and then the inner and outer boundaries of the Delaunay are refined step by step. On the other hand, according to the simplification theory of Gestalt, the inner and outer holes are optimized by gross error detection technique again, and finally the small holes are removed from the list of inner boundary set. To validate the effectiveness of the proposed method, the SRGT was validated on several cases, and 4 widely used algorithms, i.e. α-shape, χ-shape, ∂RGG, and edge length ratios were selected for comparisons. The results demonstrate that SRGT can achieve the fine shape reconstruction from planar point sets in both uniform and random distribution. Moreover, the SRGT generally outperforms the other 4 methods in terms of the L2 measure. Finally, the shape reconstructions with the SRGT using two actual datasets corresponding to typical GIS applications were implemented to verify the effectiveness of the proposed method, and the results consistently suggest the superior ability of the SRGT.

Key words: planar point set, Delaunay triangulation, Gestalt, shape reconstruction, gross error detection

中图分类号: