THE ARC TREE - AN APPROXIMATION SCHEME TO REPRESENT ARBITRARY CURVED SHAPES

被引：21

作者：

GUNTHER, O ^{[1
]}

WONG, E ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY LAWRENCE BERKELEY LAB,DEPT ELECT ENGN & COMP SCI,BERKELEY,CA 94720

来源：

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING | 1990年 / 51卷 / 03期

关键词：

Computer Vision - Data Processing--Data Structures - Mathematical Techniques--Trees;

D O I：

10.1016/0734-189X(90)90006-H

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper introduces the arc tree, a hierarchical data structure to represent arbitrary curved shapes. The arc tree is a balanced binary tree that represents a curve of length l such that any subtree whose root is on the kth tree level is representing a subcurve of length l 2k. Each tree level is associated with an approximation of the curve; lower levels correspond to approximations of higher resolution. Based on this hierarchy of detail, queries such as point search or intersection detection and computation can be solved in a hierarchical manner. Algorithms start out near the root of the tree and try to solve the queries at a very coarse resolution. If that is not possible, the resolution is increased where necessary. We describe and analyze several such algorithms to compute a variety of set and search operators. Various related approximation schemes to represent curved shapes are also discussed. © 1990.

引用

页码：313 / 337

页数：25

共 13 条

[1] STRIP TREES - A HIERARCHICAL REPRESENTATION FOR CURVES [J].

BALLARD, DH .

COMMUNICATIONS OF THE ACM, 1981, 24 (05) :310-321

[2]

Bezier Pierre, 1974, COMPUT AIDED GEOM D, P127

[3]

Boor CD., 1978, PRACTICAL GUIDE SPLI

[4] REPRESENTATION OF MANY-SIDED POLYGONS AND POLYGONAL LINES FOR RAPID PROCESSING [J].

BURTON, W .

COMMUNICATIONS OF THE ACM, 1977, 20 (03) :166-171

[5]

Faux ID, 1979, COMPUTATIONAL GEOMET

[6]

GUNTHER O, 1989, FAWTR89012 TECHN REP

[7]

HOPCROFT JE, 1987, ALGORITHMIC GEOMETRI, V1

[8] COMPUTATIONAL-GEOMETRIC METHODS FOR POLYGONAL APPROXIMATIONS OF A CURVE [J].

IMAI, H ;

IRI, M .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1986, 36 (01) :31-41

[9]

Mandelbrot B. B., 1977, FRACTALS FORM CHANCE

[10]

Pavlidis T., 1982, ALGORITHMS GRAPHICS

← 1 2 →