JGEOMETRY2D::JSmallestDistance2D Class Reference

Auxiliary class for determination of smallest distance between pair of 2D points. More...

#include <JGeometry2DToolkit.hh>

Classes
struct	JCompareX
	Auxiliary class for sorting elements. More...
struct	JCompareY
	Auxiliary class for sorting elements. More...

Public Member Functions
	JSmallestDistance2D ()
	Default constructor. More...
template<class T >
double	operator() (T __begin, T __end) const
	Get smallest distance between two points. More...
template<class T >
double	operator() (T __begin, T __end, const double delta) const
	Get distance beween the closest points within a strip around the median in z. More...

Static Public Member Functions
template<class T >
static std::pair< T, T >	getPair (T __begin, T __end, const double Dmax)
	Get pairs with smaller or equal given maximal distance. More...

Static Public Attributes
static const JCompareX	compareX
	Function object for sorting elements. More...
static const JCompareY	compareY
	Function object for sorting elements. More...

Static Protected Member Functions
template<class T >
static double	getDmin (T __begin, T __end, const double delta)
	Get distance beween the closest points within a strip around the median in x. More...
template<class T >
static double	getDmin (T __begin, T __end)
	Recursive method to find the smallest distance. More...

Detailed Description

Auxiliary class for determination of smallest distance between pair of 2D points.

Reference: Computational Geometry Algorithms and Applications Authors: de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.

Definition at line 406 of file JGeometry2DToolkit.hh.

Constructor & Destructor Documentation

JGEOMETRY2D::JSmallestDistance2D::JSmallestDistance2D ( )

inline

Default constructor.

Definition at line 538 of file JGeometry2DToolkit.hh.

    {}

Member Function Documentation

template<class T >

static double JGEOMETRY2D::JSmallestDistance2D::getDmin ( T  __begin, T  __end, const double  delta  )

inlinestaticprotected

Get distance beween the closest points within a strip around the median in x.

Note that this method runs not at O(n^2) but at O(6)!

Parameters

__begin	begin of data
__end	end of data
delta	width of strip

Returns

minimal distance

Definition at line 418 of file JGeometry2DToolkit.hh.

    {
      using namespace std;

      double Dmin = delta;
 
      sort(__begin, __end, compareY); 
 
      for (T i = __begin; i != __end; ++i) {
        for (T j = i; ++j != __end && (j->getY() - i->getY()) < Dmin; ) {

          const double d = getDistance(*i, *j);

          if (d < Dmin) {
            Dmin = d;
          }
        }
      }
      
      sort(__begin, __end, compareX);

      return Dmin;
    }

template<class T >

static double JGEOMETRY2D::JSmallestDistance2D::getDmin ( T  __begin, T  __end  )

inlinestaticprotected

Recursive method to find the smallest distance.

Parameters

__begin	begin of data
__end	end of data

Returns

minimal distance

Definition at line 451 of file JGeometry2DToolkit.hh.

    {
      using namespace std;

      const int N = distance(__begin, __end);

      if (N <= 3) {

        double Dmin = numeric_limits<double>::max();
 
        for (T i = __begin; i != __end; ++i) {
          for (T j = i; ++j != __end; ) {

            const double d = getDistance(*i, *j);

            if (d < Dmin) {
              Dmin = d;
            }
          }
        }

        return Dmin;

      } else {
 
        T i = __begin;

        advance(i, N/2);

        const double dl   = getDmin(__begin, i);
        const double dr   = getDmin(i,   __end);

        const double Dmin = min(dl, dr);

        T il = i;
        T ir = i;
 
        while (--il != __begin && i ->getX() - il->getX() < Dmin) {}
        while (++ir != __end   && ir->getX() - i ->getX() < Dmin) {}

        return min(Dmin, getDmin(++il, ir, Dmin));
      }
    }

template<class T >

double JGEOMETRY2D::JSmallestDistance2D::operator() ( T  __begin, T  __end  ) const

inline

Get smallest distance between two points.

Note that this method changes the order of the elements.

Parameters

__begin	begin of data
__end	end of data

Returns

minimal distance

Definition at line 555 of file JGeometry2DToolkit.hh.

    {
      using namespace std;

      sort(__begin, __end, compareX);
      
      return getDmin(__begin, __end);
    }

template<class T >

double JGEOMETRY2D::JSmallestDistance2D::operator() ( T  __begin, T  __end, const double  delta  ) const

inline

Get distance beween the closest points within a strip around the median in z.

Note that this method changes the order of the elements.

Parameters

__begin	begin of data
__end	end of data
delta	width of strip

Returns

minimal distance

Definition at line 575 of file JGeometry2DToolkit.hh.

    {
      using namespace std;

      double Dmin = delta;

      sort(__begin, __end, compareX);
      
      for (T i = __begin; i != __end; ) {
        
        T j = i;

        for ( ; ++j != __end && (j->getX() - i->getX()) < Dmin; ) {}

        const double d = getDmin(i, j);

        if (d < Dmin) {
          Dmin = d;
        }

        i = j;
      }

      return Dmin;
    }

template<class T >

static std::pair<T,T> JGEOMETRY2D::JSmallestDistance2D::getPair ( T  __begin, T  __end, const double  Dmax  )

inlinestatic

Get pairs with smaller or equal given maximal distance.

Note that this method changes the order of the elements.

Parameters

__begin	begin of data
__end	end of data
Dmax	maximal distance

Returns

pair of elements

Definition at line 612 of file JGeometry2DToolkit.hh.

    {
      using namespace std;

      sort(__begin, __end, compareX);
      
      for (T i = __begin; i != __end; ++i) {
      
        T j = i;
             
        while (++j != __end && (j->getX() - i->getX()) <= Dmax) {}
      
        if (distance(i,j) != 1) {
        
          if (distance(i,j) == 2) {
          
            if (getDistance(*i, *--j) <= Dmax) {
              return make_pair(i,j);
            }
          
          } else {

            sort(i, j, compareY); 
          
            for (T __i = i; __i != j; ++__i) {
              for (T __j = __i; ++__j != j && (__j->getY() - __i->getY()) <= Dmax; ) {
              
                const double d = getDistance(*__i, *__j);
              
                if (d <= Dmax) {
                  return make_pair(__i,__j);
                }
              }
            }
          
            sort(i, j, compareX);
          }
        }
      }
    
      return make_pair(__end,__end);
    }

Member Data Documentation

const JCompareX JGEOMETRY2D::JSmallestDistance2D::compareX

static

Function object for sorting elements.

Definition at line 542 of file JGeometry2DToolkit.hh.

const JCompareY JGEOMETRY2D::JSmallestDistance2D::compareY

static

Function object for sorting elements.

Definition at line 543 of file JGeometry2DToolkit.hh.

---

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

• JGeometry2DToolkit.hh