1 // convex_hull.cxx -- 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)
31 #ifdef NEEDNAMESPACESTD
35 #include "convex_hull.hxx"
36 #include "point2d.hxx"
38 // calculate the convex hull of a set of points, return as a list of
40 list_container convex_hull( list_container input_list )
42 list_iterator current, last;
43 map_iterator map_current, map_last;
45 // list of translated points
46 list_container trans_list;
48 // points sorted by radian degrees
49 map_container radians_map;
51 // will contain the convex hull
52 list_container con_hull;
58 // STEP ONE: Find an average midpoint of the input set of points
59 current = input_list.begin();
60 last = input_list.end();
61 in_count = input_list.size();
64 while ( current != last ) {
65 sum_x += (*current).x;
66 sum_y += (*current).y;
71 average.x = sum_x / in_count;
72 average.y = sum_y / in_count;
74 printf("Average center point is %.4f %.4f\n", average.x, average.y);
76 // STEP TWO: Translate input points so average is at origin
77 current = input_list.begin();
78 last = input_list.end();
79 trans_list.erase( trans_list.begin(), trans_list.end() );
81 while ( current != last ) {
82 p.x = (*current).x - average.x;
83 p.y = (*current).y - average.y;
84 printf("p is %.6f %.6f\n", p.x, p.y);
85 trans_list.push_back(p);
89 // STEP THREE: convert to radians and sort by theta
90 current = trans_list.begin();
91 last = trans_list.end();
92 radians_map.erase( radians_map.begin(), radians_map.end() );
94 while ( current != last ) {
95 p = cart_to_polar_2d(*current);
96 radians_map[p.theta] = p.dist;
100 printf("Sorted list\n");
101 map_current = radians_map.begin();
102 map_last = radians_map.end();
103 while ( map_current != map_last ) {
104 p.x = (*map_current).first;
105 p.y = (*map_current).second;
107 printf("p is %.6f %.6f\n", p.x, p.y);
117 // Revision 1.1 1998/09/04 23:04:51 curt
118 // Beginning of convex hull genereration routine.