AN ONLINE ALGORITHM FOR CONSTRAINED DELAUNAY TRIANGULATION

被引:46
作者
DEFLORIANI, L [1 ]
PUPPO, E [1 ]
机构
[1] CNR,IST MATEMAT APPL,I-16132 GENOA,ITALY
来源
CVGIP-GRAPHICAL MODELS AND IMAGE PROCESSING | 1992年 / 54卷 / 04期
关键词
D O I
10.1016/1049-9652(92)90076-A
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
A constrained Delaunay triangulation is a Delaunay triangulation of a set of points and straight-line segments. A constrained Delaunay triangulation is a basic tool for describing a topographic surface in several applications. In this paper, the definition of constrained Delaunay triangulation is introduced and its basic properties are discussed. Existing algorithms for constrained Delaunay triangulation are briefly analyzed. A new on-line algorithm for constrained Delaunay triangulation that is based on the stepwise refinement of an existing triangulation by the incremental insertion of points and constraint segments is proposed. © 1992.
引用
收藏
页码:290 / 300
页数:11
相关论文
共 33 条
[11]  
CHEW LP, 1987, 3RD P ACM S COMP GEO, P216
[12]   APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY .2. [J].
CLARKSON, KL ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421
[13]   DELAUNAY-BASED REPRESENTATION OF SURFACES DEFINED OVER ARBITRARILY SHAPED DOMAINS [J].
DEFLORIANI, L ;
FALCIDIENO, B ;
PIENOVI, C .
COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1985, 32 (01) :127-140
[14]  
DEFLORIANI L, 1988, 9TH P INT C PATT REC
[15]  
DEFLORIANI L, 1991, CNR891 I MAT APPL TE
[16]  
DEFLORIANI L, 1989, IEEE COMPUT GRAP MAR
[17]  
Edelsbrunner H, 1987, ALGORITHMS COMBINATO
[18]  
FIELD DA, 1986, 2ND P ANN ACM S COMP, P246
[19]  
Fowler R., 1979, COMPUT GRAPH, V13, P199
[20]  
JOE B, 1989, DUALITY CONSTRUCTION