GenAirports/convex_hull.cxx

   1 // convex_hull.cxx -- calculate the convex hull of a set of points
   2 //
   3 // Written by Curtis Olson, started September 1998.
   4 //
   5 // Copyright (C) 1998  Curtis L. Olson  - curt@me.umn.edu
   6 //
   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.
  11 //
  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.
  16 //
  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.
  20 //
  21 // $Id$
  22 // (Log is kept at end of this file)
  23 //
  24
  25
  26 #include <stdio.h>
  27
  28 #include <list>
  29 #include <map>
  30
  31 #ifdef NEEDNAMESPACESTD
  32 using namespace std;
  33 #endif
  34
  35 #include "convex_hull.hxx"
  36 #include "point2d.hxx"
  37
  38 // calculate the convex hull of a set of points, return as a list of
  39 // point2d
  40 list_container convex_hull( list_container input_list )
  41 {
  42     list_iterator current, last;
  43     map_iterator map_current, map_last;
  44
  45     // list of translated points
  46     list_container trans_list;
  47
  48     // points sorted by radian degrees
  49     map_container radians_map;
  50
  51     // will contain the convex hull
  52     list_container con_hull;
  53
  54     point2d p, average;
  55     double sum_x, sum_y;
  56     int in_count;
  57
  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();
  62     sum_x = sum_y = 0.0;
  63
  64     while ( current != last ) {
  65         sum_x += (*current).x;
  66         sum_y += (*current).y;
  67
  68         current++;
  69     }
  70
  71     average.x = sum_x / in_count;
  72     average.y = sum_y / in_count;
  73
  74     printf("Average center point is %.4f %.4f\n", average.x, average.y);
  75
  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() );
  80
  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);
  86         current++;
  87     }
  88
  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() );
  93
  94     while ( current != last ) {
  95         p = cart_to_polar_2d(*current);
  96         radians_map[p.theta] = p.dist;
  97         current++;
  98     }
  99
 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;
 106
 107         printf("p is %.6f %.6f\n", p.x, p.y);
 108
 109         map_current++;
 110     }
 111
 112     return con_hull;
 113 }
 114
 115
 116 // $Log$
 117 // Revision 1.1  1998/09/04 23:04:51  curt
 118 // Beginning of convex hull genereration routine.
 119 //
 120 //