Shape reconstruction from unorganized points using Voronoi diagrams
SCIE
SCOPUS
- Title
- Shape reconstruction from unorganized points using Voronoi diagrams
- Authors
- Lee, S; Choi, Y; Kim, K
- Date Issued
- 2003-01
- Publisher
- SPRINGER-VERLAG LONDON LTD
- Abstract
- Given only a set of points, without any geometric information such as the adjacency among the points, the scanning order or the scanning direction, it is a difficult problem to reconstruct a surface model corresponding to the original shape. For the reconstruction of open shapes, many effective approaches have been proposed. It is, however, hard to find a robust and effective method for the reconstruction of closed shapes. In this paper, an algorithm is proposed to reconstruct a three-dimensional closed shape from a set of good sample points using the properties of Delaunay triangulation and Voronoi diagrams. The proposed method consists of three steps; (1) constructing a convex hull consisting of mutually exclusive tetrahedra by 3D Delaunay triangulation of input points, (2) generating a Voronoi diagram of input points by utilising the properties of Delaunay triangulation, and (3) extracting the triangles on the shape boundary, defined by input points, after selecting the tetrahedra which are contained inside the shape using the properties of Voronoi diagrams. The proposed method in this paper has some advantages compared to the previous approaches. First, the distance parameter, such as a in the a-shape approach, is not required in the proposed approach. The determination of a proper parameter by trial and error is not appropriate, especially in the automation of shape reconstruction. Secondly, the time complexity of the proposed approach is 0(n) since, in a single pass, this algorithm determines whether each tetrahedron is located inside or outside the shape boundary.
- Keywords
- Delaunay triangulation; shape reconstruction; Voronoi diagram; APPROXIMATION
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/18567
- DOI
- 10.1007/s001700300052
- ISSN
- 0268-3768
- Article Type
- Article
- Citation
- INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, vol. 21, no. 6, page. 446 - 451, 2003-01
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.