多约束的平面点集形状重构方法

doi:10.11947/j.AGCS.2017.20160122

测绘学报 ›› 2017, Vol. 46 ›› Issue (2): 253-264.doi: 10.11947/j.AGCS.2017.20160122

多约束的平面点集形状重构方法

朱杰^1,2, 孙毅中^1,2

1. 南京师范大学虚拟地理环境教育部重点实验室, 江苏南京 210023;
2. 江苏省地理信息资源开发与利用协同创新中心, 江苏南京 210023

收稿日期:2016-03-30 修回日期:2016-10-27 出版日期:2017-02-20 发布日期:2017-03-07
作者简介:朱杰(1989-),男,博士生,研究方向为城市空间数据表达与挖掘。E-mail:Chu_Je@163.com
基金资助:
国家自然科学基金（41671392）；公安部科技强警基础工作专项（2015GABJC39）

An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints

ZHU Jie^1,2, SUN Yizhong^1,2

1. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210023, China;
2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China

Received:2016-03-30 Revised:2016-10-27 Online:2017-02-20 Published:2017-03-07
Contact: 孙毅中 E-mail:sunyizhong_cz@163.com
Supported by:
The National Natural Science Foundation of China (No.41671392),Special Program for basic research of Sci-tech Police of Ministry of Public Security (No.2015GABJC39)

摘要/Abstract

摘要： 针对平面点集空间分布的复杂性，本文提出了一种基于Delaunay三角网的平面点集形状重构方法。首先采用一种简单且实用的数据结构以表达Delaunay三角网中嵌入的几何信息和拓扑信息，然后由外向内迭代过滤Delaunay三角网得到一个大概边界，最后进一步考虑边界的凹凸信息和空洞现象，获取最终的精细边界。试验结果表明与其他典型的Delaunay三角网重构方法相比，本文提出的算法能更好地适用于平面点集空间分布的复杂性，通过所构建的数学模型实现了凸凹多边形内外边界提取。

关键词: 平面点集, 形状重构, Delaunay三角网, 多约束, GIS

Abstract: An efficient algorithm to boundary representation from a planar point set in order to adapt the complexity of spatial distribution was presented in this paper. At first, an appropriate and practical data structure was designed to express geometric information and topological information, which provides an easy access to links embedded in DT serving as a basis for the filtering procedures; then the algorithm generates rough boundary based on an iterative removal of Delaunay triangulation. Furthermore, a mathematic formulation for cavities and holes was given and a statistical method to detect them was designed. Finally, a series of experiments including both simulated and real data sets to validate the effectiveness and practicability of our algorithm was conducted.

Key words: planar point set, shape reconstruction, Delaunay triangulation, multi-constraints, GIS

中图分类号:

P208

朱杰, 孙毅中. 多约束的平面点集形状重构方法[J]. 测绘学报, 2017, 46(2): 253-264.

ZHU Jie, SUN Yizhong. An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 253-264.

参考文献

