---

ShapeDetector.h

#ifndef SHAPEDETECTOR_H
#define SHAPEDETECTOR_H

#include "PolyLine.h"
#include "Ellipse.h"

#include <vector>
#include <algorithm>

class VShapeDetector
{
public:

        static bool ShouldSimplify (VPolyLine *pLine)
        {
                // (could put an algorithm here :)
                return true;
        }

        static void Simplify (VPolyLine *pLine)
        {
                if ( ShouldSimplify(pLine) ) // this isn't a natural curve
                {
                        vector<unsigned int> vSimplifiedPoints; // will store the indices of the simplified points
                        
                        SimplifySegment(pLine, &vSimplifiedPoints, 4, pLine->PointCount() - 1); // will recurse to simplify whole thing

                        sort(vSimplifiedPoints.begin(), vSimplifiedPoints.end()); // sort the indices



                        unsigned int nLinePos       = pLine->PointCount()      - 2;
                        unsigned int nSimplifiedPos = vSimplifiedPoints.size() - 1;

                        if (nSimplifiedPos < 2) // no points
                        {
                                unsigned int nLinePos = 5;
                                while (nLinePos < pLine->PointCount() -1) // delete all but last + first point
                                        pLine->DeletePoint(nLinePos);
                        }
                        else
                        {
                                for (; nLinePos >= 5; nLinePos--) // delete points that aren't needed in the simplified shape
                                {
                                        while ( vSimplifiedPoints[nSimplifiedPos] != nLinePos  && nLinePos >=5) // get rid of unsimplified points
                                                pLine->DeletePoint( nLinePos-- );
                                        
                                        nSimplifiedPos--;
                                }
                        }
                }
        }

        static void SimplifySegment(VPolyLine *pLine, vector<unsigned int> *pvPoints, unsigned int nStart, unsigned int nEnd)
        {
                const int MINDISTANCE = ScreenState::PointMultiplier() * 2;

                int nGreatestDistance=0, nGreatestDistanceIndex=0;
                int nCurrentDistance;
                
                if (nStart >= nEnd)
                        return;
                        

                for (unsigned int i=nStart + 1; i<nEnd; i++)
                {
                        nCurrentDistance = pLine->GetPoint(i).DistanceToLine( pLine->GetPoint(nStart), pLine->GetPoint(nEnd) );
                        if ( nCurrentDistance > nGreatestDistance)
                        {
                                nGreatestDistance      = nCurrentDistance;
                                nGreatestDistanceIndex = i;
                        }
                }
                

                if (nGreatestDistance >= MINDISTANCE)
                {
                        pvPoints->push_back(nGreatestDistanceIndex);

                        // start simplifying subsegments
                        SimplifySegment(pLine, pvPoints, nStart, nGreatestDistanceIndex);
                        SimplifySegment(pLine, pvPoints, nGreatestDistanceIndex, nEnd);
                }
        }


        static bool Parallelogram( VPolyLine* pLine )
        {
                int nHalfWidth = (pLine->GetPoint(3).x - pLine->GetPoint(0).x)/2;
                int nHalfHeight= (pLine->GetPoint(3).y - pLine->GetPoint(0).y)/2;

                VPoint center((pLine->GetPoint(0) + pLine->GetPoint(3))/ 2);

                int outcount = 0;


                int left = 0,right = 0,top = 0,bottom = 0;
                for ( unsigned int i=4; i < pLine->PointCount(); i++ )
                {
                        VPoint pt(pLine->GetPoint(i) - center);

                        // must be along one line--top, left, right, or bottom
                        if (pt.x < -.8 * nHalfWidth  && pt.x > -1.3 * nHalfWidth)
                        {
                                left++;
                        }
                        else if (pt.x >  .8 * nHalfWidth  && pt.x <  1.3 * nHalfWidth)
                        {
                                right++;
                        }
                        else if (pt.y < -.8 * nHalfHeight && pt.y > -1.3 * nHalfHeight)
                        {
                                top++;
                        }
                        else if (pt.y >  .8 * nHalfHeight && pt.y <  1.3 * nHalfHeight)
                        {
                                bottom++;
                        }
                        else
                        {
                                outcount++;
                        }

                }

                if (outcount < .2 * (pLine->PointCount() - 4) && // 20% of the points on lines
                        left  >= .15 * (pLine->PointCount() - 4) &&
                        right >= .15 * (pLine->PointCount() - 4) &&
                        bottom>= .15 * (pLine->PointCount() - 4) &&
                        top   >= .15 * (pLine->PointCount() - 4))
                        return true;
                else
                        return false;

        }

        static bool Ellipse( VPolyLine* pLine )
        {
                int nWidth = pLine->GetPoint(3).x - pLine->GetPoint(0).x;
                int nHeight = pLine->GetPoint(3).y - pLine->GetPoint(0).y;

                VPoint center((pLine->GetPoint(0) + pLine->GetPoint(3))/ 2);

                float outcount = 0;

                // find how far away points are from an ellipse of the same width + height of the polyline 
                for ( unsigned int i=4; i < pLine->PointCount(); i++ )
                {
                        VPoint pt(pLine->GetPoint(i) - center);

                        float value = (float) (pt.x * pt.x) / (nWidth * nWidth) + (float) (pt.y * pt.y) / (nHeight * nHeight);

                        outcount += (float) fabs( 1 - value*4 );
                }

                outcount /= (float) (pLine->PointCount()-4);

                if (outcount < .18)
                        return true;
                else
                        return false;
        }
};

#endif

---