FreemanChain.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  FreemanChain.C
 * @brief Implementation of class qgar::FreemanChain.
 *
 * See file FreemanChain.H for the interface.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   December 19, 2003  17:30
 * @since  Qgar 2.1.1
 */



// STD
#include <cstdlib>
// STL
#include <list>
// QGAR
#include <qgarlib/FreemanChain.H>
#include <qgarlib/FreemanCode.H>
#include <qgarlib/image.H>
#include <qgarlib/primitives.H>



namespace qgar
{


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


// WARNING - WARNING - WARNING - WARNING - WARNING - WARNING - WARNING
//
// THE DEFAULT CONSTRUCTOR BELONGS TO THE PRIVATE SECTION
// SO THAT A CLIENT CANNOT USE IT

FreemanChain::FreemanChain()
{
  // VOID
}

//  : _chain(),
//    _first  (GenPoint<int>(0,0)),
//    _current(GenPoint<int>(0,0)),
//    _last   (GenPoint<int>(0,0))
//
//{
//  // Set iterator to begin of chain
//  _iter = _chain.begin();
//
//}

// WARNING - WARNING - WARNING - WARNING - WARNING - WARNING - WARNING


// COPY CONSTRUCTOR

FreemanChain::FreemanChain(const FreemanChain& aFreemanCh)

  : _chain  (aFreemanCh._chain),
    _first  (aFreemanCh._first),
    _current(aFreemanCh._current),
    _last   (aFreemanCh._last)

{
  // Set the iterator to the beginning of the chain
  _iter = _chain.begin();
}


// CONSTRUCT FROM A POINT

FreemanChain::FreemanChain(const GenPoint<int>& aPt)

  : _chain  (1, FreemanCode(QGE_DIRECTION_N, 0)),
    _first  (aPt),
    _current(aPt),
    _last   (aPt)

{
  // Set the iterator to the beginning of the chain
  _iter = _chain.begin();
}


// CONSTRUCT FROM A POINT, A DIRECTION AND A LENGTH

FreemanChain::FreemanChain(const GenPoint<int>& aPt,
                           QGEdirection aDir,
                           unsigned int aLength)

