Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/geometry/two_d/convex_hull.h
Go to the documentation of this file.
00001 #ifndef H_GEOMETRY_TWO_D_CONVEX_HULL
00002 #define H_GEOMETRY_TWO_D_CONVEX_HULL
00003 
00008 #include "point.h"
00009 #include <vector>
00010 #include <algorithm>
00011 #include "utils/preconditions/preconditions.h"
00012 #include <cassert>
00013 
00014 namespace geometry {
00015 namespace two_d {
00016 
00020 template <typename T>
00021 class ConvexHull {
00022  public:
00023   typedef Point<T> PointType;
00024 
00028   void clear() {
00029     data.clear();
00030   }
00031 
00035   void addPoint(const PointType point) {
00036     data.push_back(point);
00037   }
00038 
00044   std::vector<PointType> convexHull() {
00045     if (data.size() < 2) {
00046       // one point is always in the convex hull
00047       return data;
00048     }
00049 
00050     std::sort(data.begin(), data.end(), PointCompare());
00051     std::vector<PointType> lower_chain = computeChain(data);
00052 
00053     std::reverse(data.begin(), data.end());
00054     std::vector<PointType> upper_chain =
00055       rotate180(computeChain(rotate180(data)));
00056 
00057     assert(upper_chain.size() > 0);
00058     if (upper_chain.size() == 1) {
00059       assert(lower_chain.size() == 1);
00060       return lower_chain;
00061     }
00062     lower_chain.insert(lower_chain.end(), upper_chain.begin() + 1, upper_chain.end() - 1);
00063     return lower_chain;
00064   }
00065 
00066  private:
00067 
00079   std::vector<PointType> computeChain(const std::vector<PointType> data) {
00080     Preconditions::check(data.size() > 1);
00081     std::vector<PointType> chain;
00082     chain.push_back(data[0]);
00083     typedef typename std::vector<PointType>::size_type SizeType;
00084     SizeType pos = 1;
00085     while ((pos < data.size()) && 
00086            (data[0] == data[pos])) {
00087       pos++;
00088     }
00089     if (pos == data.size()) {
00090       return chain; // only 1 unique point and we were strict
00091     }
00092     chain.push_back(data[pos]);
00093     for (SizeType i = pos + 1; i < data.size(); i++) {
00094       PointType current = data[i];
00095       while (chain.size() >= 2) {
00096         PointType last1 = chain[chain.size() - 1];
00097         PointType last2 = chain[chain.size() - 2];
00098 
00099         if ((current - last1).cross(last1 - last2) > 0) {
00100           break;
00101         }
00102         chain.pop_back();
00103       }
00104       chain.push_back(current);
00105     }
00106 
00107     return chain;
00108   }
00109 
00113   std::vector<PointType> rotate180(const std::vector<PointType> data) {
00114     std::vector<PointType> result;
00115     typedef typename std::vector<PointType>::size_type SizeType;
00116     for (SizeType i = 0; i < data.size(); i++) {
00117       PointType current = data[i];
00118       result.push_back(PointType(-current.x(), -current.y()));
00119     }
00120     return result;
00121   }
00122 
00128   class PointCompare {
00129    public:
00130     bool operator()(const PointType& p1, const PointType& p2) {
00131       if (p1.x() != p2.x()) {
00132         return p1.x() < p2.x();
00133       }
00134       return (p1.y() < p2.y());
00135     }
00136   };
00137 
00141   std::vector<PointType> data;
00142 };
00143 
00144 } // namespace two_d
00145 } // namespace geometry
00146 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines