Maer.C

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 | Library QgarLib, graphics analysis and recognition                  |
 | Copyright (C) 2002  Qgar Project, LORIA                             |
 |                                                                     |
 | This library is free software; you can redistribute it and/or       |
 | modify it under the terms of the GNU Lesser General Public          |
 | License version 2.1, as published by the Free Software Foundation.  |
 |                                                                     |
 | This library is distributed in the hope that it will be useful,     |
 | but WITHOUT ANY WARRANTY; without even the implied warranty of      |
 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                |
 | See the GNU Lesser General Public License for more details.         |
 |                                                                     |
 | The GNU Lesser General Public License is included in the file       |
 | LICENSE.LGPL, in the root directory of the Qgar packaging. See      |
 | http://www.gnu.org/licenses/lgpl.html for the terms of the licence. |
 | To receive a paper copy, write to the Free Software Foundation,     |
 | Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.       |
 |                                                                     |
 | Contact Project Qgar for any information:                           |
 |   LORIA - équipe Qgar                                               |
 |   B.P. 239, 54506 Vandoeuvre-lès-Nancy Cedex, France                |
 |   email: qgar-contact@loria.fr                                      |
 |   http://www.qgar.org/                                              |
 *---------------------------------------------------------------------*/


/**
 * @file   Maer.C
 * @brief  Implementation of class qgar::Maer.
 *
 * See file Maer.H for the interface.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   May 13, 2004  11:30
 * @since  Qgar 2.1
 */



// STD
#include <cmath>
#include <limits>
#include <list>
// QGAR
#include <qgarlib/FreemanChain.H>
#include <qgarlib/GenConvexHull.H>
#include <qgarlib/Maer.H>
#include <qgarlib/math.H>
#include <qgarlib/primitives.H>



namespace qgar
{

// -------------------------------------------------------------------
// -------------------------------------------------------------------
// C O N S T R U C T O R S
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// CREATE FROM A LIST OF POINTS HAVING double COORDINATES

Maer::Maer(const std::list<DPoint>& aPtList)
{
  PRIVATEcomputeMaer(aPtList);
}

// CREATE FROM A LIST OF POINTS HAVING COORDINATES TYPE
// DIFFERENT FROM double

template <class T>
Maer::Maer(const std::list< GenPoint<T> >& aPtList)
{
  std::list<DPoint> dList;

  transform(aPtList.begin(),
            aPtList.end(),
            PRIVATEtoDPoint(),
            back_inserter(dList));

  PRIVATEcomputeMaer(dList);
}

// CREATE FROM A FREEMAN CHAIN

Maer::Maer(const FreemanChain& aCh)
{
  PRIVATEcomputeMaer(aCh.toDPointList());
}

// COPY CONSTRUCTOR

Maer::Maer(const Maer& aMaer)