[1] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2):175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2):175-181.
[2] GALTON A,DUCKHAM M.What is the Region Occupied by a Set of Points?[M]//RAUBAL M, MILLER H J, FRANK A U, et al. Geographic Information Science. Berlin Heidelberg:Springer, 2006:81-98.
[3] 李佳田,康顺,罗富丽.利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43(12):1300-1306. DOI:10.13485/j.cnki.11-2089.2014.0166. LI Jiatian, KANG Shun, LUO Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12):1300-1306. DOI:10.13485/j.cnki.11-2089.2014.0166.
[4] ZHU Chao, ZHANG Xiaopeng, HU Baogang, et al. Reconstruction of Tree Crown Shape from Scanned Data[M]//PAN Zhigeng, ZHANG Xiaopeng, RHALIBI A E, et al. Technologies for E-learning and Digital Entertainment. Berlin Heidelberg:Springer, 2008:745-756.
[5] 孙颖, 张新长, 康停军, 等. 改进GAC模型在点云和影像自动提取建筑物边界中的应用[J]. 测绘学报, 2013, 42(3):337-343, 350. SUN Ying, ZHANG Xinchang, KANG Tingjun, et al. Improved GAC Model for Automatic Building Extraction from LiDAR Point Clouds and Aerial Image[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3):337-343, 350.
[6] 孙颖, 张新长, 罗国玮. 从机载激光雷达点云提取建筑物屋顶边界的活动轮廓模型改进方法[J]. 测绘学报, 2014, 43(6):620-626, 636. DOI:10.13485/j.cnki.11-2089.2014.0106. SUN Ying, ZHANG Xinchang, LUO Guowei. Improved Active Contour Model for Building Roof Boundary Extraction from LiDAR Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6):620-626, 636. DOI:10.13485/j.cnki.11-2089.2014.0106.
[7] KISILEVICH S, MANSMANN F, BAK P, et al. Where Would You Go on Your Next Vacation? A Framework for Visual Exploration of Attractive Places[C]//Proceedings of 2010 Second International Conference on Advanced Geographic Information Systems, Applications, and Services(GEOPROCESSING). St. Maarten:IEEE, 2010:21-26.
[8] HU Yingjie,GAO Song, JANOWICZ K, et al. Extracting and Understanding Urban Areas of Interest Using Geotagged Photos[J]. Computers, Environment and Urban Systems, 2015, 54:240-254.
[9] LIU Yu, YUAN Yihong, XIAO Danqing, et al. A Point-set-based Approximation for Areal Objects:A Case Study of Representing Localities[J]. Computers, Environment and Urban Systems, 2010, 34(1):28-39.
[10] SAMPATH A,SHAN Jie. Building Boundary Tracing and Regularization from Airborne LiDAR Point Clouds[J]. Photogrammetric Engineering & Remote Sensing, 2007, 73(7):805-812.
[11] 程效军, 何桂珍. 适用于多值曲面修复的空洞边界提取方法及应用[J]. 测绘学报, 2012, 41(6):831-837. CHENG Xiaojun, HE Guizhen. The Method and Application of Hole Boundary Extraction for Multi-valued Surface Repair[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):831-837.
[12] 李雯静, 李少宁, 邱佳, 等. 凸壳内缩法进行多密度离散点群边界检测[J]. 测绘科学, 2014, 39(9):126-129. LI Wenjing, LI Shaoning, QIU Jia, et al. Boundary Detection of Multi-density Point Cluster Using Convex Hull Retracted Method[J]. Science of Surveying and Mapping, 2014, 39(9):126-129.
[13] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4):266-286.
[14] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the Shape of a Set of Points in the Plane[J]. IEEE Transactions on Information Theory, 1983, 29(4):551-559.
[15] KOLINGEROVÁ I, ŽALIK B. Reconstructing Domain Boundaries Within A Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9):1310-1319.
[16] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10):3224-3236.
[17] 黄先锋, 程晓光, 张帆, 等. 基于边长比约束的离散点准确边界追踪算法[J]. 武汉大学学报(信息科学版), 2009, 34(6):688-691. HUANG Xianfeng, CHENG Xiaoguang, ZHANG Fan, et al. Boundary Tracing from Irregular Points Based on Ratio of Edge Length[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6):688-691.
[18] PEETHAMBARAN J, MUTHUGANAPATHY R. A Non-parametric Approach to Shape Reconstruction from Planar Point Sets Through Delaunay Filtering[J]. Computer-Aided Design, 2015, 62:164-175.
[19] CHAUDHURI A R, CHAUDHURI B B, PARUI S K. A Novel Approach to Computation of the Shape of A Dot Pattern and Extraction of Its Perceptual Border[J]. Computer Vision and Image Understanding, 1997, 68(3):257-275.
[20] MELKEMI M, DJEBALI M. Computing the Shape of A Planar Points Set[J]. Pattern Recognition, 2000, 33(9):1423-1436.
[21] CHEVALLIER N, MAILLOT Y. Boundary of a Non-uniform Point Cloud for Reconstruction:Extended Abstract[C]//Proceedings of the 27th Annual ACM Symposium on Computational Geometry. New York:ACM, 2011:510-518.
[22] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3):29.
[23] 顾天奇, 张雷, 冀世军, 等. 封闭离散点的曲线拟合方法[J]. 吉林大学学报(工学版), 2015, 45(2):437-441. GU Tianqi, ZHANG Lei, JI Shijun, et al. Curve Fitting Method for Closed Discrete Points[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2):437-441.
[24] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2):249-261.
[25] MISTRY S,NIRANJAN U N, GOPI M. Puzzhull:Cavity and Protrusion Hierarchy to Fit Conformal Polygons[J]. Computer-Aided Design, 2014, 46:233-238.
[26] 武晓波, 王世新, 肖春生. Delaunay三角网的生成算法研究[J]. 测绘学报, 1999, 28(1):28-35. WU Xiaobo, WANG Shixin, XIAO Chunsheng. A New Study of Delaunay Triangulation Creation[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(1):28-35.
[27] 艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3):302-308. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):302-308.
[28] ESTIVILL-CASTRO V,LEE I.Argument Free Clustering for Large Spatial Point-data Sets Via Boundary Extraction from Delaunay Diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4):315-334.
[29] PAKHIRA M K, BANDYOPADHYAY S, MAULIK U. Validity Index for Crisp and Fuzzy Clusters[J]. Pattern Recognition, 2004, 37(3):487-501.
[30] ESTIVILL-CASTRO V,LEE I. Multi-level Clustering and Its Visualization for Exploratory Spatial Analysis[J]. GeoInformatica, 2002, 6(2):123-152.
[31] 沈蔚, 李京, 陈云浩, 等. 基于LiDAR数据的建筑轮廓线提取及规则化算法研究[J]. 遥感学报, 2008, 12(5):692-698. SHEN Wei, LI Jing, CHEN Yunhao, et al. Algorithms Study of Building Boundary Extraction and Normalization Based on LIDAR Data[J]. Journal of Remote Sensing, 2008, 12(5):692-698.

