期刊
COMPUTERS & GRAPHICS-UK
卷 51, 期 -, 页码 90-97出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cag.2015.05.025
关键词
Delaunay Triangulation; Reconstruction; Dot pattern; Boundary sample
资金
- Ministry of Human Resource Development, Government of India
Reconstruction problem in R-2 computes a polygon which best approximates the geometric shape induced by a given point set, S. In R-2, the input point set can either be a boundary sample or a dot pattern. We present a Delaunay-based, unified method for reconstruction irrespective of the type of the input point set. From the Delaunay Triangulation (DT) of S, exterior edges are successively removed subject to circle and regularity constraints to compute a resultant boundary which is termed as ec-shape and has been shown to be homeomorphic to a simple closed curve. Theoretical guarantee of the reconstruction has been provided using r-sampling. In practice, our algorithm has been shown to perform well independent of sampling models and this has been illustrated through an extensive comparative study with existing methods for inputs having varying point densities and distributions. The time and space complexities of the algorithm have been shown to be O(n log n) and O(n) respectively, where n is the number of points in S. (C) 2015 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据