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

qgar::GenConvexHull< T > Class Template Reference
[Convex hulls]

#include <qgarlib/GenConvexHull.H>

Inheritance diagram for qgar::GenConvexHull< T >:

qgar::ISerializable List of all members.

Detailed Description

template<class T>
class qgar::GenConvexHull< T >

A convex hull represented by a series of points with coordinates of type T.

The hull is constructed from a set of points using Graham's scan [Graham, 1972]. This algorithm works in three steps:

  1. Find an extreme point, the so-called pivot, which is guaranteed to be on the hull: Here, it is chosen as the point with the minimum Y coordinate. In case of equality, the point with the minimum X coordinate is selected.
  2. Sort the points in order of increasing angles about the pivot. The result is a star-shaped polygon, in which the pivot can see the whole polygon.
  3. Build the hull by marching around the star-shaped polygon, adding edges at right turns, and backtracking at left turns.

Such a hull may be empty. It is implemented by:

The GenConvexHull class is not supposed to be derived: No function member (destructor or whatever else) is virtual. Predefined instances of the class are qgar::ConvexHull, qgar::IConvexHull, qgar::FConvexHull, and qgar::DConvexHull.

Warning:
The hull is not guaranteed to be valid when constructed from an initial set of points including duplicates.
Todo:
Class to be completed: In particular, insertion and removal of points are not implemented.
Author:
Gérald Masini
Date:
March 24, 2004 11:24
Since:
Qgar 2.1.1

Definition at line 116 of file GenConvexHull.H.

Public Types

Types
typedef T value_type
 Type of the points.
typedef value_type & reference
 Reference to qgar::GenConvexHull::value_type.
typedef const value_type & const_reference
 Constant reference to qgar::GenConvexHull::value_type.
typedef value_type * pointer
 Pointer to qgar::GenConvexHull::value_type.
typedef const value_type * const_pointer
 Constant pointer to qgar::GenConvexHull::value_type.

Public Member Functions

Constructors
 GenConvexHull ()
 Default constructor.
 GenConvexHull (const GenConvexHull< value_type > &aCHull)
 Copy constructor.
 GenConvexHull (const std::list< GenPoint< value_type > > &aPtList)
 Construct from a STL list of points.
Destructor
 ~GenConvexHull ()
 Non-virtual destructor: The class is not supposed to be derived.
Access to characteristics
bool empty () const
 Is hull empty?
int size () const
 Get number of vertices.
Access to vertices
const std::list< GenPoint<
value_type > > & 		accessVertices () const
 Get vertices.
std::list< GenPoint< value_type > > vertices () const
 Get a copy of the vertices.
const GenPoint< value_type > & accessPivot () const
 Get pivot.
GenPoint< value_type > pivot () const
 Get a copy of the pivot.
Operators
GenConvexHull< value_type > & operator= (const GenConvexHull< value_type > &aCHull)
 Assignment operator.
Serialization/deserialization
virtual std::istream & read (std::istream &anInStream)
 Deserializes the current hull from an input stream.
virtual std::ostream & write (std::ostream &anOutStream) const
 Serializes the current hull to an input stream.

Protected Types

Type definitions
typedef std::pair< double,
GenPoint< value_type > > 		QGDpair
 Pair associating a vertex with its angle about the pivot.

Protected Attributes

The hull
std::list< GenPoint< value_type > > _vertices
 The list of the vertices of the hull.
std::multiset< QGDpair, _sortPred > _hull
 Sorted STL multiset of STL pairs associating a vertex (of the hull) with the angle between the X axis and the vector joining the pivot and the vertex.
GenPoint< value_type > _pivot
 The pivot.

Private Member Functions

Auxiliary functions
void PRIVATEgraham_sScan (const std::list< GenPoint< value_type > > &aPtList)
 Perfom Graham's scan to construct the convex hull from a given list of points.

Classes

struct  _sortPred
 To compare angles about the pivot when sorting points to construct their hull. More...

Member Typedef Documentation

template<class T>
typedef const value_type* qgar::GenConvexHull< T >::const_pointer
 

Constant pointer to qgar::GenConvexHull::value_type.

Definition at line 153 of file GenConvexHull.H.

template<class T>
typedef const value_type& qgar::GenConvexHull< T >::const_reference
 

Constant reference to qgar::GenConvexHull::value_type.

Definition at line 143 of file GenConvexHull.H.

template<class T>
typedef value_type* qgar::GenConvexHull< T >::pointer
 

Pointer to qgar::GenConvexHull::value_type.

Definition at line 148 of file GenConvexHull.H.

template<class T>
typedef std::pair< double, GenPoint<value_type> > qgar::GenConvexHull< T >::QGDpair [protected]
 

Pair associating a vertex with its angle about the pivot.

Definition at line 300 of file GenConvexHull.H.

template<class T>
typedef value_type& qgar::GenConvexHull< T >::reference
 

Reference to qgar::GenConvexHull::value_type.

Definition at line 138 of file GenConvexHull.H.

template<class T>
typedef T qgar::GenConvexHull< T >::value_type
 

Type of the points.

Definition at line 133 of file GenConvexHull.H.

Constructor & Destructor Documentation

template<class T>
qgar::GenConvexHull< T >::GenConvexHull (   ) 
 

Default constructor.

Construct an empty hull.

Definition at line 64 of file GenConvexHull.TCC.

