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

doi:10.11947/j.AGCS.2017.20160122

Abstract

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

CLC Number:

P208

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.

References

[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.