The crust and the β-skeleton:: Combinatorial curve reconstruction

被引：264

作者：

Amenta, N ^{[1
]}

Bern, M

Eppstein, D

机构：

[1] Univ Texas, Dept Comp Sci, Austin, TX 78712 USA

[2] Xerox Corp, Palo Alto Res Ctr, Palo Alto, CA 94304 USA

[3] Univ Calif Irvine, Dept Informat & Comp Sci, Irvine, CA 92697 USA

来源：

GRAPHICAL MODELS AND IMAGE PROCESSING | 1998年 / 60卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/gmip.1998.0465

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We construct a graph on a planar point set, which captures its shape in the following sense: if a smooth curve is sampled densely enough, the graph on the samples is a polygonalization of the curve, with no extraneous edges. The required sampling density varies with the local feature size on the curve, so that areas of less detail can be sampled less densely. We give two different graphs that, in this sense, reconstruct smooth curves: a simple new construction which we call the crust, and the beta-skeleton, using a specific value of beta. (C) 1998 Academic Press.

引用

页码：125 / 135

页数：11

共 19 条

[1] [Anonymous], 1994, COMPUTATIONAL GEOMET
[2] Attali D., 1997, Proceedings of the Thirteenth Annual Symposium on Computational Geometry, P248, DOI 10.1145/262839.262980
[3] BAJAJ CL, 1995, P SIGGRAPH, P109
[4] Blum H., 1967, MODELS PERCEPTION SP, P362, DOI DOI 10.1142/S0218654308001154
[5] CONTINUOUS SKELETON COMPUTATION BY VORONOI DIAGRAM
BRANDT, JW
ALGAZI, VR
[J]. CVGIP-IMAGE UNDERSTANDING, 1992, 55 (03): : 329 - 338
[6] CHEW LP, P ACM S COMP GEOM 19, P274
[7] Curless B., 1996, Computer Graphics Proceedings. SIGGRAPH '96, P303, DOI 10.1145/237170.237269
[8] EDELSBRUNNER H, 1983, IEEE T INFORM THEORY, V29, P551, DOI 10.1109/TIT.1983.1056714
[9] Edelsbrunner H., 1987, ALGORITHMS COMBINATO
[10] Hoppe Hugues., 1992, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, P71, DOI [10.1145/133994.134011, DOI 10.1145/133994.134011]

← 1 2 →