Chapter 9
Computations for
Geometric Design
Finding intersection between curves, surfaces and solids are much used operations in computer aided
geometric design and other applications like robotics. Intersection determination is primarily used in
computing Boolean relations between two solids in constructive solid geometry. Herein, we are
interested in computing the portions common to the two objects (if any). In path planning in robotics,
collision detection requires computing the proximity between two objects (robot and obstacles)
wherein, it may be required to determine if the robot is colliding (in contact) with the obstacle or not.
In case not, then how far is the robot from the obstacle. Virtual assembly simulation is another
application domain. For instance, a mechanical assembly has to be checked for service accessibility
by a technician. Virtual simulation can verify accessibility by checking the movements of a virtual
technician to reach the appropriate parts of the engine without colliding with the other parts. Rendering
models (display) in computer graphics requires computation of ray collisions with the object to
determine the hidden faces, depth of field and shading. The collection of algorithms to compute
various relations like proximity, intersection, decomposition and relational search between geometric
entities (points, lines, planes, and solids) lies within the realm of computational geometry.
This chapter discusses the implementation of a few such algorithms notwithstanding their complexity
or robustness.
A Euclidean space Rd of dimension d, has a family of natural distance metrics, known as
theLp norms, which are defined so that the distance between two points x = (x 1 ,x 2 ,... , xd) and
y = (y 1 ,y 2 ,... , yd) is given as
d(x,y) = |x 1 – y 1 |p + |x 2 – y 2 |p +... + |xd –yd|p (9.1)The Euclidean distance between two points in a three dimensional space is given by the L^2 norm. To
compute the distance between any two geometric entities one algorithmically computes the distances
between respectively belonging points.
9.1 Proximity of a Point and a Line
Consider a point C (x 3 ,y 3 ) and a line ABwith end points (x 1 ,y 1 ) and (x 2 ,y 2 ). The area of triangle ABC
is computed by calculating the determinant Δ as