  : _chain(1, FreemanCode(QGE_DIRECTION_N, 0)),
    _first(aPt)

{
  // Set the iterator to the beginning of the chain
  _iter = _chain.begin();

  FreemanCode code(aDir, aLength);
  // Second point
  _chain.push_back(code);
  _current = code.toPoint(aPt);
  _last = _current;
  _iter++;
}


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


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


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


// IS CURRENT CHAIN EMPTY?

bool
FreemanChain::empty() const
{
  return _chain.empty();
}


// CHAIN LENGTH (NUMBER OF POINTS)

int
FreemanChain::size() const
{
  return _chain.size();
}


// -------------------------------------------------------------------
// I T E R A T O R 
// -------------------------------------------------------------------


// MAKE THE INTERNAL ITERATOR POINT TO THE FIRST POINT OF THE CHAIN,
// THAT BECOMES THE CURRENT POINT

void
FreemanChain::setToBegin()
{ 
  _iter = _chain.begin();
  _current = _first;
}


// MAKE THE INTERNAL ITERATOR POINT TO THE LAST POINT OF THE CHAIN,
// THAT BECOMES THE CURRENT POINT

void
FreemanChain::setToEnd()
{
  _iter = _chain.end();
  _iter--;
  _current = _last;
}


// DOES INTERNAL ITERATOR POINTS TO THE BEGINNING OF THE CHAIN?

bool
FreemanChain::isAtBegin() const
{
  return _iter == _chain.begin();
}


// DOES INTERNAL ITERATOR POINTS TO THE END OF THE CHAIN?

bool
FreemanChain::isAtEnd() const
{
  return _iter == _chain.end();
}


// IS THERE A POINT AFTER THE CURRENT POINT?

bool
FreemanChain::hasNext() const
{
  std::list<FreemanCode>::iterator itAux = _iter;
  return (++itAux != _chain.end());
}


// IS THERE A POINT BEFORE THE CURRENT POINT?

bool
FreemanChain::hasPrevious() const
{
  return (_iter != _chain.begin());
}


// MOVE TO NEXT POINT, THAT BECOMES THE CURRENT POINT

void
FreemanChain::moveNext()
{

  _iter++;
  _current = _iter->toPoint(_current);
}


// MOVE TO PREVIOUS POINT, THAT BECOMES THE CURRENT POINT

void
FreemanChain::movePrevious()
{
  _current = _iter->toOppositePoint(_current);
  _iter--;
}


// -------------------------------------------------------------------
// A C C E S S   T O   F R E E M A N   C O D E S
// -------------------------------------------------------------------


// GET THE (STL) LIST OF FREEMAN CODES

const std::list<FreemanCode>&
FreemanChain::accessCodesList() const
{
  return _chain;
}


// -------------------------------------------------------------------
// A C C E S S   T O   P O I N T S 
// -------------------------------------------------------------------


// GET THE FIRST POINT

const GenPoint<int>&
FreemanChain::accessFront() const
{
  return _first;
}

// GET A COPY OF THE FIRST POINT

GenPoint<int>
FreemanChain::front() const
{
  return _first;
}

// GET THE LAST POINT

const GenPoint<int>&
FreemanChain::accessBack() const
{
  return _last;
}

// GET A COPY OF THE LAST POINT

GenPoint<int>
FreemanChain::back() const
{
  return _last;
}

// GET THE CURRENT POINT

const GenPoint<int>&
FreemanChain::accessCurrent() const
{
  return _current;
}

// GET A COPY OF THE CURRENT POINT

GenPoint<int>
FreemanChain::current() const
{
  return _current;
}

// GET THE SUCCESSOR OF THE CURRENT POINT

const GenPoint<int>&
FreemanChain::accessNext()
{
  moveNext();
  return _current;
}

// GET A COPY OF THE SUCCESSOR OF THE CURRENT POINT

GenPoint<int>
FreemanChain::next()
{
  moveNext();
  return _current;
}

// GET THE PREDECESSOR OF THE CURRENT POINT

const GenPoint<int>&
FreemanChain::accessPrevious()
{
  movePrevious();
  return _current;
}

// GET A COPY OF THE PREDECESSOR OF THE CURRENT POINT

GenPoint<int>
FreemanChain::previous()
{
  movePrevious();
  return _current;
}


// -------------------------------------------------------------------
// I N S E R T I O N 
// -------------------------------------------------------------------


// INSERT A POINT AT THE BEGINNING OF THE CHAIN
//
// WARNING
// - When the chain is not empty, the new point is supposed
//   to be consistent with the coding of the chain: All the points
//   of the segment joining the first point of the chain to the
//   new point must be strictly aligned along one of the 8 Freeman
//   directions.
// - A new point is always inserted in the chain, even when
//   the given point is the same as the first point of the chain
//   or is aligned with the first segment of the chain.

void
FreemanChain::push_front(const GenPoint<int>& aPt)
{
 if (_chain.empty())
    {
      // EMPTY CHAIN
      // -----------

      // Insert new point in chain
      _chain.push_back(FreemanCode(QGE_DIRECTION_N, 0));
      // Update first, current and last points in chain
      _first   = aPt;
      _current = aPt;
      _last    = aPt;
      // Set iterator to the beginning of chain
      _iter = _chain.begin();
    }
  else
    {
      // NON-EMPTY CHAIN
      // ---------------
      
      int dx = aPt.x() - _first.x();
      int dy = aPt.y() - _first.y();

      // Insert new point as the beginning of the chain
      FreemanCode& code = _chain.front();
      code.setDirLength(qgDirection(dx, dy), (dx == 0) ? abs(dy) : abs(dx));

      // New beginning of the list representing the chain
      _chain.push_front(FreemanCode(QGE_DIRECTION_N, 0));
      // Update first point in chain
      _first = aPt;
    }
}


// INSERT A POINT DEFINED BY A FREEMAN CODE
// AT THE BEGINNING OF THE CHAIN
//
// WARNING
// - The chain is supposed not to be empty.
// - A new point is always inserted in the chain, even when
//   the direction of the given Freeman code is the same as
//   the direction of the first Freeman code of the chain, or when
//   it is the opposite of the direction of the first Freeman code
//   of the chain.

void
FreemanChain::push_front(const FreemanCode& aCode)
{
  // Insert new point as the beginning of the chain
  FreemanCode& code = _chain.front();
  code.setDirLength(qgOpposite(aCode.direction()), aCode.length());

  // New beginning of the list representing the chain
  _chain.push_front(FreemanCode(QGE_DIRECTION_N, 0));

  // Update first point in chain
  _first = aCode.toPoint(_first);
}


// INSERT A POINT AT THE END OF THE CHAIN
//
// WARNING
// - When the chain is not empty, the new point is supposed
//   to be consistent with the coding of the chain: All the points
//   of the segment joining the last point of the chain to the
//   new point must be strictly aligned along one of the 8 Freeman
//   directions.
// - A new point is always inserted in the chain, even when
//   the given point is the same as the last point of the chain
//   or is aligned with the last segment of the chain.

void
FreemanChain::push_back(const GenPoint<int>& aPt)
{
  if (_chain.empty())
    {
      // EMPTY CHAIN
      // -----------
      // Insert new point in chain
      _chain.push_back(FreemanCode(QGE_DIRECTION_N, 0));
      // Update first, current and last points in chain
      _first   = aPt;
      _current = aPt;
      _last    = aPt;
      // Update iterator
      _iter = _chain.begin();
    }
  else
    {
      // NON-EMPTY CHAIN
      // ---------------
      
      int dx = _last.x() - aPt.x();
      int dy = _last.y() - aPt.y();

      // Insert new point as the end of the chain
      _chain.push_back
        (FreemanCode(qgDirection(dx, dy), (dx == 0) ? abs(dy) : abs(dx)));
      // Update last point in chain
      _last = aPt;
    }
}


// INSERT A POINT DEFINED BY A FREEMAN CODE AT THE END OF THE CHAIN
//
// @warning
// - The chain is supposed not to be empty.
// - A new point is always inserted in the chain, when
//   the direction of the given Freeman code is the same as
//   the direction of the last Freeman code of the chain, or when
//   it is the opposite of the direction of the last Freeman code
//   of the chain.

void
FreemanChain::push_back(const FreemanCode& aCode)
{
  _chain.push_back(aCode);
  // Update last point
  _last = aCode.toPoint(_last);
}


// -------------------------------------------------------------------
// T R A N S F O R M A T I O N S 
// -------------------------------------------------------------------


// REVERSE ELEMENTS ORDER IN THE CHAIN
// NOTHING TO DO IF THE CHAIN DOES NOT INCLUDE AT LEAST TWO POINTS

void
FreemanChain::reverse()
{
  int chLg = _chain.size();
  if (chLg > 1)
    {
// Starting from both ends of the chain (first element excepted),
// swap elements after having changed each direction for its opposite.
//
//              +-----+    +----+    +----+     +----+    +----+
// _first = P0  |North|    | D1 |    | D2 |     |Dn-1|    | Dn |
// _last  = Pn  +-----+<==>+----+<==>+----+ ... +----+<==>+----+
//              |  0  |    | L1 |    | L2 |     |Ln-1|    | Ln |
//              +-----+    +----+    +----+     +----+    +----+
//                           ^                               ^
//                           |       dx = opposite(Dx)       |
//                           |_______________________________|
//                                           |
//                                           V
//              +-----+    +----+    +----+     +----+    +----+
// _first = Pn  |North|    | dn |    |dn-1|     | d2 |    | d1 |
// _last  = P0  +-----+<==>+----+<==>+----+ ... +----+<==>+----+
//              |  0  |    | Ln |    |Ln-1|     | L2 |    | L1 |
//              +-----+    +----+    +----+     +----+    +----+

      QGEdirection dir;
      int lg;

      int iCntEnd = (chLg - 1) / 2;

      std::list<FreemanCode>::iterator it = _chain.begin();
      it++;
      std::list<FreemanCode>::iterator itRev = _chain.end();
      itRev--;

      for (int iCnt = 1 ; iCnt <= iCntEnd ; iCnt++, it++, itRev--)
        {
          dir = qgOpposite(it->direction());
          lg  = it->length();

          it->setDirLength(qgOpposite(itRev->direction()), itRev->length());
          itRev->setDirLength(dir, lg);
        }

      // Invert direction of the last element if necessary
      if (((chLg + 1) % 2) == 1)
        {
          it->setDir(qgOpposite(it->direction()));
        }

      // Update first and last points
      int x = _last.x();
      int y = _last.y();
      _last = _first;
      _first.setXY(x, y);

      // Update current point
      _current = _first;
      it = _chain.begin();
      bool loop = true;
      while (loop)
        {
          _current = it->toPoint(_current);

          if (it == _iter)
            {
              loop = false;
            }
          else
            {
              it++;
            }
        } // END while
    }
}


// -------------------------------------------------------------------
// C O N V E R S I O N S 
// -------------------------------------------------------------------


// CONVERT INTO A (STL) LIST OF POINTS HAVING INTEGER COORDINATES

std::list< GenPoint<int> >
FreemanChain::toPointList() const
{
  std::list< GenPoint<int> > ptList;
  GenPoint<int> pt = _first;

  for (std::list<FreemanCode>::const_iterator itCh = _chain.begin();
       itCh != _chain.end();
       ++itCh)
    {
      pt = itCh->toPoint(pt);
      ptList.push_back(pt);
    }

  return ptList;
}

// CONVERT INTO A (STL) LIST OF POINTS HAVING FLOAT COORDINATES

std::list< GenPoint<float> >
FreemanChain::toFPointList() const
{
  std::list< GenPoint<float> > ptList;
  GenPoint<float> pt = (GenPoint<float>)_first;

  for (std::list<FreemanCode>::const_iterator itCh = _chain.begin();
       itCh != _chain.end();
       ++itCh)
    {
      pt = itCh->toPoint(pt);  // Implicit conversion
      ptList.push_back(pt);
    }

  return ptList;
}

// CONVERT INTO A (STL) LIST OF POINTS HAVING DOUBLE COORDINATES

std::list< GenPoint<double> >
FreemanChain::toDPointList() const
{
  std::list< GenPoint<double> > ptList;
  GenPoint<double> pt = (GenPoint<double>)_first;

  for (std::list<FreemanCode>::const_iterator itCh = _chain.begin();
       itCh != _chain.end();
       ++itCh)
    {
      pt = itCh->toPoint(pt);  // Implicit conversion
      ptList.push_back(pt);
    }

  return ptList;
}


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


// ASSIGNMENT

FreemanChain&
FreemanChain::operator=(const FreemanChain& aFreemanCh)
{
  // Are left hand side and right hand side different objects?
  if (this != &aFreemanCh)
    {
      _chain = aFreemanCh._chain;
      // Set iterator to the beginning of the chain
      _iter = _chain.begin();

      _first   = aFreemanCh._first;
      _current = aFreemanCh._current;
      _last    = aFreemanCh._last;
    }

  return *this;
}


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


} // namespace qgar