Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages
qgar::FreemanChain

qgar::FreemanChain Class Reference
[Points]

#include <qgarlib/FreemanChain.H>

Inheritance diagram for qgar::FreemanChain:

qgar::AbstractGenPointChain< int > List of all members.

Detailed Description

Chain of Freeman codes.

A Freeman chain represents a series of consecutive points, in an integer (i.e. discrete) coordinate system. It is coded as a series of integer vectors, defined by pairs (direction, length), starting from a point of given coordinates: 

                                     etc.
                                      *
                                     *
                            POINT-2 @ ^
                                    * |
                                    * |
                                  ^ * |
                                  | * |
                      DIRECTION-2 | * LENGTH-2
                                  | * |
                                    * |
                                    * |
  (STARTING)      DIRECTION-1 -->   * |
    POINT-0  @**********************@ V
             <------ LENGTH-1 ------> POINT-1

A direction is coded using predefined enum type qgar::QGEdirection. As the origin of the coordinates system in images is at top left corner, North and South are upside down for more convenience: 

  (0,0) +---------------------------------------------> X
        |
        |                 QGE_DIRECTION_N
        |                        |  
        |     QGE_DIRECTION_NW \ | / QGE_DIRECTION_NE
        |                       \|/
        |   QGE_DIRECTION_W -----+----- QGE_DIRECTION_E
        |                       /|\
        |     QGE_DIRECTION_SW / | \ QGE_DIRECTION_SE
        |                        |
        |                 QGE_DIRECTION_S
      Y V

A Freeman chain is implemented using a STL list of Freeman codes, instances of class qgar::FreemanCode: 

                                     _iter  (current point)
                                       |
                                       V
               +-----+    +----+    +----+             +----+
               |North|    | D1 |    | D2 |             | Dn |
     _chain    +-----+<==>+----+<==>+----+<==> ... <==>+----+
               |  0  |    | L1 |    | L2 |             | Ln |
               +-----+    +----+    +----+             +----+
The direction of the first code is always North (qgar::QGE_DIRECTION_N, the first value of the qgar::QGEdirection predefined enum type) and the length of the first code is always 0: The first code represents the first point of the chain (a null vector from the given starting point). In this way, the complete chain of points is consistently coded, which allows easier algorithm implementations.

An (internal) iterator, qgar::FreemanChain::_iter, allows bidirectional traversal of the chain. The validity of the iterator is preserved by any legal operation on the chain, unless the chain is empty.

Three points are permanently available as effective points, i.e. instances of class qgar::GenPoint<int>:

Use cases of a Freeman chain:

Warning:
A Freeman chain is not an appropriate way of representing a chain of points if efficiency is required for insertions or chain traversals. Class qgar::GenPointChain should be better used in this case. A STL list of the points coded by a Freeman chain can be also obtained using function qgar::FreemanChain::pointList.
Author:
Gérald Masini, from previous work by Karl Tombre
Date:
December 19, 2003 17:30
Since:
Qgar 2.1.1

Definition at line 173 of file FreemanChain.H.

Public Types

typedef int value_type
 Type of the points stored in the chain.
typedef value_type & reference
 Reference to qgar::AbstractGenPointChain::value_type.
typedef const value_type & const_reference
 Constant reference to qgar::AbstractGenPointChain::value_type.
typedef value_type * pointer
 Pointer to qgar::AbstractGenPointChain::value_type.
typedef const value_type * const_pointer
 Constant pointer to qgar::AbstractGenPointChain::value_type.

Public Member Functions

 AbstractGenPointChain ()
 Default constructor.
virtual void push_front (const GenPoint< value_type > &aPt)=0
 Insert a point at the beginning of the chain.
virtual void push_back (const GenPoint< value_type > &aPt)=0
 Insert a point at the end of the chain.
Constructors
 FreemanChain (const FreemanChain &aFreemanCh)
 Default constructor.Copy constructor.
 FreemanChain (const GenPoint< int > &aPt)
 Construct from a point, that becomes the current point.
 FreemanChain (const GenPoint< int > &aPt, QGEdirection aDir, unsigned int aLength)
 Construct from given point, direction and length.
Destructor
virtual ~FreemanChain ()
 Virtual destructor.
Access to chain characteristics
virtual bool empty () const
 Is current chain empty?
