COMPUTING SOME DISTANCE FUNCTIONS BETWEEN POLYGONS

被引：15

作者：

ATALLAH, MJ ^{[1
]}

RIBEIRO, CC ^{[1
]}

LIFSCHITZ, S ^{[1
]}

机构：

[1] UNIV RIO JANEIRO,DEPT ELECT ENGN,CAIXA POSTAL 38063,GAVEA 22452,RJ,BRAZIL

来源：

PATTERN RECOGNITION | 1991年 / 24卷 / 08期

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL GEOMETRY; POLYGONS; DISTANCE COMPUTATION; HAUSDORFF DISTANCE; PATTERN RECOGNITION; CONTOUR FITTING; ROBOT VISION; ALGORITHMS;

D O I：

10.1016/0031-3203(91)90045-7

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We present algorithms for computing some distance functions between two (possibly intersecting) polygons, in both the convex and nonconvex cases. The interest for such distance functions comes from applications in robot vision, pattern recognition and contour fitting. We present an optimal EREW-PRAM parallel algorithm for the case when the input polygons are convex, and an essentially quadratic sequential algorithm for the case of arbitrary polygons (possibly with holes).

引用

页码：775 / 781

页数：7

共 18 条

[11] OPTIMAL MERGING AND SORTING ON THE EREW PRAM [J].

HAGERUP, T ;

RUB, C .

INFORMATION PROCESSING LETTERS, 1989, 33 (04) :181-185

[12]

HUTTENLOCHER DP, 1990, 6TH P ACM S COMP GEO, P340

[13] A NEW LINEAR ALGORITHM FOR INTERSECTING CONVEX POLYGONS [J].

OROURKE, J ;

CHIEN, CB ;

OLSON, T ;

NADDOR, D .

COMPUTER GRAPHICS AND IMAGE PROCESSING, 1982, 19 (04) :384-391

[14] MAINTENANCE OF CONFIGURATIONS IN THE PLANE [J].

OVERMARS, MH ;

VANLEEUWEN, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 23 (02) :166-204

[15]

Preparata F. P., 2012, COMPUTATIONAL GEOMET

[16]

RIBEIRO CC, 1990, GERAD G9023 EC HAUT

[17] AN O(N-LOG-N) ALGORITHM FOR THE VORONOI DIAGRAM OF A SET OF SIMPLE CURVE SEGMENTS [J].

YAP, CK .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (04) :365-393

[18]

[No title captured]

← 1 2 →