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. More...
template<class T >
std::pair< T, T >	operator() (T __begin, T __end) const
	Get convex Hull. More...

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

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

Detailed Description

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

Definition at line 119 of file JGeometry2DToolkit.hh.

Constructor & Destructor Documentation

JGEOMETRY2D::JConvexHull2D::JConvexHull2D ( )

inline

Default constructor.

Definition at line 216 of file JGeometry2DToolkit.hh.

    {}

Member Function Documentation

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;
      }
    }

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

const JLowerHull JGEOMETRY2D::JConvexHull2D::sortLowerHull

static

Function object for sorting elements.

Definition at line 220 of file JGeometry2DToolkit.hh.

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