Graphics Reference
In-Depth Information
point on the edge of the initial bounding box, or a single unique point farthest away
from an edge. There might be several points on a given bounding box edge, or several
points equally far away from an edge. In both cases, one of the two points that lie
closest to the edge endpoints must be chosen as the extreme point. Any points that
lie between these two points are generally not considered vertices of the convex hull,
as they would lie on an edge, collinear with the edge's end vertices.
Given an edge specified by two points
A
and
B
, the point of a point set
P
farthest
from the edge can be found by projecting the points onto a perpendicular to the edge.
The point projecting farthest along the perpendicular is the sought point. To break ties
between two points equally far along the perpendicular, the one projecting farthest
along
AB
is selected as the farthest point. This procedure is illustrated through the
following code:
// Return index i of point p[i] farthest from the edge ab, to the left of the edge
int PointFarthestFromEdge(Point2D a, Point2D b, Point2D p[], int n)
{
// Create edge vector and vector (counterclockwise) perpendicular to it
Vector2De=b-a,eperp = Vector2D(-e.y, e.x);
// Track index, 'distance' and 'rightmostness' of currently best point
int bestIndex = -1;
float maxVal = -FLT_MAX, rightMostVal = -FLT_MAX;
// Test all points to find the one farthest from edge ab on the left side
for(inti=1;i<n;i++) {
float d = Dot2D(p[i] - a, eperp);
// d is proportional to distance along eperp
float r = Dot2D(p[i] - a, e);
// r is proportional to distance along e
if (d > maxVal || (d == maxVal && r > rightMostVal)) {
bestIndex = i;
maxVal = d;
rightMostVal = r;
}
}
return bestIndex;
}
The Quickhull algorithm can also be made to work in three dimensions (and
higher) [Barber96]. In 3D, the initial approximation starts from the (up to) six extreme
points that lie on the axis-aligned box that bounds the point set. Now, instead of
finding points that are farthest from the edges of a polygon, points farthest from the
faces of a polyhedron are located. Instead of breaking the polygon edges up as a
new point is inserted into the hull, the polyhedron faces are broken up into two or
more faces.
