A Direct Convex Hull Algorithm

John Henckel
Rural Route 1
Zumbro Falls, MN 55991
Tel. 507-253-1203

henckel@iname.com, http://www.formulus.com

(C) 1998, John Henckel
ABSTRACT

The convex hull problem is to find the smallest convex polyhedron that contains a given finite set of points. This paper describes a practical convex hull algorithm for 3-dimensional points. The algorithm uses a gift-wrapping approach and it is easy to implement. An implementation in C++ is used in the Tru-Physics simulation program for Microsoft Windows.

Introduction

The convex hull of a set of points is the smallest convex polyhedron that contains the points. We describe the convex hull as a list of faces and edges. Each face has a list of perimeter points in clockwise order. Each edge has two points.

The two approaches to the convex hull problem are incremental and gift-wrapping. The incremental approach, such as QuickHull [Barber et al. 96], starts with a convex hull (for example, 4 non-coplanar points) and repeatedly adds a point to the convex hull of the previously processed points. The gift-wrapping approach, such as the Preparata and Hong algorithm [Edelsbrunner 87], starts with a single face and repeatedly adds a face to the edge of a previous face. The algorithm described here is a variation of the gift-wrapping approach, though much simpler than the Preparata and Hong algorithm.

Informal Algorithm Description

We first find two points such that the line segment connecting them is an edge on the convex hull. This edge is the seed of the iterative part of the algorithm and we put the edge in the to-do list. At each iteration, we take a known edge, (A, B), from the to-do list and find a face adjacent to this edge. To find a face, we begin by choosing any non-collinear point, C. If other points are above the plane ABC, choose a new point, C', to be the point farthest above ABC and repeat using the new point, C'. If all other points are below or on the plane ABC, we build a new face with point A, B, C, any other coplanar points. Also we compute the edges of the face and add them to the to-do list. When the to-do list is empty, we are done.

Definitions

Vector or Point
refer to a data structure containing three floating point numbers, x, y, and z.
Data Points
the set of points that are the input to the algorithm.
Plane
is a 2D flat surface described by a point on the plane, and the normal direction vector which is perpendicular to the plane.
Face Plane
a plane containing one of the convex hull faces. No data points are above a face plane (in the direction of the normal vector).
Edge
is a line segment connecting two data points at the intersection of two face planes.

Algorithm

  1. Get input, N = number of points
  2. If N < 3, return error
  3. Initialize: FaceList = empty, EdgeList = empty, ToDoList = empty.
  4. Find two points, A and B, that form an edge (see details below).
  5. Choose any point C, not collinear with A and B.
  6. Compute cross product NM = (A - B) x (C - B).
    M = the plane at B with normal NM.
  7. For every data point (except A, B, C) compute signed distance to plane
    dist(P, M) = (P - B) * NM
    and find the point, P, with maximum distance
  8. If dist(P, M) > 0, then C = P and go to 6.
    Else we know M is a face plane.
  9. Create a face, F, with all data points on the plane M. (This will include A, B, C and possibly others).
  10. Sort F points according to angle(P) = (P - B) * (A - B)
  11. Add F to FaceList.
  12. For each edge, E = (P1, P2), clockwise on the perimeter of F do {
     ER = (P2, P1).
     If ER is in the EdgeList list {
        If E is in the ToDoList, remove E from the ToDoList.
     }
     Else {
        Add E to the EdgeList
        Add ER to the ToDoList
     }
    }
  13. If the ToDoList is empty, return the EdgeList and FaceList.
  14. Else get (A, B) the next edge in the ToDoList and go to 5.

Finding the initial edge

 Find the initial edge to seed the interative part of the algorithm as follows.
  1. Choose a random unit vector, D.
  2. Find the extreme point, A, in direction D. Simply find the maximum of the dot product A*D.
  3. If more than three points have the maximum distance, go to 1.
  4. M = the plane perpendicular to D through point A.
    Choose the point, B, with the smallest angle at A to the plane M.
    The sine of the angle is computed, sineOfAngle(B) = ( (B - A) / ||B - A|| ) * D.
  5. If more than one point has the minimum angle value, choose the point, B, nearest to A.
  6. E = (A, B) is an edge of the convex hull.

Bibliography