virtual int size () const
 Get chain length (number of points).
Iterator
virtual void setToBegin ()
 Make the internal iterator point to the beginning (first point) of the chain, that becomes the current point.
virtual void setToEnd ()
 Make the internal iterator point to the end (last point) of the chain, that becomes the current point.
virtual bool isAtBegin () const
 Does internal iterator points to the beginning of the chain?
virtual bool isAtEnd () const
 Does internal iterator points to the end of the chain?
virtual bool hasNext () const
 Is there a point after the current point?
virtual bool hasPrevious () const
 Is there a point before the current point?
virtual void moveNext ()
 Move to next point, that becomes the current point.
virtual void movePrevious ()
 Move to previous point, that becomes the current point.
Access to points
virtual const GenPoint< int > & accessFront () const
 Get the first point.
virtual GenPoint< int > front () const
 Get a copy of the first point.
virtual const GenPoint< int > & accessBack () const
 Get the last point.
virtual GenPoint< int > back () const
 Get a copy of the last point.
virtual const GenPoint< int > & accessCurrent () const
 Get the current point.
virtual GenPoint< int > current () const
 Get a copy of the current point.
virtual const GenPoint< int > & accessNext ()
 Get the successor of the current point.
virtual GenPoint< int > next ()
 Get a copy of the successor of the current point.
virtual const GenPoint< int > & accessPrevious ()
 Get the predecessor of the current point.
virtual GenPoint< int > previous ()
 Get a copy of the predecessor of the current point.
Access to Freeman codes
const std::list< FreemanCode > & accessCodesList () const
 Get the (STL) list of Freeman codes.
Insertion
virtual void push_front (const GenPoint< int > &aPt)
 Insert a point at the beginning of the chain.
void push_front (const FreemanCode &aCode)
 Insert a point whose location is defined by the given Freeman code, starting from the first point of the chain.
virtual void push_back (const GenPoint< int > &aPt)
 Insert a point at the end of the chain.
void push_back (const FreemanCode &aCode)
 Insert a point whose location is defined by the given Freeman code, starting from the last point of the chain.
Transformations
virtual void reverse ()
 Reverse elements order in the list.
Conversions
virtual std::list< GenPoint<
int > > 		toPointList () const
 Convert into a (STL) list of points having integer coordinates.
virtual std::list< GenPoint<
float > > 		toFPointList () const
 Convert into a (STL) list of points having float coordinates.
virtual std::list< GenPoint<
double > > 		toDPointList () const
 Convert into a (STL) list of points having double coordinates.
Operators
FreemanChain & operator= (const FreemanChain &aFreemanCh)
 Assignment.

Protected Attributes

Representation of a Freeman chain
std::list< FreemanCode > _chain
 The (STL) list of Freeman codes defining the points of the chain.
std::list< FreemanCode
>::iterator 		_iter
 Iterator on the list of Freeman codes.
Pre-computed points
GenPoint< int > _first
 First point of the chain.
GenPoint< int > _current
 Current point of the chain.
GenPoint< int > _last
 Last point of the chain.

Private Member Functions

Constructors
 FreemanChain ()
 Disabled default constructor.

Member Typedef Documentation

typedef const value_type* qgar::AbstractGenPointChain< int >::const_pointer [inherited]
 

Constant pointer to qgar::AbstractGenPointChain::value_type.

Definition at line 169 of file AbstractGenPointChain.H.

typedef const value_type& qgar::AbstractGenPointChain< int >::const_reference [inherited]
 

Constant reference to qgar::AbstractGenPointChain::value_type.

Definition at line 159 of file AbstractGenPointChain.H.

typedef value_type* qgar::AbstractGenPointChain< int >::pointer [inherited]
 

Pointer to qgar::AbstractGenPointChain::value_type.

Definition at line 164 of file AbstractGenPointChain.H.

typedef value_type& qgar::AbstractGenPointChain< int >::reference [inherited]
 

Reference to qgar::AbstractGenPointChain::value_type.

Definition at line 154 of file AbstractGenPointChain.H.

typedef int qgar::AbstractGenPointChain< int >::value_type [inherited]
 

Type of the points stored in the chain.

Definition at line 149 of file AbstractGenPointChain.H.

Constructor & Destructor Documentation

