Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable

The use of coordinates to describe and analyze geometrical configurations has undoubtedly been one of the most pervasive and productive developments in the entire history of mathematics, science, and engineering. This seminal idea — from which the field of

analytic geometry

arose — was first systematically expounded by René Descartes in his 1637 treatise

La Géométrie

. The immense appeal of analytic geometry derives from its intuitive visual aspect; from its remarkable success in applying algebra and analysis to geometrical problems; and from the ubiquity of such problems in science and technology.

Figure 2.1 shows cuneiform tablet no. 322 in the Plimpton Collection of the Rare Book and Manuscript Library at Columbia University. This compilation of sexagesimal (base 60) numbers

1

is believed to originate from the ancient Mesopotamian city Larsa (Tell Senkereh in modern Iraq) and has been dated to the period 1820–1762 BC. It was discovered in the 1920s and acquired in a market by the antiquities dealer Edgar A. Banks, who then sold it for $10 to George A. Plimpton, a New York publisher and a collector of mathematical artifacts.

Complex numbers are indispensable tools for modern science and technology, and the emergence of fields such as quantum mechanics, signal processing, and control theory is inconceivable without a complete theory of complex variables.

The methods of three—dimensional vector analysis —

dot

and

cross

products, and the differential operators such as the

gradient, divergence

, and

curl

— are fundamental to modern science. It is not commonly appreciated, however, that these methods are actually a rather late development in mathematics: they devolved from a more—sophisticated theory, the algebra of the

quaternions

. We present here a brief introduction to quaternions and their use in describing an important set of geometrical transformations — namely, rotations in ℝ

3

. As we shall see in Chap. 22, this property of quaternions proves invaluable in the formulation of a sufficient—and—necessary characterization for Pythagorean hodographs in ℝ

3

, that is invariant under arbitrary spatial rotations.

Clifford algebra (also known as

geometric algebra

) is named after the English mathematician William Kingdon Clifford (1845–1879), who made significant contributions to algebra and geometry1 in a brilliant but tragically brief career (he died of tuberculosis, possibly exacerbated by his rigorous work schedule). Clifford algebra provides a systematic framework for generalizing the known algebras of complex numbers and quaternions to any number of dimensions. For a more comprehensive discussion of its methods and diverse applications in science and engineering, see [30, 133, 134, 238, 310].

Coordinates may be regarded as a powerful and versatile means whereby the tools of algebra and analysis can be brought to bear upon various geometrical problems — constructions, transformations, analysis of shape and incidence relationships, etc. They are obviously crucial to the computer implementation of geometrical algorithms and the visualization of their results.

It is commonly believed that the invention of calculus was motivated by the desire to formulate and solve differential equations, especially the equations of motion of Newtonian dynamics. In fact, purely geometrical problems, such as the determination of tangents and curvatures, feature prominently among its earliest applications. The first calculus textbook, the

Analyse des infiniment petits, pour l'intelligence des lignes courbes

(see Fig. 8.1), published in 1696 by the French aristocrat Guillaume Francois Antoine de l'Hôpital (1661–1704), is an exposition on the elementary differential geometry of plane curves.

1

Algebraic geometry

is the study of point sets satisfying polynomial equations in the Cartesian coordinates of two, three, or more dimensions. For example, a plane algebraic curve is just the set of points with two—dimensional Cartesian coordinates (

x, y

) on which some polynomial

f

vanishes:

f

(

x

,

y

) = 0. Similarly, an algebraic surface is the set of three—dimensional points (

x

,

y

,

z

) on which a polynomial

g

vanishes:

g

(

x

,

y

,

z

) = 0. These are examples of

implicit

curve and surface equations. They allow us to easily test whether a point lies on the curve or surface, but are not so convenient for generating points on it.

Computing the distance between points on a plane is a trivial matter once we erect a Cartesian coordinate system on it—we simply use equation (7.1). Seen from a three—dimensional vantage point, the plane may have any position or orientation we like. If we choose to remain “in” the plane, we can regard it as a

two—dimensional space

in its own right: the possibility of erecting Cartesian coordinates upon it, and using equation (7.1) to measure distances between its points, characterizes it as a “flat” or

Euclidean

space.

The geometrical algorithms of computer-aided design systems usually employ

floating-point arithmetic

— a finite approximation to real-number arithmetic that sacrifices exactitude for computational efficiency and predictable memory requirements. In general, floating-point arithmetic incurs errors whenever real numbers must be stored in the computer memory, or arithmetic operations are performed on numbers already in memory. These errors are typically of small relative magnitude, but under certain circumstances they can be dramatically magnified, yielding numerical results that are essentially meaningless.

In the design of curves and surfaces subject to prescribed constraints, such as interpolation of a given set of points, the adopted representation must provide sufficient degrees of freedom to permit satisfaction of those constraints. If a

single

polynomial or rational form is employed, the only scope for introducing additional freedoms is to increase the degree. Unfortunately, interpolants of high degree often exhibit undesired oscillations that are incompatible with the “shape” of the given data, and can be difficult to suppress or control.

Constructing a spline curve that interpolates an ordered sequence of points is a relatively simple matter, involving only the solution of tridiagonal linear systems. Constructing a spline

surface

that interpolates an

array

