The convex hull of rational plane curves

被引：14

作者：

Elber, G ^{[1
]}

Kim, MS

Heo, HS

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] Seoul Natl Univ, Dept Comp Engn, Seoul 151742, South Korea

[3] POSTECH, Dept Comp Sci, Pohang 790784, South Korea

来源：

GRAPHICAL MODELS | 2001年 / 63卷 / 03期

关键词：

convex hull; point-curve tangent; bi-tangent; curve-curve tangent; zero-set finding; rational curve; B-spline; symbolic computation;

D O I：

10.1006/gmod.2001.0546

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many redundant curve segments. (C) 2001 Academic Press.

引用

页码：151 / 162

页数：12

共 15 条

[1]

[Anonymous], P INT C SHAP MOD APP

[2]

[Anonymous], 2001, P 6 ACM S SOL MOD AP

[3] CONVEX HULLS OF OBJECTS BOUNDED BY ALGEBRAIC-CURVES [J].

BAJAJ, C ;

KIM, MS .

ALGORITHMICA, 1991, 6 (04) :533-553

[4]

Do Carmo Manfredo P, 2016, Differential geometry of curves & surfaces, Vsecond

[5] COMPUTATIONAL GEOMETRY IN A CURVED WORLD [J].

DOBKIN, DP ;

SOUVAINE, DL .

ALGORITHMICA, 1990, 5 (03) :421-457

[6]

Elber G, 1992, THESIS U UTAH

[7] FINDING THE CONVEX-HULL OF A SIMPLE POLYGON [J].

GRAHAM, RL ;

YAO, FF .

JOURNAL OF ALGORITHMS, 1983, 4 (04) :324-331

[8] ON FINDING THE CONVEX-HULL OF A SIMPLE POLYGON [J].

LEE, DT .

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1983, 12 (02) :87-98

[9]

LEE IK, 1992, VISUAL COMPUTING, P533

[10] SOLVING SYSTEMS OF POLYNOMIAL EQUATIONS [J].

MANOCHA, D .

IEEE COMPUTER GRAPHICS AND APPLICATIONS, 1994, 14 (02) :46-55

← 1 2 →