Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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