9

Computational geometry

The geodesic concept, introduced in the last chapter purely on variational

principles, has interesting engineering aspects. On the other hand, the an-

alytic solution of a geodesic curve by ﬁnding the extremum of a variational

problem may not be easy in practical cases.

It is reasonable to assume, however, that the quality of a curve in a geodesic

sense is related to its curvature. This observation proposes a strategy for cre-

ating good quality (albeit not necessarily geodesic) curves by minimizing the

curvature.

Since the curvature is diﬃcult to compute, one can use the second derivative

of the curve in lieu of the curvature. This results in the following variational

problem statement for a smooth curve: Find the curve s(t)thatresultsin

I(s)=

t

n

t

0

k(s

)

2

dt = extremum.

The constant k represents the fact that this is an approximation of the

curvature, but will be left out from our work below. This variational problem

leads to the well-known spline functions.

9.1 Natural splines

Let us consider the following variational problem. Find the curve between

two points P

0

,P

3

such that

I(s)=

t

3

t

0

(

d

2

s

dt

2

)

2

dt = extremum,

with boundary conditions of

P

0

= s(t

0

),P

3

= s(t

3

),

125

126 Applied calculus of variations for engineers

and additional discrete internal constraints of

P

1

= s(t

1

),P

2

= s(t

2

).

In essence, we are constraining two interior points of the curve, along with

the ﬁxed beginning and endpoints. We will, for the sake of simplicity, assume

unit equidistant parameter values as

t

i

= i, i =0....,3.

While the functional does not contain the independent variable t and the de-

pendent variable s(t), it is of higher order. Hence the Euler-Poisson equation

of second order applies:

∂f

∂y

−

d

dx

∂f

∂y

+

d

2

dx

2

∂f

∂y

=0,

and in this case it simpliﬁes to

d

4

dt

4

s(t)=0.

Straightforward integration yields the solution of the form

s(t)=c

0

+ c

1

t + c

2

t

2

+ c

3

t

3

,

where c

i

are constants of integration to be satisﬁed by the boundary condi-

tions. Imposing the boundary conditions and constraints yields the system of

equations

⎡

⎢

⎢

⎣

100 0

111 1

124 8

13927

⎤

⎥

⎥

⎦

⎡

⎢

⎢

⎣

c

0

c

1

c

2

c

3

⎤

⎥

⎥

⎦

=

⎡

⎢

⎢

⎣

P

0

P

1

P

2

P

3

⎤

⎥

⎥

⎦

.

The inversion of the system matrix results in the generating matrix

M =

⎡

⎢

⎢

⎣

1 000

−11/63−3/21/3

1 −5/22−1/2

−1/61/2 −1/21/6

⎤

⎥

⎥

⎦

for the natural spline. For any given set of four points

P =

⎡

⎢

⎢

⎣

x

0

y

0

z

0

x

1

y

1

z

1

x

2

y

2

z

2

x

3

y

3

z

3

⎤

⎥

⎥

⎦

the coeﬃcients of the solution may be obtained by

C = MP,

Computational geometry 127

with distinct coeﬃcients for all coordinate directions as

C =

⎡

⎢

⎢

⎣

c

x

0

c

y

0

c

z

0

c

x

1

c

y

1

c

z

1

c

x

2

c

y

2

c

z

2

c

x

3

c

y

3

c

z

3

⎤

⎥

⎥

⎦

.

For example, the points

P =

⎡

⎢

⎢

⎣

11

22

32

43

⎤

⎥

⎥

⎦

result in coeﬃcients

C =

⎡

⎢

⎢

⎣

11

113/6

0 −3/2

01/3

⎤

⎥

⎥

⎦

.

The parametric solution curve is of the form

x(t)=1+t,

y(t)=1+13/6t − 3/2t

2

+1/3t

3

.

The example solution curve is shown in Figure 9.1, where the input points

are connected by the straight lines that represent the chords of the spline.

The spline demonstrates a good smoothness while satisfying the constraints.

Several extensions of this problem are noteworthy. It is possible to pose the

variational problem in two-parameter form as

I(s)=

D

((

∂

∂u

s(u, v))

2

+(

∂

∂v

s(u, v))

2

)dudv = extremum.

The Euler-Lagrange equation corresponding to this problem arrives at Laplace’s

equation:

∂

2

∂u

2

s(u, v)+

∂

2

∂v

2

s(u, v)=0.

This is sometimes called the harmonic equation, hence the splines so obtained

are also called harmonic splines.

It is also often the case in practice that many more than four points are

given:

P

i

=(x

i

,y

i

,z

i

),i=0,...,n.

128 Applied calculus of variations for engineers

1

1.5

2

2

.5

3

1 1.5 2 2.5 3 3.5

4

FIGURE 9.1 Natural spline approximation

This enables the generation of a multitude of natural spline segments, and a

curvature continuity condition between the segments may also be enforced.

Finally, the direct (for example Ritz) solution of the above variational problem

leads to the widely used B-splines, a topic of the next chapter.

9.2 B-spline approximation

As shown in Chapter 7, when using numerical methods an approximate solu-

tion is sought in terms of suitable basis functions:

s(t)=

n

i=0

B

i,k

(t)Q

i

,

where Q

i

are the yet unknown control points (i=0,. . . ,n) and B

i,k

are the basis

functions of degree k in the parameter t. For industrial computational work,

the class of basis functions resulting in the so-called B-splines are deﬁned in

[1] as

Get *Applied Calculus of Variations for Engineers, 2nd Edition* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.