Creating the Hull
The actual creation of the hull is done by method build_hull, which calls method build_half_hull twice, once with the points on the lower hull, and once with the points on the upper hull. The output of build_half_hull is sent on the first call to array lower_hull and next to array upper_hull:
void build_hull( std::ofstream &f )
{
build_half_hull( f, lower_partition_points, lower_hull, 1 );
build_half_hull( f, upper_partition_points, upper_hull, -1 );
}
So the bulk of the work is actually done in build_half_hull, which looks like this:
void build_half_hull( std::ostream &f,
std::vector<std::pair<int,int>> input,
std::vector<std::pair<int,int>> &output,
int factor )
{
// The hull will always start with the left point, and end with the right
// point. Initialize input and output accordingly
//
input.push_back( right );
output.push_back( left );
while ( input.size() != 0 ) {
//
// Repeatedly add the leftmost point to the null, then test to see
// if a convexity violation has occurred. If it has, fix things up
// by removing the next-to-last point in the output sequence until
// convexity is restored.
//
output.push_back( input.front() );
input.erase( input.begin() );
while ( output.size()>= 3 ) {
size_t end = output.size() - 1;
if ( factor * direction( output[ end - 2 ],
output[ end ],
output[ end - 1 ] ) <= 0 ) {
output.erase( output.begin() + end - 1 );
} else
break;
}
}
}
The main loop in this routine simply pulls points out of the input array, adds them to the output array, and then performs the check to make sure that convexity has not been violated. If it has, points are removed until it is again correct. Figure 5 gives a nice animated view of the process.
Once this is done, calling the log_hull routine produces output that looks like this:
Lower hull: (16,21)(27,10)(59,8)(94,42)(97,90)
Upper hull: (16,21)(18,90)(59,95)(81,95)(97,90)
Convex hull: (16,21) (27,10) (59,8) (94,42) (97,90) (81,95) (59,95)
(18,90) (16,21)
The plot_hull() method can then be called to create a gnuplot command file that will display the convex hull, as in Figure 6.
There are quite a few variations on the 2-D convex hull building process, and this program ought to be amenable to trying out many of them. If you use the existing data structures and just change the algorithms, you can use the existing gnuplot routines to animate your work and get a good feel for how it is working. Enjoy!
References and Links
[1]R.L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Info. Proc. Lett. 1, 132-133 (1972).
[2] A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inform. Process. Lett., 9(5):216-219, 1979. (A note about the this algorithm can be found here.)
