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 finding 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 difficult 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 fixed 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 simplifies 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 satisfied 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 coefficients of the solution may be obtained by
C = MP,
Computational geometry 127
with distinct coefficients 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 coefficients
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 defined in
[1] as
Get Applied Calculus of Variations for Engineers, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
