On-Line Computer Graphics Notes
Overview
Convex combinations are simply affine combinations where the constants in the combination are limited to be in the interval [0,1].
For a postscript version of these notes look here.
What is a Convex Combination?
Given a set of points 
, we can form an
affine combination
of these points by selecting constants 
, (where 
) and
write
If each 
is such that 
, then the
point 
is called a convex combination of the points
.
Example - Point on a Line Segment
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
or equivalently
where 
.
The points
and
in the
following figure are affine combinations of 
and 
.
The point 
is a convex combination since
. Any point on the line segment
joining 
and 
can be written as a convex combination.
Convex Set
Given any set of points, we say that the set is a convex set
if given any points 
in the set, any
convex combination of these
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).
Since any convex combination of points from a convext set must lie in the set, then certainly the straight line joining any two points of the set must also be completely in the set. 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 not convex.
Convex Hull
Given a set of points
.
The set of all points 
that can be written as convex combinations
of
.
is called the convex hull of the set.
It is easy to see that this
convex hull is necessarily a convex set - but, it turns out that it
is the
smallest convex set that contains
.
(If there were a
convex set C smaller than the convex hull that contained the points,
then we could find a point 
in the convex hull, but not in the
set C. But since each of the 
is in both sets, and the point 
is a convex combination of the 
s, it must also be in the convex
hull as well as in C.)
The following figure illustrates the convex hull of a
set of six points:
We note that one of the six points does not contribute to the boundary of the
convex hull. If one looked closely at the coordinates of 
,
one would find that this point could be written as a convex
combination of the other five.
Summary
Convex combinations are an extremely important concept in computer graphics and geometric modeling. The convex-hull concept will allow us to take a set of points, put a bounding box about the set of points, and since the bounding box is convex, we are insured that the convex-hull of the set of points is also contained in the bounding box. These bounding boxes are the method that we will use to ``keep track of'' our objects.
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
