JGEOMETRY2D::JConvexHull2D Class Reference

Auxiliary class for convex hull determination in X-Y plane. More...

#include <JGeometry2DToolkit.hh>

Classes
struct	JLowerHull
	Auxiliary class for sorting elements. More...
struct	JUpperHull
	Auxiliary class for sorting elements. More...

Public Member Functions
	JConvexHull2D ()
	Default constructor.
template<class T >
std::pair< T, T >	operator() (T __begin, T __end) const
	Get convex Hull.

Static Public Attributes
static const JLowerHull	sortLowerHull
	Function object for sorting elements.
static const JUpperHull	sortUpperHull
	Function object for sorting elements.

Static Protected Member Functions
template<class T , class JCompare_t >
static T	getConvexHull2D (T __begin, T __end, JCompare_t compare)
	Partition half Hull.

Detailed Description

Auxiliary class for convex hull determination in X-Y plane.

Definition at line 119 of file JGeometry2DToolkit.hh.

Constructor & Destructor Documentation

JConvexHull2D()

JGEOMETRY2D::JConvexHull2D::JConvexHull2D ( )

inline

Default constructor.

Definition at line 216 of file JGeometry2DToolkit.hh.

    {}

Member Function Documentation

getConvexHull2D()

template<class T , class JCompare_t >

static T JGEOMETRY2D::JConvexHull2D::getConvexHull2D ( T __begin, T __end, JCompare_t compare )

inlinestaticprotected

Partition half Hull.

Parameters

__begin	begin of data
__end	end of data
compare	comparator

Returns

end of data

Definition at line 130 of file JGeometry2DToolkit.hh.

    {
      using namespace std;
 
      if (__begin != __end) {
        
        sort(__begin, __end, compare);
        
        T l = __begin;
        
        if (++l != __end) {
          
          T i = __begin; 
          
          ++(++i);
          
          for (T j, k; i != __end; ++i) {
            
            for (j = k = l; j != __begin && getCCW(*i, *j, *--k); --j) {}
            
            l = j;
            ++l;
 
            iter_swap(l,i);
          }
        }
        
        return l;
        
      } else {
 
        return __begin;
      }
    }

operator()()

template<class T >

std::pair< T, T > JGEOMETRY2D::JConvexHull2D::operator() ( T __begin, T __end ) const

inline

Get convex Hull.

Parameters

__begin	begin of data
__end	end of data

Returns

end of lower and upper Hull data

Definition at line 232 of file JGeometry2DToolkit.hh.

    {
      using namespace std;
 
      T __p = getConvexHull2D(__begin, __end, sortLowerHull);        // make lower hull
    
      if (__p == __begin || __p == __end) {
        return make_pair(__p, __p);
      }
    
      // add first point of lower hull to upper hull
    
      reverse(__begin, __p);
    
      T __q = getConvexHull2D(--__p, __end, sortUpperHull);          // make upper hull
    
      ++__q;
    
      // re-store order and keep the extra point
      
      reverse(__p,     __q);
      reverse(__begin, __q);
    
      const int n = distance(__p, __q);
    
      __p = __begin;
 
      advance(__p, n);
    
      return make_pair(__p, __q);
    }

Member Data Documentation

sortLowerHull

const JLowerHull JGEOMETRY2D::JConvexHull2D::sortLowerHull

static

Function object for sorting elements.

Definition at line 220 of file JGeometry2DToolkit.hh.

sortUpperHull

const JUpperHull JGEOMETRY2D::JConvexHull2D::sortUpperHull

static

Function object for sorting elements.

Definition at line 221 of file JGeometry2DToolkit.hh.

---

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

• JGeometry2DToolkit.hh