of points is a much more challenging problem — such a surface comprises a network of “patches,” and we must guarantee second—order continuity along the common boundary curves of every pair of adjacent patches. Attempting to formulate and solve systems of equations that express these continuity constraints is an exceedingly cumbersome and unrewarding task. However, we shall see below that the expression of spline functions in terms of

spline bases

offers an elegant and easily—implemented solution to this problem.

The study of planar PH curves brings us to an unexpected acquaintance with Count Ehrenfried Walther von Tschirnhaus

1

(Fig. 18.1) — a less-prominent contemporary of Huygens, Leibniz, and Newton. Born on April 10, 1651 in Kieslingswalde (now Sławnikowice in Poland), he was schooled privately and at Görlitz Gymnasium before entering the University of Leiden in 1668, where he studied philosophy, mathematics, and medicine. After completing his studies in Leiden, he travelled to England carrying a letter of recommendation from the philosopher Baruch Spinoza to Henry Oldenburg, Secretary of the newly-formed Royal Society of London for the Improvement of Natural Knowledge (and also editor of its

Philosophical Transactions

).

The recognition that complex numbers admit a geometrical interpretation, as points in the Euclidean plane, was a critical step in securing their widespread acceptance (see §4.1). The “geometric algebra” of points in ℝ

2

defined by the arithmetic rules for complex numbers allows us to

multiply

and

divide

points, as well as adding or subtracting them in the usual vector sense. However, the systematic use of complex numbers as a means of exploring analytic geometry in ℝ

2

has received less attention than it deserves —

The Advanced Geometry of Plane Curves and Their Applications

1

by C. Zwikker [480] seems to be the only treatise that consistently employs this approach.

A

helix

— or “curve of constant slope” — is characterized by the property that its tangent maintains a constant inclination relative to a fixed direction — the

axis

of the helix. Equivalently, a helix exhibits a circular

tangent indicatrix

, and the ratio of curvature and torsion remains constant along its length [290, 307, 433]. Whereas all spatial PH cubics are helical (see §21.1), the helical PH quintics constitute a proper subset of the spatial PH quintics.

The

Minkowski Pythagorean hodograph curves

— or MPH curves for brevity — were first introduced by H. P. Moon [328–330]. Their distinctive feature is that the hodographs satisfy a Pythagorean condition under the metric of the Minkowski space ℝ

2,1

with two “space-like” and one “time-like” coordinates, rather than the Euclidean metric of ℝ

3

with three space-like coordinates. The motivation for the definition of MPH curves is that they allow the

medial axis transform

of a planar domain to be specified in such a way that the domain boundary is exactly describable by rational curves. The medial axis transform (MAT) represents a planar domain as the union of a one-parameter family of variable-radius disks, and the problem of constructing the domain boundary from the MAT is a generalization of the problem of constructing offset curves, which correspond to envelopes of families of fixed-radius disks. Rationality of the domain boundary is ensured by requiring the components of a polynomial MAT to satisfy a Pythagorean condition under the metric of ℝ

2,1

.

Planar PH quintics offer sufficient shape flexibility for most practical design and manufacturing applications — they can inflect, and are in many respects similar in behavior to “ordinary” plane cubics (see §19.7). To construct planar PH quintics, a scheme that provides control over basic geometrical properties of a curve segment is required. Selecting numerical values for the coefficients

u

0

,

u

1

,

u

2

and

v

0

,

v

1

,

v

2

in (17.6) by “guesswork” clearly does not satisfy this need: we must develop algorithms that

determine

appropriate values for these coefficients, consistent with the specified geometrical constraints. Because the control points (17.6) have a non—linear dependence on

u

0

,

u

1

,

u

2

and

v

0

,

v

1

,

v

2

such algorithms incur non—linear equations with a multiplicity of solutions.

In Chap. 14 we reviewed the classical (linear) theory of “ordinary”

C

2

cubic splines. Having discussed how individual PH curve segments are constructed, we are now ready to address the more challenging problem of constructing

C

2

PH quintic spline curves. Our focus at present is on

planar

PH splines, and we use the complex representation (Chap. 19) to facilitate their computation.

As with planar PH curves (see Chap. 25), first—order Hermite interpolation is a convenient approach to constructing spatial PH curves in a geometrically meaningful manner. The quaternion formulation introduced in Chap. 22 is useful in reducing the problem to a simple system of quadratic equations, but the nature of the solution space differs qualitatively from the planar case — instead of just a finite multiplicity of solutions, the spatial PH quintic Hermite interpolation problem admits a

two—parameter family

of solutions.

To describe a general spatial motion of a rigid object, we must specify both its

position

and its

orientation

at each instant in time. The positional component amounts to specifying a space curve, parameterized by time, to be executed by some chosen point — e.g., the center of mass. In many applications, however, the orientational component is not precisely specified or constrained

a priori

. Instead, an algorithm must be formulated to determine a “natural” variation of orientation along the specified path, by aligning the body's principal axes with an orthonormal frame defined at each point along the path.

Since their inception [186] in 1990, a substantial volume of literature on Pythagorean—hodograph curves has accumulated — the bibliography includes over 80 papers concerned with elucidating the basic theory of PH curves, their extensions and generalizations, algorithms for their construction and analysis, and their applications in computer—aided design and manufacturing, robotics, motion control, graphics and animation, and related fields. Nevertheless, many problems merit further study, and research on PH curves remains very active. A forthcoming special issue of

Computer Aided Geometric Design

is devoted to the theme “Pythagorean—hodograph curves and related topics.”