1 // convex_hull.hxx -- calculate the convex hull of a set of points
3 // Written by Curtis Olson, started September 1998.
5 // Copyright (C) 1998 Curtis L. Olson - curt@me.umn.edu
7 // This program is free software; you can redistribute it and/or modify
8 // it under the terms of the GNU General Public License as published by
9 // the Free Software Foundation; either version 2 of the License, or
10 // (at your option) any later version.
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License
18 // along with this program; if not, write to the Free Software
19 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 // (Log is kept at end of this file)
26 #ifndef _CONVEX_HULL_HXX
27 #define _CONVEX_HULL_HXX
32 #ifdef NEEDNAMESPACESTD
36 #include "point2d.hxx"
40 typedef list < point2d > list_container;
41 typedef list_container::iterator list_iterator;
44 // calculate the convex hull of a set of points, return as a list of
45 // point2d. The algorithm description can be found at:
46 // http://riot.ieor.berkeley.edu/riot/Applications/ConvexHull/CHDetails.html
47 list_container convex_hull( list_container input_list );
50 #endif // _CONVEX_HULL_HXX
54 // Revision 1.2 1998/09/09 16:26:33 curt
55 // Continued progress in implementing the convex hull algorithm.
57 // Revision 1.1 1998/09/04 23:04:51 curt
58 // Beginning of convex hull genereration routine.