多约束的平面点集形状重构方法

An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘振东, 戴昭鑫, 李成名, 刘晓丽. 三维GIS场景与多路视频融合的对象快速确定法[J]. 测绘学报, 2020, 49(5): 632-643.
[2]	姜三, 江万寿. Delaunay三角网约束下的影像稳健匹配方法[J]. 测绘学报, 2020, 49(3): 322-333.
[3]	颜金彪, 吴波, 彭馨. 顾及Gestalt邻近与简化原则的平面点集形状重建[J]. 测绘学报, 2020, 49(11): 1485-1496.
[4]	李成名, 殷勇, 武鹏达, 刘晓丽. 一种聚集性面群中毗邻区自动识别与处理方法[J]. 测绘学报, 2019, 48(3): 363-373.
[5]	李清泉, 周宝定, 马威, 薛卫星. GIS辅助的室内定位技术研究进展[J]. 测绘学报, 2019, 48(12): 1498-1506.
[6]	刘文凯, 刘启亮, 蔡建南. 自然邻域支持下的空间同位模式挖掘方法[J]. 测绘学报, 2019, 48(1): 95-105.
[7]	杨伟, 艾廷华. 轨迹分割与图层融合的车辆轨迹线构建道路地图方法[J]. 测绘学报, 2018, 47(12): 1650-1659.
[8]	何撼东, 胡迪, 闾国年, 李安波, 李军利. 几何与语义统一的区域地质构造GIS数据模型[J]. 测绘学报, 2017, 46(8): 1058-1068.
[9]	杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2): 237-245.
[10]	唐炉亮, 阚子涵, 段倩, 李清泉. 一种时空路径支持下的车辆油耗与排放估计方法[J]. 测绘学报, 2017, 46(12): 2024-2031.
[11]	黎夏, 李丹, 刘小平. 地理模拟优化系统(GeoSOS)及其在地理国情分析中的应用[J]. 测绘学报, 2017, 46(10): 1598-1608.
[12]	兰泽英, 刘洋. 领域知识辅助下基于多尺度与主方向纹理的遥感影像土地利用分类[J]. 测绘学报, 2016, 45(8): 973-982.
[13]	郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8): 1001-1007.
[14]	汶建龙, 杨春成, 符浩军, 岳志兰. 一种地图跨媒介出版数据模型[J]. 测绘学报, 2015, 44(8): 936-942.
[15]	韩元利. 网格总分并行式Delaunay三角网建模方法[J]. 测绘学报, 2015, 44(6): 702-708.