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
*P*_{0}*P*_{1}*P*_{2}
where
*P*_{0}=(*x*_{0},*y*_{0}),
*P*_{1}=(*x*_{1},*y*_{1}) and
*P*_{2}=(*x*_{2},*y*_{2}) is

If the area is positive then the points occur in anti-clockwise order and

If the area is negative then they are in clockwise order. If the convex
hull is kept in anti-clockwise order and
*P*_{0}*P*_{1} is a hull edge this means that
*P*_{2} can see *P*_{0}*P*_{1} (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

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
*P*_{0}*P*_{1}*P*_{2}*P*_{3}where
*P*_{0}=(*x*_{0},*y*_{0},*z*_{0}),
*P*_{1}=(*x*_{1},*y*_{1},*z*_{1}),
*P*_{2}=(*x*_{2},*y*_{2},*z*_{2}) and
*P*_{3}=(*x*_{3},*y*_{3},*z*_{3}) is

If this volume is positive then the triangle *P*_{0}*P*_{1}*P*_{2} is
anti-clockwise when viewed from the side away from *P*_{3}. Another way
to say this is that the normal to *P*_{0}*P*_{1}*P*_{2} determined by the
right-hand rule (curl you fingers from *P*_{0} to *P*_{1} *P*_{2}, your
thumb shows the direction of the normal) points out from the
tetrahedron.

If the volume is negative then the normal to *P*_{0}*P*_{1}*P*_{2} points into
the tetrahedron. By convention, we store polyhedra with outward
normals. This means that if *P*_{0}*P*_{1}*P*_{2} is any triangle of the convex
hull and *P*_{3} is any other vertex, we want the volume of
*P*_{0}*P*_{1}*P*_{2}*P*_{3} 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 *P*_{3} can see
*P*_{0}*P*_{1}*P*_{2}, 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