摘要: 以Voronoi图和Delaunay三角剖分为基础,针对二维闭合曲线集的采样点集,提出一种曲线重建算法。该算法按给定采样密度对曲线集进行采样,从而用一条或多条线段准确地重建曲线集,将采样点密集程度的度量定义为点集的本地特征值度量,以此要求采样达到一定的密集程度。理论分析证明该算法的时间复杂度为O(nlogn)。
关键词:
曲线重建,
点的局部特征值,
Voronoi图,
Delaunay三角剖分
Abstract: Based on Voronoi diagram and Delaunay triangulation and aiming at sample set of 2D closed curve set, this paper proposes a curves reconstruction algorithm. It samples the curve set according to sample dense to correctly reconstruct curve set with one or some lines. The measurement of dense extent is defined as local feature size of point, and samples are demanded to achieve a certain dense degree. Analysis proves that time complexity of the algorithm is O(nlogn).
Key words:
curve reconstruction,
local eigenvalue of point,
Voronoi diagram,
Delaunay triangulation
中图分类号:
钟华, 王加阳, 谭正华. 基于Voronoi图和三角剖分的闭合曲线重建[J]. 计算机工程, 2010, 36(21): 81-82,85.
ZHONG Hua, WANG Jia-Yang, TAN Zheng-Hua. Closed Curve Reconstruction Based on Voronoi Diagram and Triangulation[J]. Computer Engineering, 2010, 36(21): 81-82,85.