**On-Line Geometric Modeling Notes**

These notes discuss affine combinations of points, barycentric coordinates of points and vectors, convex combinations, convex sets, and the convex hull of a set of points.

For a postscript version of these notes look here.

Points in an affine space are utilized to position ourselves within the space. The operations on the vectors of an affine space are numerous - addition, scalar multiplication, dot products, cross products - but the operations on the points are limited. In this section we discuss the basic operations on points - affine combinations.

Let and be points in an affine space. Consider the
expression

This equation is meaningful, as is a vector, and thus
so is . Therefore is the sum of a
point and a vector which is again a point (see the notes on
Points and
Vectors.
This point represents, in the affine space of two-dimensional
points and vectors, a point on the line that passes through
and .

We note that if then is somewhere on the line segment joining and .

This expression allows us to define a basic operation on points. We
utilize the following notation

to mean that is the point defined by

We can then define an **affine combination** of two points
and to be

where . The form is shown to be an affine transformation by setting .

We can generalize this to define an affine combination of an arbitrary
number of points. If are points and
are scalars such that
, then

is defined to be the point

To construct
an excellent example of an affine combination consider three
points , and . A point defined by

where , gives a point in the
triangle . We note that the definition of
affine combination defines this point to be

The following illustration shows the point generated when
and .

In fact, it can be easily shown that if then the point will be within (or on the boundary) of the triangle. If any is less than zero or greater than one, then the point will lie outside the triangle. If any is zero, then the point will lie on the boundary of the triangle.

Given a frame
for an affine space
, we can write any point uniquely as

If we define points by

and define to be

then we can see that can be equivalently written as

where

In this form, the values are called the
*barycentric coordinates* of relative to the points

Vectors can also be expressed in barycentric form by letting

Then we have

where now we have that
.

To give a simple example of barycentric coordinates, consider two
points and in the plane. If and
are scalars such that , then the point
defined by

is a point on the line that passes through and . If
then the point is on the line
segment joining and . The following figure shows an
example of a line and three points , and . These
points were generated using the following s:

- : ,
- : ,
- : ,

To give a slightly more complex
example of barycentric coordinates, consider three points
, , in the plane. If , ,
are scalars such that , then
the point defined by

is a point on the plane of the triangle formed by , ,
. The point is within the triangle if
. If any of the 's
is less than zero or greater than one, the point is outside the
triangle. If any of the 's is zero, we reduce to the example
above and note that is on one of the lines joining the vertices of
the triangle. The following figure shows an example of such a triangle and
three points , and , these points were calculated
using the following 's:

- : , .
- : , , .
- : , , .

Thus barycentric coordinates are another method of introducing coordinates into an affine space. If the coordinates sum to one, they represent a point ; if the coordinates sum to zero, they represent a vector.

Given a set of points , we can form affine
combinations of these points by selecting , with and form
the point

If each is such that , then the
points is called a __convex combination__ of the points
.

To give a simple example of this, consider two points and . Any point on the line passing through these two points can be written as which is an affine combination of the two points. The points and in the following figure are affine combinations of and .

However, the point is a convex combination, as , and any point on the line segment joining and can be written in this way.

Given any set of points, we say that the set is a __convex set__,
if given any two points of the set, any convex combination of these
two points is also in the set. The following figure illustrates both
a convex set (on the left) and a non-convex set (on the right).

This concept is actually quite intuitive, in that if one can draw a
straight line between two points of the set *that is not
completely contained within the set*, the the set is non-convex.

The set of all points that can be written as convex combinations
of is called the __convex hull__ of
the points . This convex hull is the
smallest convex set that contains the set of points . The following figure illustrates the convex hull of a
set of six points:

One of the six points does not contribute to the boundary of the convex hull. If one looked closely at the coordinates of the point, one would find that this point could be written as a convex combination of the other five.

Most of this material was adapted from Tony DeRose's wonderful treatment of affine spaces given in [1].

**1**- Tony DeRose. Coordinate-free geometric programming. Technical Report 89-09-16, Department of Computer Science and Engineering, University of Washington, Seattle, Washington, 1988.

This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |

Thu Jul 24 10:13:59 PDT 1997