---

ApproxPoly.h

Go to the documentation of this file.

#ifndef __APROX_POLY_H__
#define __APROX_POLY_H__

#include <math.h>
#include "SmartArray.h"

struct POINT {
        double x, y;
        POINT() {x = -1; y = -1; }
        POINT(const double& xx, const double& yy)    { x = xx; y = yy; }
        void Set(const double& xx, const double& yy) { x = xx; y = yy; }

        friend ostream& operator<<(ostream& os, const POINT& p)
        {
                //os << "(x:" << p.x << ", y:" << p.y << ")";
                os << p.x << ", " << p.y;
        }

        POINT& operator=(const POINT& rhs)
        {
                x = rhs.x;
                y = rhs.y;

                return *this;
        }
        
        bool operator==(const POINT& rhs) const { return x == rhs.x && y == rhs.y; }
        bool operator!=(const POINT& rhs) const { return !operator==(rhs); }
        
        double L2() const { return sqrt(x * x + y * y); }
        double L2(const POINT& p1) const
        {
                double dx = x - p1.x;
        double dy = y - p1.y;
        return sqrt(dx * dx + dy * dy);
        }
        
        double Dot(const POINT& b) const { return x * b.x + y * b.y; }
};

typedef SmartArray<POINT> POINTS;

struct SEGMENT
{
    double m, b;
    POINT p0, p1;
                
    SEGMENT() { m = 0; b = 0; }
    void Set(const double& slope, const double& y_intercept,
        const POINT& startPt, const POINT& endPt)
    {
        m = slope;
        b = y_intercept;
        p0 = startPt;
        p1 = endPt;
    }

    double GetLen() const { return p0.L2(p1); }
    double Y(const double& x) const { return m * x + b; }
    double Y0() const { return Y(p0.x); }
    double Y1() const { return Y(p1.x); }

    istream& Read(istream& is)
    {
        is.read((char*)this, sizeof(*this));
    }

        ostream& Write(ostream& os) const
        {
                os.write((char*)this, sizeof(*this));
        }
        
        ostream& Print(ostream& os) const
    {
        return os << "[" << p0 << "," << p1 << "] "
                << m << " x + " << b;
    }

        friend ostream& operator<<(ostream& os, const SEGMENT& s)       { return s.Print(os); }
        //friend istream& operator>>(istream& is, SEGMENT& s)                   { return s.Read(is); }
};

typedef SmartArray<SEGMENT> SEGMENTS;

class MEMDATA
{
        int ptIdx;
        double dMinError;
        bool bEmpty;
        
public: 
        MEMDATA() { bEmpty = true; ptIdx = -1; dMinError = 0; }
        bool IsEmpty() const { return bEmpty; }
        int GetIdx() const { return ptIdx; }
        double GetMinError() const { return dMinError; }
        
        void Set(const double& e, int i)
        {
                bEmpty = false;
                ptIdx = i;
                dMinError = e;
        }
        double operator+(const MEMDATA& rhs) const
        {
                ASSERT(!bEmpty && !rhs.bEmpty);
                
                return dMinError + rhs.dMinError;
        }
        
        friend ostream& operator<<(ostream& os, const MEMDATA& d)
        {
                os << "(" << d.dMinError << ", " << d.ptIdx << ")";
        }
};

typedef SmartArray< SmartMatrix<MEMDATA> > MEMORY;

struct SLOPE
{
        double m;

        bool bRelSmall;
        
        friend ostream& operator<<(ostream& os, const SLOPE& s)
        {
                os << "(" << s.m << ", " << s.bRelSmall << ")";
        }
};

typedef SmartArray<SLOPE> SlopesArray;

class ApproxPoly
{
public: 
        struct KNOT
        {
                int nIndex;
                SEGMENT seg;
                double dError;
                int dir;

                KNOT() { nIndex = 0; }
                KNOT(int idx, double slope) { Set(idx, slope); }
                KNOT(int idx, const SEGMENT& s, const double& err) { Set(idx, s, err); }
                void Set(int idx, const SEGMENT& s, const double& err) { nIndex = idx; seg = s; dError = err; }
                void Set(int idx, double slope) { nIndex = idx; seg.m = slope; }
                
                friend ostream& operator<<(ostream& os, const KNOT& p)
                {
                        os << "Knot at " << p.nIndex << ", line segment " << p.seg
                                << ", fit error: " << p.dError;
                }
        };

        double m_dMinError, m_dMinSlope, m_dMaxSegments;
        bool m_bDbgMode;
        double m_ymin, m_ymax;
        
        SmartArray<KNOT> m_knots;
        POINTS m_points;
        SmartMatrix<SEGMENT> m_segments;
        MEMORY m_minerrors;

public:

        ApproxPoly(double dMinError, double dMinSlope, double dMaxSegments);
        double LeastSquares(const POINT* vertices, int n, double& a, double& b) const;
        double LeastSquares(const POINT* vertices, int fromIdx, int toIdx, double& m, double& b) const;

        bool IsRelativeSmall(double x0, double xn, double m, double b); 
        void Test();
        
        MEMDATA Min(int seg_num, int s, int e);
        int AddKnots(int seg_num, int s, int e);
        void PlotKnots(int seg_num);
        void SetDbgMode(bool bOn) { m_bDbgMode = bOn; }
        void SetYMinMax();
        double CompAcuteAngle(int seg1, int seg2) const;
        double CompObtuseAngle(int seg1, int seg2) const;

        void Fit(const POINTS vertices);
};

typedef SmartMatrix< SmartMatrix<MEMDATA> > MEMORY2;

struct MINMAX
{
        int min, max;
        MINMAX(int mi, int ma) { min = mi; max = ma; }
};

class ModelFit
{
        MEMORY2 m_minerrors;
        SEGMENTS m_segments;
        POINTS m_points;
        SmartArray<double> m_minLineLen;
        SmartArray<double> m_minDataLen;
        double m_minLenCoeff, m_totalMinLineLen, m_totalMaxLineLen, m_totalDataLen;
        
public: 
        ModelFit(double minLenCoeff) { m_minLenCoeff = minLenCoeff; }
        
        double Fit(const POINTS& vertices, const SEGMENTS& segs);
        MEMDATA Min(int ls, int le, int ps, int pe);
        void UpdateSegments(int ls, int le, int ps, int pe);
        double CompLSError(int ls, int ps, int pe) const;
        MINMAX GetMinMaxLen(int ls, int li, int le, int ps, int pe) const;
        void GetSegmentError(int s, double* error, double* scaleFactor) const;
        void Plot(ostream& os, const POINTS& points2, const SEGMENTS& segments2) const;
};

#endif //__APROX_POLY_H__

---