Graphics Reference
In-Depth Information
current last edge of the chain, the point is tentatively assumed part of the hull and is
added to the chain. However, if the next point lies to the left of the current last edge
of the chain, this point clearly lies outside the hull and the hull chain must be in error.
The last point added to the chain is therefore removed, and the test is applied again.
The removal of points from the chain is repeated until the next point lies to the right
of the last edge of the chain, after which the next point is appended to the hull chain.
The next point in the example is point
C
.
C
lies to the left of edge
AB
, and thus
the tentative hull must be in error and
B
is removed from the chain. Because there
are no more points to delete (
A
must lie on the hull, being the leftmost point),
C
is
added to the chain, making the hull chain
A
C
. Next is point
D
, which lies to the
right of edge
AC
, and is therefore added to the chain. The next point is
E
, which lies
to the right of
CD
, and thus
E
is also added to the chain, as is the next point,
F
. Point
G
lies to the left of edge
EF
, and thus again the tentative hull chain must be in error
and
F
is removed from the chain. Next,
G
is found to lie to the left of
DE
as well, and
thus
E
is also removed from the chain. Finally,
G
now lies to the right of the last edge
on the chain,
CD
, and
G
is added to the chain, which at this point is
A
−
G
.
Proceeding to the remaining points, the final upper chain ends up as shown in the
middle right-hand illustration. An analogous process is applied to form the lower
hull chain. Remaining then is to handle the case of multiple points sharing the same
x
coordinate. The straightforward solution is to consider only the topmost point for
addition to the upper chain, and only the bottommost point for addition to the lower
chain.
It is easy to write an in-situ version of Andrew's algorithm. Thus, it can with benefit
be used on point sets represented as arrays.
−
C
−
D
−
3.9.2
The Quickhull Algorithm
Although Andrew's algorithm works very well in 2D, it is not immediately clear how
to extend it to work in 3D. An alternative method that works in both 2D and 3D is
the
Quickhull algorithm
. The basic idea of the Quickhull algorithm is very simple, and
is illustrated in Figure 3.23 for the 2D case.
In a first step, the bounding box of the point set is obtained, and in the general case
the four extreme points of the set (lying on each of the four sides of the bounding
box) are located. Because these points are extreme, they must lie on the convex hull,
and thus form a quadrilateral“first approximation”of the convex hull (Figure 3.23, top
left). As such, any points lying inside this quadrilateral clearly cannot lie on the convex
hull of the point set and can be removed from further consideration (Figure 3.23, top
right). Some of the points lying outside the quadrilateral must, however, lie on the
hull, and thus the approximation is now refined. For each edge of the quadrilateral,
the point outside the edge farthest away from the edge (if any) is located. Because
each such point is extreme in the direction perpendicularly away from the edge, it
must lie on the hull. Therefore, these points are inserted into the hull, between the two
points of the edge they were outside of (Figure 3.23, bottom left). Together with the
