Polar-Natural Distance and Curve Reconstruction
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We propose a new distance measure between 2-dimensional points to provide a total order for an entire point set and to reflect the correct geometric meaning of the naturalness of the point ordering. In general, there is no total order for 2-dimensional point sets, so curve reconstruction algorithms do not solve the self-intersection problem because the distance used in the previous methods is the Euclidean distance. A natural distance based on Brownian motion was previously proposed to solve the self-intersection problem. However, the distance reflects the wrong geometric meaning of the naturalness. In this paper, we correct the disadvantage of the natural distance by introducing a polar-natural distance, and we also propose a new curve reconstruction algorithm that is based on the polar-natural distance. Our experiments show that the new distance adequately reflects the correct geometric meaning, so non-simple curve reconstruction can be solved.
Abstract
We propose a new distance measure between 2-dimensional points to provide a total order for an entire point set and to reflect the correct geometric meaning of the naturalness of the point ordering. In general, there is no total order for 2-dimensional point sets, so curve reconstruction algorithms do not solve the self-intersection problem because the distance used in the previous methods is the Euclidean distance. A natural distance based on Brownian motion was previously proposed to solve the self-intersection problem. However, the distance reflects the wrong geometric meaning of the naturalness. In this paper, we correct the disadvantage of the natural distance by introducing a polar-natural distance, and we also propose a new curve reconstruction algorithm that is based on the polar-natural distance. Our experiments show that the new distance adequately reflects the correct geometric meaning, so non-simple curve reconstruction can be solved.
참고문헌 (12)
- H. Hoppe, "Surface Reconstruction from unorganized points", Proc. SIGGRAPH’ 92, pp.71~78 (1992)
- J. D. Boissonnat, "Three dimentional reconstruction of complex shapes based on the Delaunay triangulation", Proc. of Biomedical Image Process, Biomed. Visualization, pp.964~975 (1993)
- Philsu Kim, "Point ordering with the natural distance based on Brownian motion", Mathematical problems in engineering, 2010, pp.17~ (2010)
- J. D. Boissonnat, "Smooth surface reconstruction via natural neighbor interpolation of distance functions", Comp. Geom. Theo. Appl, 22, pp.185~203 (2002)
- H. Edelsbrunner, "On the shape of a set of points in the plane", IEEE Trans. Information Theory, pp.551~559 (1983)
- D. Attali, "-regular shape reconstruction from unorganized points", Proc. of 13th Ann. Sympos. Comput. Geom, pp.248~253 (1997)
- N. Amenta, "The crust and the beta-skeleton: combinatorial curve reconstruction", Graphical Models, 60, pp.125~135 (1998)
- T. K. Dey, "A simple provable algorithm for curve reconstruction", Proc. 10th. ACM-SIAM Symp. Discr. Algorithms, pp.893~894 (1999)
- L. Fang, "Fitting 3D curves to unorganized data points using deformable curves", Proc.of CG International’92, pp.535~543 (1992)
- J. P. Dedieu, "Algorithms for ordering unorganized points along parametrized curves", Numerical Algorithms, 6, pp.160~200 (1994)
- G. Taubin, "Implicit simplicial models for adaptive curve reconstruction", IEEE Trans. on Pattern Analysis and Machine Intelligence, 18, pp.321~325 (1996)
- Thanh An Nguyen, "VICUR: A humanvision- based algorithm for curve reconstruction", Robotics and Computer Integrated Manufacturing, 24, pp.824~834 (2008)