Results in Mathematics Vol. 12 (1987)

0378-6218/87/020027 - 10$1.50+0 . 20/0 (c) 1987 Birkhallser Verlag, Basel

Parallel-Beziersegmente

Randolf Arnold, Fachbereich Hathematik, Universitiit Dortmund

Einleitunq

Die Parallelkurve einer ebenan polynomial paramatrisierten

j(urve besitzt 1. a . keine polynomie:le Darstallunq. 1m Bereich

der Bezierkurven erqibt s ich daraus das Problem, zu einem

qeqebenen Bezierseqment X ein Bezierseqment Y qleichen Grades

zu konstruieren, das die Pa rallelkurve X4 von X zum Abstand S

bzql. dar Hausdorff-Hetrik m6qlichst qut approximiert .

Es wird ein Approximationsverfahren fur den kubischen Fall

anqeqeben und qezeiqt, daB sich der Hausdorff-Abstand von X4

und Y uber ein alqebraisches Gleichunqssystem in zwei

Unbestimmten berechnen laBt .

1 , Problemstellunq

Ein ebenas Beziersegment vom Grad n ist eine Polynom­

kurve X der Form

" (1) x( t I t;;:[O,1]

mi t

b, E JF

Die vektoriellen Koeffizienten bo, . ,b. heiBen Bezierpunkte

von X. Ober die qaometrischen Eiqanschaften dar Bezierseqmen­

ta und der aus Bezierseqmenten zusammenqlsetzten Dezierkurven

sind zshlreiche Arbeiten erschienen, siehe z . B. [2J, [3 1.

An dieser Stella solI nun ain spezielles Problem sus diesem

Themenkreis behandelt werden:

28

Bezeichnet man den Hauptnormalenvektor aines regularsn

Beziet"seqmentes X mit N, so wird durch

'" .. x(t) + olHt) t € [0,11

die Parallelkurve X6 von X 2um Abstand & E R parametrisiert.

Die Frenet-Ableitunqsgleichungen (siehe [101, S. 8) liafern

(3) XI'" (1 - &k)x'

mit k( tJ als Krijmmunq von X im Punkt x( t). Die For-derung

(4) -bk>Q

sichert nseh (3) die Reqularitlit von X6 und die Obereinstim­

mung del' Krijmmunq8worzeichen von X und X6 in 2uqeordneten

Punkten.

b, b.

x b,

b.

x. n • 3

Fig."

Os X6 nur dann aine polynomiale Darstellunq besitzt , wenn X

eine Stracke ist (siehe Izl1, ergibt sieh folgendes Problem

Arnold

Konstruiere ain Bezierseqment Y vom Grad n, das die

Parallelkurve X. von X 2um Abstand S bzql . der Hausdorff ­

Metrik moqlichst qut approximiert.

Wir werden una in dieser Arbeit i.w. aur den Fall n =3 be­

schranken und :zuali.t:zlich vorausset:zen, daB X 2usammen mit

seinen Randnormalen eine kompakte konvexe Henqe IU Xl C fP

ai nschli eBt :

Arnold

I

JI:( Xl

f i. q. 2 .

Verfahren 2ur Parallelkurvenapproximation 1m Bereieh der

B~2ierkurven, die auf allqemeineren Vorausset2unqen beruhen,

wurden in den Arbeiten Ill, [61, [71, 191 entwiekelt. Dabei

wurde in [1 I erstma ls eine Fehleruntersuehunq 1m Sinne der

Hausdorff-Hetrik durehqefUhrt.

2. Der Hausdorff-Abstand kompakter konvexer Hengen und

konvexer Kurven

Bevor wir uns der Definition und Konstruktion des MParallel­

e.2ierseqmentes" 2uwenden, betraehten wir die von HAUSDORfF

[4,51 definierte Hetrik D auf der Henqe der kompakten Teil-

menqen der euklidisehen Ebene (R 2 ,( , ») Fur 2wei kompakte

Henq en ',' C R' is t

(5l D( A, B) .. rna< ( rna IC mi n I a- b I , rna< mi n I a- b I ) , aEA bEB bEB •••

1.1 • ~> filr aER 2

Dieser Abstand liBt sieh wesentlieh einfaeher ausdrileken,

wenn man 2U 2wei kompakten konvexen Heng-en K, K' C R'

ilberqeht (siehl! 181,S.148)

(6) D( K, KO) ~ max I h( b) h' ( bl 1 .

beS I

Dabei sind h,ho : S'''(bER2 lib] "'l}-R mit

h( b) max (a, b> , hO ( bl

aEK

die Stilt2funktionen von K und KO .

" max <ao,b>

a ' EK o

29

30 Arnold

Vir betrac hten nun 3wei requlare lurven X.Y mit den folgenden

£i genschaften :

( i I

( i i)

X und Y haben gemeinsame Randnormalen .

X un d Y schlieBen 3uaammen mit ihren Randno rmalen

kompakte konvaxa Manqan KI Xl und K( YI ain.

Iii i I Di a Menqe X( XI n KC YI beai t3t i nn a r a Punkte .

I

r

FIg . 3.

Ea aeie n die StUtzfunkt io nan vo n KtX I und KtYl mit h und h"

bezeichnet . Sind X und Y in del" Fo rm x - x( t) und y ., y( t' l

t, to E [0,1 J parametri aie rt, so lassan s i c h lib_I" den Haupt­

normalanva ktor N vo n X vo m Pa rameter t abhanqi9_ Stilt3funk-

tionan 5,5' : [0, 1 J - R vo n X b2W. Y def i nia!"an :

at tl " h I b l s ' (t) :- h'(b) rUr b • -EN( t )

wo bei E E {1,- 1 } daa Vo rzeichen del" Krll mmunq von X angibt.

FUr den Hau a d o rff-Abstand vo n X und Y qilt nun die wic htiqe

Formal

17) DC X. Yl m., (s(t) - a ' (t) ( •. Jl s - a'lIoo .

tEl 0,1 J

Del" Saweis von (71 wurda in [ 1 J dur e hqefllhrt und be s teht aua

zw_ i Sc hri tten Zunaehst wird mitte ls (6) di e Glei chu ng

DIK(XI,X(Yl) - Is - s"l. na e h qe wiese n und anachlieBend libel" dia ursprllnoliehe Defini­

tio n l SI de a Hauad o rffabatandea die Ob e r einstimmu ng von

D( X. II und OJ KI XI, XI YI) ge2eiqt.

Arnold

Zur Berec:hnung von lis - s'~ ... sind die Extremstellen von 5 - S

'Zu bestimmen. :Zu diesem :Zwec:k wird y durc:h t' .. ¢Ii tl derart

umparametrisiert , dan fUr den Hauptnormalenvektor N' • HOit')

'Ion Y gilt:

H'c¢l(t » • H(t>

Aus (1) sowie der Konvexittit von X und Y folgt nun

(8) s - s' · <yo¢l- x, H>

Durc:h Differentiation von (8 ) erhalten wir ein notwendiges

Kriterium fUr die Extremstellen von s - 110'

1st t E [0,1) elne Extremstelle von s - 110', so existiert ein

t'E{0 , 1 ) mit

(9) Fi t , t ' )

Gi t, t' I

det (dx/dt, dy/dt')

• < yet') - x(t), dx/dt>

o o

D. h. An einer Extremstelle t vo n s - 5' hat der Differen'Z­

'1e kt or fyo. - xl ( t) der 'Zugehtirigen Kurvenpunkte die Ric:htunq

der gemei nsamen Hormalen H( t).

J. Definition und Eiqensc:haften eines Pprallel-Be'Zierseqmentes

1st nun ein Be'Ziersegment X 'Zusa mmen mit einem Abstand 0

unter den Vorausset'Zungen des ersten Absc:hnitts geqeben, so

erfUllen X und X, die Bedinqungen (il - (iii). Wir definieren

Ein requlores Be'Ziersegment Y heiBt Parallel-S''Zierseqment

von X 'Zum Abstand 0, wenn

(a) X und Y (damit auc:h X3 und Yl die Eigenac:haften (il - (iii>

besit'Zen,

(bl X, und Y in den Randpunkten Ubereinstimmen.

31

32 Arnold

b. _ I

.,?::::----..:::: ., ., C._I

& •• c,

f i 9. 4.

Dies8 Definition sichert bel elnem tanqentanstetigen Obergang

zweier Ausqanqsaeqmente X" X, ainen tanqentanatetigen Dber­

gsnq del' 2uqehoriqen Parallel-Bezierse<;Jmente Y., Yz . DarUber­

hinaus lassen eich die oben anqefUhrten Ergebnisse libel' den

Hausdorff-Abet.nd auf X~ und Y soweoden

Wir bezeichnen die vom Parameter t sbhinqiqe StUtzfunktion

von XI mit SI und arhaltan nach (7) :

( 1 01 DIX" Yl • , .. - "II .. . II', - &> - ,'i .. . ,,' - ,'J - &11 .. , lus (10) arksnnen wir. daft 88 zur Bestimmun9 von DC XI, Y)

ausreicht, die Extremat.llen von s - s· 2U barechnen. Ds X

und Y Bezierseqmenta sind, 1st das Gleichunqssystam (9)

alqebraisch. Geometrisch qedeutet sind also die Schnittpunkte

del' alqabraischen Kurven

F(t,to} · 0 G(t,to} . 0

im Einheitsquadrat 10,1 J2 zu suchen. 1m Fall n - 2 gelinCilt

dieses Vorhaben explizit, wobei gezei9t werden kann, daB im

oCCenen Intervall 10,1 [ hBchstens drei Extremstellen der

Funktion 110 - aO liegen. Auch der Fall n-3 liSt eich mit Hilfe

eines Rechners 9ut behandeln, da der Parameterwechsel 41 sus

Abschnitt 2 explizit angebbar ist (siehe [111 .

Arnold

4. Konstruktion eines Parallel-Beziersegmentes im Fall n a )

Sind X und Y requlare kubische Bezierseqmente und ist Y

Parallel-Bezierseqment von X zum Abstand 8, so gilt per def.

fUr die Bizierpunkte bo, ,bJ von X und Co, ,CJ von Y :

Co bo + 8 tH 0) CJ bl + 8H( 1)

(111 c, Co" ao(b, hoI Cl - C2 '" adbl - b2)

mit 80, a, 0

Da aIle c, nach Wahl von ao und a, mittels (11) aus X und 8

berechenbar sind, besteht die Parallel-Beziersegment-Kon­

struktion i. w. darin, die Parameter ao und a, so zu wahlen,

dsB Y eine moqlichst qute Approximation an Xa darstellt .

KUHN (?] und KLASS{61 ha ben in die8er Situation qefordert, daR

in den Randpunkten Co und Cl die KrUrnmunq von Y mit der

KrUmmunq von X6 tibereinstimmt. Dabei erqab sich ein quadrati­

sches Gleichunqssystem in a o und a,. Dieser Ansatz sttitzt

sich allerdinqs nur auf das Verhalten des Ausqanqssegmentes

in einer Umqebunq der Randpunkte .

Urn d as Verhallen des Ausgangssegmentes in der -Seqmentmitte­

starker zu berDcksichtiqen, fordern wir zur Bestimmung von ao

und a" daB die Tanqente an X im Punkt x( 1/2) parallel ist

zur Tanqente an Y im Punkt y( 1/2) und der orientierte Abstand

dieser Tangenten gleich 8 ist . Hit Hilfe des Parameter ­

wechsels • und der StDtzfunktionen 8,S· lassen sich diese

Bedingunqen durch

(12) 11(1/2) 1/2 x( 1/2)

( 1) (s - s·){1/2) z 8

beschreiben. y( 1/2)

•

Fig. 5.

33

34

Zur Herleitunq der a, aus ( 12) und (13) fUhren wir die

AbkUr-.:unqen

I bt - b o I ) 0 , ,I, I b] - bJ I ) 0 ,

u, ( i • 0, 1)

ein und betrachten die Winkel

•• • <):( ll' (0), x' (1/Z)) ., -"IX'(1/2),I1'(1))

(x' • dx / dt)

mit

o C ~O.~I ( n. 0 < ~o • '1', . ~ n

x(1/2)

F i q. 6 .

Die Auswertunq von (12) und (13) liefert nun ain lineares

Gleichunqssystem in (~o - Ao),(~, - All mit der erweiterte n

Koerri-.:ientenmatrix

Arnold

( 1 4)

[

S1n '+'0

S 1 n '1'0

-8 , n '1'1

si n ,+"

2o( cos '+'0

(8/3) 01-1

cos ,+,,) J + (1/2)(cos '+'0 t CQS ,+,d'

sin '+'1 ~ 0 eindeutiq Oieses System 1st aufqrund

losbar, und 8S gilt

von

( 15) Uo • ~o ol 4 + COS ,+"

0(4+C08"'0

s1 n '+'0

5 cos '+'0) II 3 sin '1'0)

5 cos 11',1/(3 sin .,)

Arnold

'. ,. u.

F i q . 7.

Um die Stabilitat des Verfahrens bei fortqeset~ter Untertei-

1un9 des Ausqanqsseqmentes X nach~uweisen , betrachten wir fur

einen Parameter t E Jo, 11 das von x( 0) nach x( t) verlauCende

Teilseqment X' von X. Hach dem Alqorithmus von DE CASTELJAU

(sie he [21. [3J) laBt sich X' vermoqe

" ,. x 0 4>' , 4>' [0 , 11 - [0, t I r ... rt

als kubis ches Be~ierseqment darste11en . Wendet man nun bei

fest em b ~ur Konstruktion eines Parallel-Be~ierseqmentes y'

vo n X' das Verfahren ( 15 ) an, so qilt nach (1) fur die so

entstehenden Funktionen ao',a,' ;

( 16) lima,' = 1 -bko) 0,

,--0 wobei ko die KrUmmunq von X (und damit aller Teilseqmente X')

im Anfanqspunkt bo be~eichne . Zur Oeutunq von (16) beachten

wir, daB n ach Konstruktion

(dy/dtO)(i) " a'(dx/dtHi) (i .. 0, 1 )

gilt . Die Verhaltnisse a.' konverqieren nach (3) qeqen das

Verhaltnis der Lanqen der Tanqentenvektoren in den Anfll.nqs­

punkten von X& und X.

35

36

Liter. tur

[ 1 I ARNOLD , R.

Qu,dr.tische und kubi,che orrset-Be2ierkurYen.

Di 5S . Dortmund 1986.

12 1 BOHK , W. IF ARIN,G./ UHMANN,J .

A s urve y of c urve and s urfac e lIIat h oda in CACO .

Compu ter Aided Geometric Desiqn 1 (198 4 ) 1-50 .

[3) BOHK , W./ KAHKANN,J .

Arnold

Crundl.q a n kurven- und flachenorientierter Hodell ier unq .

Info rm. tik-F.c hb eric hte 8d.65 ( 19 83' .

[ 4 ) HAUSDORFF , F .

Gru ndzU qa del" Ma nq e nl . hr e . Veit & Co . Leipzi q 1914 ,

151 HAUSDORFF , F .

He nqenlehre. de Gruyt.r . Berlin-L.ip'Ji9 1 935 .

( 61 KLASS, R.

An o ff se t spline approximation f or plane c ubi c s pl ines.

Co mputer Aid e d Oe8i9n Yo l . 1S no.s s8pt . 1983 pp 297-299 .

(7 J KUHN,8.

App roximation von lqu idiat, ntkurv.n durch k ubi sc he

Splines. Oiplom,rbait St uttqart 1983.

181 L.EICHTWEISS,K .

Ko n v exe Mengen . Sprinqer - Verlaq 1980 .

191 TI LLER , W. I HAN SON , E. G.

Offsets of two - dimensional pr o file s . IEEE Computer

Gra ph ics and Appli cations. Sept . 198 . , pp 36-.6.

1101 WALTER, R.

Oifferentialoeometrie . Bi bliooraphiachell I nlltitut 1978 .

e1ngegangen am 25 . 3.87