Convex Hull Geometric Primitives

This applet shows the geometric test needed to compute the convex hull of a set of points.

In the Gift Wrap algorithm we need to determine if a point is to the left of the line through two other points. In the Incremental algorithm we need to determine if a point can see an edge.

Actually, both of these tests are the same and we can implement them by calculating the area of a triangle. The area of the triangle P0P1P2 where P0=(x0,y0), P1=(x1,y1) and P2=(x2,y2) is

\begin{displaymath}\frac12\left\vert\begin{array}{ccc} x_0&x_1&x_2\\ y_0&y_1&y_2\\ 1&1&1\\ \end{array}\right\vert\end{displaymath}

If the area is positive then the points occur in anti-clockwise order and P2 is to the left of the line P0P1 (the test required by the Gift Wrap algorithm). If the convex hull is kept in anti-clockwise order then this area will be positive for any three consecutive points on the hull.

If the area is negative then they are in clockwise order. If the convex hull is kept in anti-clockwise order and P0P1 is a hull edge this means that P2 can see P0P1 (the test required by the Incremental algorithm).

Finally, if the area is zero the three points are collinear.

You can move a point in the triangle below by dragging it with the mouse and see how the area changes. If the area is positive the triangle is coloured black, if it is negative then is colored red.

Note that since we only care whether the area is positive, negative or zero it is only necessary to calculate

\begin{displaymath}\left\vert\begin{array}{ccc} x_0&x_1&x_2\\ y_0&y_1&y_2\\ 1&1&1\\ \end{array}\right\vert\end{displaymath}

If the coordinates are integers this means that we only need to use integer calculations to compute the convex hull.

This approach generalises to higher dimensions. The volume of the tetrahedron P0P1P2P3where P0=(x0,y0,z0), P1=(x1,y1,z1), P2=(x2,y2,z2) and P3=(x3,y3,z3) is

\begin{displaymath}\frac16\left\vert\begin{array}{cccc} x_0&x_1&x_2&x_3\\ y_0&y... ..._2&y_3\\ z_0&z_1&z_2&z_3\\ 1&1&1&1\\ \end{array}\right\vert \end{displaymath}

If this volume is positive then the triangle P0P1P2 is anti-clockwise when viewed from the side away from P3. Another way to say this is that the normal to P0P1P2 determined by the right-hand rule (curl you fingers from P0 to P1 P2, your thumb shows the direction of the normal) points out from the tetrahedron.

If the volume is negative then the normal to P0P1P2 points into the tetrahedron. By convention, we store polyhedra with outward normals. This means that if P0P1P2 is any triangle of the convex hull and P3 is any other vertex, we want the volume of P0P1P2P3 to be positive. So, testing the sign of the volume is just the test needed for the 3D Gift Wrap algorithm.

The same volume test also allows us to determine if P3 can see P0P1P2, the test needed by the Incremental algorithm.

Similarly, in 4D we must compute a 5x5 determinant, and so on.

lambert@cse.unsw.edu.au
Last modified: Fri Nov 1 01:24:54 MET