template<class T>
qgar::GenConvexHull< T >::GenConvexHull (  const GenConvexHull< value_type > &  aCHull  ) 
 

Copy constructor.

Parameters:
aCHull a convex hull

Definition at line 82 of file GenConvexHull.TCC.

template<class T>
qgar::GenConvexHull< T >::GenConvexHull (  const std::list< GenPoint< value_type > > &  aPtList  ) 
 

Construct from a STL list of points.

Parameters:
aPtList a STL list of points
The convex hull is constructed using Graham's scan. Duplicate points are eliminated.

Definition at line 73 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::PRIVATEgraham_sScan().

template<class T>
qgar::GenConvexHull< T >::~GenConvexHull (   ) 
 

Non-virtual destructor: The class is not supposed to be derived.

Definition at line 97 of file GenConvexHull.TCC.

Member Function Documentation

template<class T>
const GenPoint< T > & qgar::GenConvexHull< T >::accessPivot (   )  const
 

Get pivot.

Definition at line 154 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_pivot.

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

template<class T>
const std::list< GenPoint< T > > & qgar::GenConvexHull< T >::accessVertices (   )  const
 

Get vertices.

Definition at line 135 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_vertices.

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

template<class T>
bool qgar::GenConvexHull< T >::empty (   )  const [inline]
 

Is hull empty?

Definition at line 111 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_vertices.

template<class T>
GenConvexHull< T > & qgar::GenConvexHull< T >::operator= (  const GenConvexHull< value_type > &  aCHull  ) 
 

Assignment operator.

Parameters:
aCHull a hull

Definition at line 178 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_hull, qgar::GenConvexHull< T >::_pivot, and qgar::GenConvexHull< T >::_vertices.

template<class T>
GenPoint< T > qgar::GenConvexHull< T >::pivot (   )  const
 

Get a copy of the pivot.

Definition at line 163 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_pivot.

template<class T>
void qgar::GenConvexHull< T >::PRIVATEgraham_sScan (  const std::list< GenPoint< value_type > > &  aPtList  )  [private]
 

Perfom Graham's scan to construct the convex hull from a given list of points.

Parameters:
aPtList the initial list of points, from which to construct the convex hull

Definition at line 258 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_hull, qgar::GenConvexHull< T >::_pivot, qgar::GenConvexHull< T >::_vertices, qgar::Math::QG_PI, and qgar::qgAngle().

Referenced by qgar::GenConvexHull< T >::GenConvexHull(), and qgar::GenConvexHull< T >::read().

template<class T>
std::istream & qgar::GenConvexHull< T >::read (  std::istream &  anInStream  )  [virtual]
 

Deserializes the current hull from an input stream.

Parameters:
anInStream the input stream
A serialized hull is represented by: 
  ConvexHull(<VERTICES COUNT>)(<VERTICE 1>)...(<VERTICE n>)

Implements qgar::ISerializable.

Definition at line 199 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::PRIVATEgraham_sScan(), qgar::qgReadObjData(), and qgar::qgReadObjName().

template<class T>
int qgar::GenConvexHull< T >::size (   )  const [inline]
 

Get number of vertices.

Definition at line 120 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_vertices.

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

template<class T>
std::list< GenPoint< T > > qgar::GenConvexHull< T >::vertices (   )  const
 

Get a copy of the vertices.

Definition at line 145 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_vertices.

template<class T>
std::ostream & qgar::GenConvexHull< T >::write (  std::ostream &  anOutStream  )  const [virtual]
 

Serializes the current hull to an input stream.

Parameters:
anOutStream the output stream
A serialized hull is represented by: 
  ConvexHull(<VERTICES COUNT>)(<VERTICE 1>)...(<VERTICE n>)

Implements qgar::ISerializable.

Definition at line 227 of file GenConvexHull.TCC.

References qgar::GenConvexHull< T >::_vertices.

Member Data Documentation

template<class T>
std::multiset<QGDpair, _sortPred> qgar::GenConvexHull< T >::_hull [protected]
 

Sorted STL multiset of STL pairs associating a vertex (of the hull) with the angle between the X axis and the vector joining the pivot and the vertex.

Pairs are sorted in order of increasing angles.

Definition at line 373 of file GenConvexHull.H.

Referenced by qgar::GenConvexHull< T >::operator=(), and qgar::GenConvexHull< T >::PRIVATEgraham_sScan().

template<class T>
GenPoint<value_type> qgar::GenConvexHull< T >::_pivot [protected]
 

The pivot.

It is the initial given point of minimum ordinate, which is guaranteed to belong to the hull.

Definition at line 381 of file GenConvexHull.H.

Referenced by qgar::GenConvexHull< T >::accessPivot(), qgar::GenConvexHull< T >::operator=(), qgar::GenConvexHull< T >::pivot(), and qgar::GenConvexHull< T >::PRIVATEgraham_sScan().

template<class T>
std::list< GenPoint<value_type> > qgar::GenConvexHull< T >::_vertices [protected]
 

The list of the vertices of the hull.

The first point of the list is the pivot.

Definition at line 364 of file GenConvexHull.H.

Referenced by qgar::GenConvexHull< T >::accessVertices(), qgar::GenConvexHull< T >::empty(), qgar::GenConvexHull< T >::operator=(), qgar::GenConvexHull< T >::PRIVATEgraham_sScan(), qgar::GenConvexHull< T >::size(), qgar::GenConvexHull< T >::vertices(), and qgar::GenConvexHull< T >::write().

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