Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members File Members Related Pages

# ApproxPoly.h

Go to the documentation of this file.

    00001
    00034 #ifndef __APROX_POLY_H__
    00035 #define __APROX_POLY_H__
    00036
    00037 #include <math.h>
    00038 #include "SmartArray.h"
    00039
    00040 struct POINT {
    00041         double x, y;
    00042         POINT() {x = -1; y = -1; }
    00043         POINT(const double& xx, const double& yy)    { x = xx; y = yy; }
    00044         void Set(const double& xx, const double& yy) { x = xx; y = yy; }
    00045
    00046         friend ostream& operator<<(ostream& os, const POINT& p)
    00047         {
    00048                 //os << "(x:" << p.x << ", y:" << p.y << ")";
    00049                 os << p.x << ", " << p.y;
    00050         }
    00051
    00052         POINT& operator=(const POINT& rhs)
    00053         {
    00054                 x = rhs.x;
    00055                 y = rhs.y;
    00056
    00057                 return *this;
    00058         }
    00059
    00060         bool operator==(const POINT& rhs) const { return x == rhs.x && y == rhs.y; }
    00061         bool operator!=(const POINT& rhs) const { return !operator==(rhs); }
    00062
    00063         double L2() const { return sqrt(x * x + y * y); }
    00064         double L2(const POINT& p1) const
    00065         {
    00066                 double dx = x - p1.x;
    00067         double dy = y - p1.y;
    00068         return sqrt(dx * dx + dy * dy);
    00069         }
    00070
    00071         double Dot(const POINT& b) const { return x * b.x + y * b.y; }
    00072 };
    00073
    00074 typedef SmartArray<POINT> POINTS;
    00075
    00076 struct SEGMENT
    00077 {
    00078     double m, b;
    00079     POINT p0, p1;
    00080
    00081     SEGMENT() { m = 0; b = 0; }
    00082     void Set(const double& slope, const double& y_intercept,
    00083         const POINT& startPt, const POINT& endPt)
    00084     {
    00085         m = slope;
    00086         b = y_intercept;
    00087         p0 = startPt;
    00088         p1 = endPt;
    00089     }
    00090
    00091     double GetLen() const { return p0.L2(p1); }
    00092     double Y(const double& x) const { return m * x + b; }
    00093     double Y0() const { return Y(p0.x); }
    00094     double Y1() const { return Y(p1.x); }
    00095
    00096     istream& Read(istream& is)
    00097     {
    00098         is.read((char*)this, sizeof(*this));
    00099     }
    00100
    00101         ostream& Write(ostream& os) const
    00102         {
    00103                 os.write((char*)this, sizeof(*this));
    00104         }
    00105
    00106         ostream& Print(ostream& os) const
    00107     {
    00108         return os << "[" << p0 << "," << p1 << "] "
    00109                 << m << " x + " << b;
    00110     }
    00111
    00112         friend ostream& operator<<(ostream& os, const SEGMENT& s)       { return s.Print(os); }
    00113         //friend istream& operator>>(istream& is, SEGMENT& s)                   { return s.Read(is); }
    00114 };
    00115
    00116 typedef SmartArray<SEGMENT> SEGMENTS;
    00117
    00118 class MEMDATA
    00119 {
    00120         int ptIdx;
    00121         double dMinError;
    00122         bool bEmpty;
    00123
    00124 public:
    00125         MEMDATA() { bEmpty = true; ptIdx = -1; dMinError = 0; }
    00126         bool IsEmpty() const { return bEmpty; }
    00127         int GetIdx() const { return ptIdx; }
    00128         double GetMinError() const { return dMinError; }
    00129
    00130         void Set(const double& e, int i)
    00131         {
    00132                 bEmpty = false;
    00133                 ptIdx = i;
    00134                 dMinError = e;
    00135         }
    00136         double operator+(const MEMDATA& rhs) const
    00137         {
    00138                 ASSERT(!bEmpty && !rhs.bEmpty);
    00139
    00140                 return dMinError + rhs.dMinError;
    00141         }
    00142
    00143         friend ostream& operator<<(ostream& os, const MEMDATA& d)
    00144         {
    00145                 os << "(" << d.dMinError << ", " << d.ptIdx << ")";
    00146         }
    00147 };
    00148
    00149 typedef SmartArray< SmartMatrix<MEMDATA> > MEMORY;
    00150
    00151 struct SLOPE
    00152 {
    00153         double m;
    00154
    00155         bool bRelSmall;
    00156
    00157         friend ostream& operator<<(ostream& os, const SLOPE& s)
    00158         {
    00159                 os << "(" << s.m << ", " << s.bRelSmall << ")";
    00160         }
    00161 };
    00162
    00163 typedef SmartArray<SLOPE> SlopesArray;
    00164
    00165 class ApproxPoly
    00166 {
    00167 public:
    00168         struct KNOT
    00169         {
    00170                 int nIndex;
    00171                 SEGMENT seg;
    00172                 double dError;
    00173                 int dir;
    00174
    00175                 KNOT() { nIndex = 0; }
    00176                 KNOT(int idx, double slope) { Set(idx, slope); }
    00177                 KNOT(int idx, const SEGMENT& s, const double& err) { Set(idx, s, err); }
    00178                 void Set(int idx, const SEGMENT& s, const double& err) { nIndex = idx; seg = s; dError = err; }
    00179                 void Set(int idx, double slope) { nIndex = idx; seg.m = slope; }
    00180
    00181                 friend ostream& operator<<(ostream& os, const KNOT& p)
    00182                 {
    00183                         os << "Knot at " << p.nIndex << ", line segment " << p.seg
    00184                                 << ", fit error: " << p.dError;
    00185                 }
    00186         };
    00187
    00188         double m_dMinError, m_dMinSlope, m_dMaxSegments;
    00189         bool m_bDbgMode;
    00190         double m_ymin, m_ymax;
    00191
    00192         SmartArray<KNOT> m_knots;
    00193         POINTS m_points;
    00194         SmartMatrix<SEGMENT> m_segments;
    00195         MEMORY m_minerrors;
    00196
    00197 public:
    00198
    00199         ApproxPoly(double dMinError, double dMinSlope, double dMaxSegments);
    00200         double LeastSquares(const POINT* vertices, int n, double& a, double& b) const;
    00201         double LeastSquares(const POINT* vertices, int fromIdx, int toIdx, double& m, double& b) const;
    00202
    00203         bool IsRelativeSmall(double x0, double xn, double m, double b);
    00204         void Test();
    00205
    00206         MEMDATA Min(int seg_num, int s, int e);
    00207         int AddKnots(int seg_num, int s, int e);
    00208         void PlotKnots(int seg_num);
    00209         void SetDbgMode(bool bOn) { m_bDbgMode = bOn; }
    00210         void SetYMinMax();
    00211         double CompAcuteAngle(int seg1, int seg2) const;
    00212         double CompObtuseAngle(int seg1, int seg2) const;
    00213
    00214         void Fit(const POINTS vertices);
    00215 };
    00216
    00217 typedef SmartMatrix< SmartMatrix<MEMDATA> > MEMORY2;
    00218
    00219 struct MINMAX
    00220 {
    00221         int min, max;
    00222         MINMAX(int mi, int ma) { min = mi; max = ma; }
    00223 };
    00224
    00225 class ModelFit
    00226 {
    00227         MEMORY2 m_minerrors;
    00228         SEGMENTS m_segments;
    00229         POINTS m_points;
    00230         SmartArray<double> m_minLineLen;
    00231         SmartArray<double> m_minDataLen;
    00232         double m_minLenCoeff, m_totalMinLineLen, m_totalMaxLineLen, m_totalDataLen;
    00233
    00234 public:
    00235         ModelFit(double minLenCoeff) { m_minLenCoeff = minLenCoeff; }
    00236
    00237         double Fit(const POINTS& vertices, const SEGMENTS& segs);
    00238         MEMDATA Min(int ls, int le, int ps, int pe);
    00239         void UpdateSegments(int ls, int le, int ps, int pe);
    00240         double CompLSError(int ls, int ps, int pe) const;
    00241         MINMAX GetMinMaxLen(int ls, int li, int le, int ps, int pe) const;
    00242         void GetSegmentError(int s, double* error, double* scaleFactor) const;
    00243         void Plot(ostream& os, const POINTS& points2, const SEGMENTS& segments2) const;
    00244 };
    00245
    00246 #endif //__APROX_POLY_H__