An optimal morphing between polylines

被引：12

作者：

Bespamyatnikh, S ^{[1
]}

机构：

[1] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2002年 / 12卷 / 03期

关键词：

morphing; polylines; skeleton; shortest path;

D O I：

10.1142/S0218195902000839

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We address the problem of continuously transforming or morphing one simple polyline into another so that every point p of the initial polyline moves to a point g of the final polyline using the geodesic shortest path from p to q. We optimize the width of the morphing, that is, the longest path made by a point on the polyline. We present an algorithm for finding the minimum width morphing in O(n(2)) time using O(n) space, where n is the total number of vertices of polylines. This improves the previous algorithm(7) by a factor of log(2) n.

引用

页码：217 / 228

页数：12

共 12 条

[1] Matching shapes with a reference point [J].

Aichholzer, O ;

Alt, H ;

Rote, G .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1997, 7 (04) :349-363

[2]

Alt H, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P121, DOI 10.1016/B978-044482537-7/50004-8

[3] CONGRUENCE, SIMILARITY, AND SYMMETRIES OF GEOMETRIC OBJECTS [J].

ALT, H ;

MEHLHORN, K ;

WAGENER, H ;

WELZL, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (03) :237-256

[4] COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES [J].

ALT, H ;

GODAU, M .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) :75-91

[5]

ALT H, 2001, P 18 INT S THEOR ASP, P63

[6]

Efrat A, 2001, SIAM PROC S, P680

[7]

Efrat A, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P927

[8] Morphing simple polygons [J].

Guibas L. ;

Hershberger J. ;

Suri S. .

Discrete & Computational Geometry, 2000, 24 (1) :1-34

[9] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].

GUIBAS, L ;

HERSHBERGER, J ;

LEVEN, D ;

SHARIR, M ;

TARJAN, RE .

ALGORITHMICA, 1987, 2 (02) :209-233

[10] COMPUTING MINIMUM LENGTH PATHS OF A GIVEN HOMOTOPY CLASS [J].

HERSHBERGER, J ;

SNOEYINK, J .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (02) :63-97

← 1 2 →