qgar::FreemanChain::FreemanChain (  const FreemanChain &  aFreemanCh  ) 
 

Default constructor.Copy constructor.

Parameters:
aFreemanCh a Freeman chain
Warning:
The iterator points to the beginning of the chain.

Definition at line 88 of file FreemanChain.C.

References _chain, and _iter.

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

Construct from a point, that becomes the current point.

Parameters:
aPt a point (integer coordinates)
The iterator points to this point.

Definition at line 103 of file FreemanChain.C.

References _chain, and _iter.

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

Construct from given point, direction and length.

Parameters:
aPt a point (integer coordinates)
aDir direction code of the initial part of chain
aLength length of the initial part of chain
The iterator points to the end of the chain.

Warning:
The given length is supposed to be different from zero. Otherwise, the validity of the resulting chain is absolutely not guaranteed.

Definition at line 118 of file FreemanChain.C.

References _chain, _current, _iter, _last, and qgar::FreemanCode::toPoint().

qgar::FreemanChain::~FreemanChain (   )  [virtual]
 

Virtual destructor.

Definition at line 143 of file FreemanChain.C.

qgar::FreemanChain::FreemanChain (   )  [private]
 

Disabled default constructor.

The default constructor belongs to the private section so that a client cannot use it.

Definition at line 67 of file FreemanChain.C.

Member Function Documentation

qgar::AbstractGenPointChain< int >::AbstractGenPointChain (   )  [inherited]
 

Default constructor.

const GenPoint< int > & qgar::FreemanChain::accessBack (   )  const [virtual]
 

Get the last point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 296 of file FreemanChain.C.

References _last.

const std::list< FreemanCode > & qgar::FreemanChain::accessCodesList (   )  const
 

Get the (STL) list of Freeman codes.

The first element is an extra code including qgar::QGE_DIRECTION_N as direction and 0 as length: 

    +-----+      +----+      +----+               +----+
    |North|      | D1 |      | D2 |               | Dn |
    +-----+ <==> +----+ <==> +----+ <==> ... <==> +----+
    |  0  |      | L1 |      | L2 |               | Ln |
    +-----+      +----+      +----+               +----+
This implementation allows an easier implementation of algorithms.

Using this function to traverse the chain is much more efficient than using appropriate member functions like qgar::FreemanChain::setToBegin, qgar::FreemanChain::hasNext, qgar::FreemanChain::moveNext, etc. In particular, the points represented by the chain may be obtained by applying the successive Freeman codes of the chain to a point initialized to the first point of the chain, in the following way: 

    const std::list<FreemanCode>& lFc = myChain.accessCodesList();
    GenPoint<int> p = myChain.first();

    for (std::list<FreemanCode>::const_iterator it = lFc.begin();
         it != lFc.end();
	 it++)
      {
        // Current point
	p = (*it).toPoint(p);
	// Processing continues...
	...
      }

Definition at line 266 of file FreemanChain.C.

References _chain.

const GenPoint< int > & qgar::FreemanChain::accessCurrent (   )  const [virtual]
 

Get the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 312 of file FreemanChain.C.

References _current.

const GenPoint< int > & qgar::FreemanChain::accessFront (   )  const [virtual]
 

Get the first point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 280 of file FreemanChain.C.

References _first.

const GenPoint< int > & qgar::FreemanChain::accessNext (   )  [virtual]
 

Get the successor of the current point.

Warning:
The chain is supposed not to be empty, and the iterator is supposed not to point to the last point.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 328 of file FreemanChain.C.

References _current, and moveNext().

const GenPoint< int > & qgar::FreemanChain::accessPrevious (   )  [virtual]
 

Get the predecessor of the current point.

Warning:
The chain is supposed not to be empty, and the iterator is supposed not to point to the first point.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 346 of file FreemanChain.C.

References _current, and movePrevious().

GenPoint< int > qgar::FreemanChain::back (   )  const [virtual]
 

Get a copy of the last point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 304 of file FreemanChain.C.

References _last.

GenPoint< int > qgar::FreemanChain::current (   )  const [virtual]
 

Get a copy of the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 320 of file FreemanChain.C.

References _current.

bool qgar::FreemanChain::empty (   )  const [virtual]
 

Is current chain empty?

Implements qgar::AbstractGenPointChain< int >.