  : _vertices(aMaer._vertices),
    _area(aMaer._area)

{
  // VOID
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// D E S T R U C T O R
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// NON-VIRTUAL DESTRUCTOR

Maer::~Maer()
{
  // VOID
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// A C C E S S   T O   C O R N E R S
// -------------------------------------------------------------------
// -------------------------------------------------------------------

// GET THE LIST INCLUDING THE 4 CORNERS OF THE MAER

const std::list<DPoint>&
Maer::accessVertices() const
{
  return _vertices;
}
  
// GET A COPY OF THE LIST INCLUDING THE 4 CORNERS OF THE MAER

std::list<DPoint>
Maer::vertices() const
{
  return _vertices;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// O P E R A T O R S
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// ASSIGNMENT

Maer&
Maer::operator=(const Maer& aMaer)
{
  // Are left hand side and right hand side different objects?
  if (this != &aMaer)
    {
      _vertices = aMaer._vertices;
      _area     = aMaer._area;
    }

  return *this;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// C O N S T R U C T I O N   O F   T H E   M A E R   (PRIVATE)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


void
Maer::PRIVATEcomputeMaer(const std::list<DPoint>& aPtList)
{
  // THE CONVEX HULL OF THE GIVEN POINTS
  // ===================================

  DConvexHull hull(aPtList);

  // THE COMPONENT IS A SINGLE POINT: DEGENERATED MAER
  // =================================================

  if (hull.size() == 1)
    {
      // 4 same corners and null area
      _vertices.push_back(hull.accessPivot());
      _vertices.push_back(hull.accessPivot());
      _vertices.push_back(hull.accessPivot());
      _vertices.push_back(hull.accessPivot());
      _area = 0.;

      return;
    }

  // COMPUTE THE DIFFERENT RECTANGLES AND SELECT THE MINIMAL ONE
  // ===========================================================

  // List of the vertices of the hull
  const std::list<DPoint>& vList = hull.accessVertices();

  // 2 consecutive points of the hull
  std::list<DPoint>::const_iterator itPrev = vList.begin();
  std::list<DPoint>::const_iterator itCurr = itPrev;
  itCurr++;

  // Current minimum area
  _area = std::numeric_limits<double>::max();

  // Consider each consecutive pair of hull vertices
  // and compute the corresponding rectangle
  // WARNING: The last pair includes the last and first vertices

  do
    // DO WHILE BLOCK  WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
    {

      // Coordinates of previous point
      double xPrev = itPrev->x();
      double yPrev = itPrev->y();

      // Direction of the vector joining previous and current points 
      double theta = atan2(itCurr->y() - yPrev, itCurr->x() - xPrev);
      if (theta < 0.)
        {
           theta += Math::QG_2PI;
        }

      // Initializations
      double minX = std::numeric_limits<double>::max();
      double maxX = std::numeric_limits<double>::min();
      double minY = std::numeric_limits<double>::max();
      double maxY = std::numeric_limits<double>::min();
      
      // Minimum and maximum X and Y
      for (std::list<DPoint>::const_iterator itV  = vList.begin() ;
           itV != vList.end() ;
           itV++)
        { 
          // Translation
          double xTmp = itV->x() - xPrev;
          double yTmp = itV->y() - yPrev;
          
          // Rotation
          double x = (  xTmp * cos(theta) ) + ( yTmp * sin(theta) );
          double y = ( -xTmp * sin(theta) ) + ( yTmp * cos(theta) );
          
          // Update coordinates min's and max's
          if (x < minX)
            {
              minX = x;
            }
          if (x > maxX)
            {
              maxX = x;
            }
          if (y < minY)
            {
              minY = y;
            }
          if (y > maxY)
            {
              maxY = y;
            }
        }
      
      // The four corners of the corresponding rectangle
       double xTopL = minX * cos(theta) - minY * sin(theta) + xPrev;
       double yTopL = minX * sin(theta) + minY * cos(theta) + yPrev;
      
       double xTopR = minX * cos(theta) - maxY * sin(theta) + xPrev;
       double yTopR = minX * sin(theta) + maxY * cos(theta) + yPrev;
      
       double xBotR = maxX * cos(theta) - maxY * sin(theta) + xPrev;
       double yBotR = maxX * sin(theta) + maxY * cos(theta) + yPrev;
      
       double xBotL = maxX * cos(theta) - minY * sin(theta) + xPrev;
       double yBotL = maxX * sin(theta) + minY * cos(theta) + yPrev;

       double currArea =   hypot(xTopL - xTopR, yTopL - yTopR)
                         * hypot(xTopR - xBotR, yTopR - yBotR);
             
      // Update minimum area
      if (currArea < _area)
        {
          // Current rectangle is the minimum one up to now
          _area = currArea;

          // Save new maer
          _vertices.clear();
          _vertices.push_back(DPoint(xTopL, yTopL));
          _vertices.push_back(DPoint(xTopR, yTopR));
          _vertices.push_back(DPoint(xBotR, yBotR));
          _vertices.push_back(DPoint(xBotL, yBotL));
        }

      // Next vertices pair
      // WARNING: The last pair includes the last and first vertices
      itPrev = itCurr;
      itCurr++;
      if (itCurr == vList.end())
        {
          itCurr = vList.begin();
        }

    }
    // END OF DO WHILE BLOCK  WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

  while (itPrev != vList.begin());

}

// -------------------------------------------------------------------

} // namespace qgar