00001 #ifndef _VUCONVEXHULL_H_
00002 #define _VUCONVEXHULL_H_
00003
00004 #include "vuVector.h"
00005 #include "vuDVector.h"
00006
00007 class vuConvexHull
00008 {
00009 public:
00010 vuConvexHull() : m_CHCalculated(false) {};
00011
00012 void setPoints(int npoints, float* plist);
00013 void addPoint(float x, float y);
00014 void addPoint(int index, float x, float y);
00015 void clearPoints();
00016 int getNPoints() {return m_PList.getLength();};
00017
00018
00019 int angleThreshold(float angle_th);
00020
00021
00022 bool getCHull(vuDVector<int>& indices);
00023 bool getCHull(int & lenHull, int *indices);
00024
00025 private:
00026 class CHPoint
00027 {
00028 public:
00029 CHPoint() {};
00030 CHPoint(int _i, float _x, float _y) : x(_x), y(_y), index(_i) {};
00031 CHPoint(int _i, const vuVector& v) : x(v[0]) , y(v[1]), index(_i) {};
00032 CHPoint& operator= (const CHPoint & rhs) {
00033 x = rhs.x;
00034 y = rhs.y;
00035 index = rhs.index;
00036 return *this;
00037 }
00038 vuVector& toVector(vuVector& v) {
00039 v[0] = x;
00040 v[1] = y;
00041 v[2] = 0;
00042 v[3] = 1;
00043 return v;
00044 }
00045 float x,y;
00046 int index;
00047 };
00048
00049 void setPoints(const vuDVector<CHPoint>& plist);
00050 void addPoint(const CHPoint& p);
00051 void sortPList();
00052 void sweepLine();
00053 void mergeULHulls();
00054 void calcConvexHull();
00055 static float knickTest(const CHPoint & b, const CHPoint & q, const CHPoint & r);
00056
00057 vuDVector<CHPoint> m_PList;
00058 vuDVector<CHPoint> m_CHull;
00059 vuDVector<CHPoint> m_UHull, m_LHull;
00060 bool m_CHCalculated;
00061 };
00062
00063
00064 #endif