Definition at line 157 of file FreemanChain.C.

References _chain.

GenPoint< int > qgar::FreemanChain::front (   )  const [virtual]
 

Get a copy of the first point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 288 of file FreemanChain.C.

References _first.

bool qgar::FreemanChain::hasNext (   )  const [virtual]
 

Is there a point after the current point?

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 221 of file FreemanChain.C.

References _chain, and _iter.

bool qgar::FreemanChain::hasPrevious (   )  const [virtual]
 

Is there a point before the current point?

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 231 of file FreemanChain.C.

References _chain, and _iter.

bool qgar::FreemanChain::isAtBegin (   )  const [virtual]
 

Does internal iterator points to the beginning of the chain?

Implements qgar::AbstractGenPointChain< int >.

Definition at line 203 of file FreemanChain.C.

References _chain, and _iter.

bool qgar::FreemanChain::isAtEnd (   )  const [virtual]
 

Does internal iterator points to the end of the chain?

Implements qgar::AbstractGenPointChain< int >.

Definition at line 212 of file FreemanChain.C.

References _chain, and _iter.

void qgar::FreemanChain::moveNext (   )  [virtual]
 

Move to next point, that becomes the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 240 of file FreemanChain.C.

References _current, and _iter.

Referenced by accessNext(), and next().

void qgar::FreemanChain::movePrevious (   )  [virtual]
 

Move to previous point, that becomes the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 251 of file FreemanChain.C.

References _current, and _iter.

Referenced by accessPrevious(), and previous().

GenPoint< int > qgar::FreemanChain::next (   )  [virtual]
 

Get a copy of the successor of the current point.

Warning:
The chain is supposed not to be empty, and the iterator is supposed not to point to the last point.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 337 of file FreemanChain.C.

References _current, and moveNext().

FreemanChain & qgar::FreemanChain::operator= (  const FreemanChain &  aFreemanCh  ) 
 

Assignment.

Parameters:
aFreemanCh a Freeman chain
Warning:
The internal iterator points to the beginning of the chain.

Definition at line 662 of file FreemanChain.C.

References _chain, _current, _first, _iter, and _last.

GenPoint< int > qgar::FreemanChain::previous (   )  [virtual]
 

Get a copy of the predecessor of the current point.

Warning:
The chain is supposed not to be empty, and the iterator is supposed not to point to the first point.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 355 of file FreemanChain.C.

References _current, and movePrevious().

virtual void qgar::AbstractGenPointChain< int >::push_back (  const GenPoint< value_type > &  aPt  )  [pure virtual, inherited]
 

Insert a point at the end of the chain.

Parameters:
aPt a point
The internal iterator remains valid after the operation.

void qgar::FreemanChain::push_back (  const FreemanCode &  aCode  ) 
 

Insert a point whose location is defined by the given Freeman code, starting from the last point of the chain.

Parameters:
aCode a Freeman code
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.

Definition at line 498 of file FreemanChain.C.

References _chain, _last, and qgar::FreemanCode::toPoint().

void qgar::FreemanChain::push_back (  const GenPoint< int > &  aPt  )  [virtual]
 

Insert a point at the end of the chain.

Parameters:
aPt a point
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.

Definition at line 455 of file FreemanChain.C.

References _chain, _current, _first, _iter, _last, qgar::qgDirection(), qgar::QGE_DIRECTION_N, qgar::GenPoint< T >::x(), and qgar::GenPoint< T >::y().

virtual void qgar::AbstractGenPointChain< int >::push_front (  const GenPoint< value_type > &  aPt  )  [pure virtual, inherited]
 

Insert a point at the beginning of the chain.

Parameters:
aPt a point
The internal iterator remains valid after the operation.

void qgar::FreemanChain::push_front (  const FreemanCode &  aCode  ) 
 

Insert a point whose location is defined by the given Freeman code, starting from the first point of the chain.

Parameters:
aCode a Freeman code
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.

Definition at line 428 of file FreemanChain.C.

References _chain, _first, qgar::FreemanCode::direction(), qgar::FreemanCode::length(), qgar::QGE_DIRECTION_N, qgar::qgOpposite(), qgar::FreemanCode::setDirLength(), and qgar::FreemanCode::toPoint().

