On-Line Geometric Modeling Notes

Affine Combinations, Barycentric Coordinates and Convex Combinations


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.

Affine Combinations of Points

 

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 tex2html_wrap_inline257 and tex2html_wrap_inline259 be points in an affine space. Consider the expression
displaymath38
This equation is meaningful, as tex2html_wrap_inline261 is a vector, and thus so is tex2html_wrap_inline263. Therefore tex2html_wrap_inline265 is the sum of a point and a vector which is again a point (see the notes on Points and Vectors. This point tex2html_wrap_inline267 represents, in the affine space of two-dimensional points and vectors, a point on the line that passes through tex2html_wrap_inline269 and tex2html_wrap_inline271.

tex2html_wrap325

We note that if tex2html_wrap_inline273 then tex2html_wrap_inline275 is somewhere on the line segment joining tex2html_wrap_inline277 and tex2html_wrap_inline279.

This expression allows us to define a basic operation on points. We utilize the following notation
displaymath43
to mean that tex2html_wrap_inline281 is the point defined by
displaymath45
We can then define an affine combination of two points tex2html_wrap_inline283 and tex2html_wrap_inline285 to be
displaymath48
where tex2html_wrap_inline287. The form tex2html_wrap_inline289 is shown to be an affine transformation by setting tex2html_wrap_inline291.


We can generalize this to define an affine combination of an arbitrary number of points. If tex2html_wrap_inline293 are points and tex2html_wrap_inline295 are scalars such that tex2html_wrap_inline297, then
displaymath50
is defined to be the point
displaymath52


To construct an excellent example of an affine combination consider three points tex2html_wrap_inline299, tex2html_wrap_inline301 and tex2html_wrap_inline303. A point tex2html_wrap_inline305 defined by
displaymath54
where tex2html_wrap_inline307, gives a point in the triangle tex2html_wrap_inline309. We note that the definition of affine combination defines this point to be
displaymath56
The following illustration shows the point tex2html_wrap_inline311 generated when tex2html_wrap_inline313 and tex2html_wrap_inline315.

tex2html_wrap327

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

Barycentric Coordinates

  Given a frame tex2html_wrap_inline329 for an affine space tex2html_wrap_inline331, we can write any point tex2html_wrap_inline333 uniquely as
displaymath67
If we define points tex2html_wrap_inline335 by
equation69
and define tex2html_wrap_inline337 to be
displaymath73
then we can see that tex2html_wrap_inline339 can be equivalently written as
displaymath75
where tex2html_wrap_inline341

In this form, the values tex2html_wrap_inline343 are called the barycentric coordinates of tex2html_wrap_inline345 relative to the points tex2html_wrap_inline347

Vectors can also be expressed in barycentric form by letting
displaymath78
Then we have
displaymath80
where now we have that tex2html_wrap_inline349.


To give a simple example of barycentric coordinates, consider two points tex2html_wrap_inline351 and tex2html_wrap_inline353 in the plane. If tex2html_wrap_inline355 and tex2html_wrap_inline357 are scalars such that tex2html_wrap_inline359, then the point tex2html_wrap_inline361 defined by
displaymath82
is a point on the line that passes through tex2html_wrap_inline363 and tex2html_wrap_inline365. If tex2html_wrap_inline367 then the point tex2html_wrap_inline369 is on the line segment joining tex2html_wrap_inline371 and tex2html_wrap_inline373. The following figure shows an example of a line and three points tex2html_wrap_inline375, tex2html_wrap_inline377 and tex2html_wrap_inline379. These points were generated using the following tex2html_wrap_inline381s:

tex2html_wrap465


To give a slightly more complex example of barycentric coordinates, consider three points tex2html_wrap_inline401, tex2html_wrap_inline403, tex2html_wrap_inline405 in the plane. If tex2html_wrap_inline407, tex2html_wrap_inline409, tex2html_wrap_inline411 are scalars such that tex2html_wrap_inline413, then the point tex2html_wrap_inline415 defined by
displaymath99
is a point on the plane of the triangle formed by tex2html_wrap_inline417, tex2html_wrap_inline419, tex2html_wrap_inline421. The point is within the triangle tex2html_wrap_inline423 if tex2html_wrap_inline425. If any of the tex2html_wrap_inline427's is less than zero or greater than one, the point tex2html_wrap_inline429 is outside the triangle. If any of the tex2html_wrap_inline431's is zero, we reduce to the example above and note that tex2html_wrap_inline433 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 tex2html_wrap_inline435, tex2html_wrap_inline437 and tex2html_wrap_inline439, these points were calculated using the following tex2html_wrap_inline441's:

tex2html_wrap467


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.

Convex Combinations

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

If each tex2html_wrap_inline475 is such that tex2html_wrap_inline477, then the points tex2html_wrap_inline479 is called a convex combination of the points tex2html_wrap_inline481.


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

tex2html_wrap515

However, the point tex2html_wrap_inline499 is a convex combination, as tex2html_wrap_inline501, and any point on the line segment joining tex2html_wrap_inline503 and tex2html_wrap_inline505 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).

tex2html_wrap517

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 tex2html_wrap_inline507 that can be written as convex combinations of tex2html_wrap_inline509 is called the convex hull of the points tex2html_wrap_inline511. This convex hull is the smallest convex set that contains the set of points tex2html_wrap_inline513. The following figure illustrates the convex hull of a set of six points:

tex2html_wrap519

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.


Acknowledgement

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


References

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

Comments to the Author

All contents copyright (c) 1996, 1997
Computer Science Department,
University of California, Davis
All rights reserved.



Ken Joy
Thu Jul 24 10:13:59 PDT 1997