TABLE OF CONTENTS There are many kinds of relationships between geometric objects. For example, given a group of objects, we might ask which member of the group is nearest or which is farthest from a given point? Or, with respect to an observer, which objects are partially or completely obscured by which other objects? Which is the smallest or largest object in a group? Which objects fit inside which other objects? And so on.
These and other relational properties are important in geometric modeling, and these must frequently be resolved in computer graphics applications such as 3D modeling, animation, and CAD/CAM. Underlying these relational properties are two additional relational phenomena of a more fundamental nature. They are the minimum-distance problem and the intersection. We will explore the minimum distance problem in this section and the intersection problem in the next.
Applications, or course, demand numerical solutions. We will see that the minimum-distance problem relies on a variety of numerical techniques and offers subtleties and idiosyncrasies sufficient to enthrall the most ardent numerical analyst. Gre3at volumes have been written describing techniques for finding roots of nth degree polynomials and solving systems of nonlinear equations. We do not discuss these methods here. Our focus is, instead, on the geometric content of each minimum-distance problem.
The computation of the minimum distance between two points is at once trivial and subtly complex. Consider the four distance problems posed in Figure 12.27. First, the distance between two arbitrary...