void qgar::FreemanChain::push_front (  const GenPoint< int > &  aPt  )  [virtual]
 

Insert a point at the beginning of the chain.

Parameters:
aPt a point
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.

Definition at line 380 of file FreemanChain.C.

References _chain, _current, _first, _iter, _last, qgar::qgDirection(), qgar::QGE_DIRECTION_N, qgar::FreemanCode::setDirLength(), qgar::GenPoint< T >::x(), and qgar::GenPoint< T >::y().

void qgar::FreemanChain::reverse (   )  [virtual]
 

Reverse elements order in the list.

Warning:
The internal iterator points to the same element of the chain (but the content of this element has changed) once the operation is completed.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 515 of file FreemanChain.C.

References _chain, _current, _first, _iter, _last, qgar::qgOpposite(), qgar::GenPoint< T >::setXY(), qgar::GenPoint< T >::x(), and qgar::GenPoint< T >::y().

void qgar::FreemanChain::setToBegin (   )  [virtual]
 

Make the internal iterator point to the beginning (first point) of the chain, that becomes the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 181 of file FreemanChain.C.

References _chain, _current, _first, and _iter.

void qgar::FreemanChain::setToEnd (   )  [virtual]
 

Make the internal iterator point to the end (last point) of the chain, that becomes the current point.

Warning:
The chain is supposed not to be empty.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 192 of file FreemanChain.C.

References _chain, _current, _iter, and _last.

int qgar::FreemanChain::size (   )  const [virtual]
 

Get chain length (number of points).

Implements qgar::AbstractGenPointChain< int >.

Definition at line 166 of file FreemanChain.C.

References _chain.

std::list< GenPoint< double > > qgar::FreemanChain::toDPointList (   )  const [virtual]
 

Convert into a (STL) list of points having double coordinates.

Definition at line 637 of file FreemanChain.C.

References _chain, and _first.

Referenced by qgar::Maer::Maer().

std::list< GenPoint< float > > qgar::FreemanChain::toFPointList (   )  const [virtual]
 

Convert into a (STL) list of points having float coordinates.

Definition at line 618 of file FreemanChain.C.

References _chain, and _first.

std::list< GenPoint< int > > qgar::FreemanChain::toPointList (   )  const [virtual]
 

Convert into a (STL) list of points having integer coordinates.

Implements qgar::AbstractGenPointChain< int >.

Definition at line 599 of file FreemanChain.C.

References _chain, and _first.

Member Data Documentation

std::list<FreemanCode> qgar::FreemanChain::_chain [protected]
 

The (STL) list of Freeman codes defining the points of the chain.

Definition at line 583 of file FreemanChain.H.

Referenced by accessCodesList(), empty(), FreemanChain(), hasNext(), hasPrevious(), isAtBegin(), isAtEnd(), operator=(), push_back(), push_front(), reverse(), setToBegin(), setToEnd(), size(), toDPointList(), toFPointList(), and toPointList().

GenPoint<int> qgar::FreemanChain::_current [protected]
 

Current point of the chain.

Definition at line 605 of file FreemanChain.H.

Referenced by accessCurrent(), accessNext(), accessPrevious(), current(), FreemanChain(), moveNext(), movePrevious(), next(), operator=(), previous(), push_back(), push_front(), reverse(), setToBegin(), and setToEnd().

GenPoint<int> qgar::FreemanChain::_first [protected]
 

First point of the chain.

Definition at line 600 of file FreemanChain.H.

Referenced by accessFront(), front(), operator=(), push_back(), push_front(), reverse(), setToBegin(), toDPointList(), toFPointList(), and toPointList().

std::list<FreemanCode>::iterator qgar::FreemanChain::_iter [protected]
 

Iterator on the list of Freeman codes.

Definition at line 588 of file FreemanChain.H.

Referenced by FreemanChain(), hasNext(), hasPrevious(), isAtBegin(), isAtEnd(), moveNext(), movePrevious(), operator=(), push_back(), push_front(), reverse(), setToBegin(), and setToEnd().

GenPoint<int> qgar::FreemanChain::_last [protected]
 

Last point of the chain.

Definition at line 610 of file FreemanChain.H.

Referenced by accessBack(), back(), FreemanChain(), operator=(), push_back(), push_front(), reverse(), and setToEnd().

The documentation for this class was generated from the following files: