Jpp - the software that should make you happy
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Public Member Functions | Static Public Member Functions | Static Public Attributes | Static Protected Member Functions | List of all members
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, TgetPair (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.

539  {}

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
__beginbegin of data
__endend of data
deltawidth of strip
Returns
minimal distance

Definition at line 418 of file JGeometry2DToolkit.hh.

419  {
420  using namespace std;
421 
422  double Dmin = delta;
423 
424  sort(__begin, __end, compareY);
425 
426  for (T i = __begin; i != __end; ++i) {
427  for (T j = i; ++j != __end && (j->getY() - i->getY()) < Dmin; ) {
428 
429  const double d = getDistance(*i, *j);
430 
431  if (d < Dmin) {
432  Dmin = d;
433  }
434  }
435  }
436 
437  sort(__begin, __end, compareX);
438 
439  return Dmin;
440  }
static const JCompareX compareX
Function object for sorting elements.
double getDistance(const JFirst_t &first, const JSecond_t &second)
Get distance between objects.
do set_variable OUTPUT_DIRECTORY $WORKDIR T
static const JCompareY compareY
Function object for sorting elements.
then JMuonMCEvt f $INPUT_FILE o $INTERMEDIATE_FILE d
Definition: JMuonPath.sh:45
int j
Definition: JPolint.hh:666
template<class T >
static double JGEOMETRY2D::JSmallestDistance2D::getDmin ( T  __begin,
T  __end 
)
inlinestaticprotected

Recursive method to find the smallest distance.

Parameters
__beginbegin of data
__endend of data
Returns
minimal distance

Definition at line 451 of file JGeometry2DToolkit.hh.

452  {
453  using namespace std;
454 
455  const int N = distance(__begin, __end);
456 
457  if (N <= 3) {
458 
459  double Dmin = numeric_limits<double>::max();
460 
461  for (T i = __begin; i != __end; ++i) {
462  for (T j = i; ++j != __end; ) {
463 
464  const double d = getDistance(*i, *j);
465 
466  if (d < Dmin) {
467  Dmin = d;
468  }
469  }
470  }
471 
472  return Dmin;
473 
474  } else {
475 
476  T i = __begin;
477 
478  advance(i, N/2);
479 
480  const double dl = getDmin(__begin, i);
481  const double dr = getDmin(i, __end);
482 
483  const double Dmin = min(dl, dr);
484 
485  T il = i;
486  T ir = i;
487 
488  while (--il != __begin && i ->getX() - il->getX() < Dmin) {}
489  while (++ir != __end && ir->getX() - i ->getX() < Dmin) {}
490 
491  return min(Dmin, getDmin(++il, ir, Dmin));
492  }
493  }
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
double getDistance(const JFirst_t &first, const JSecond_t &second)
Get distance between objects.
do set_variable OUTPUT_DIRECTORY $WORKDIR T
counter_type advance(counter_type &counter, const counter_type value, const counter_type limit=std::numeric_limits< counter_type >::max())
Advance counter.
then JMuonMCEvt f $INPUT_FILE o $INTERMEDIATE_FILE d
Definition: JMuonPath.sh:45
int j
Definition: JPolint.hh:666
then usage $script[input file[working directory[option]]] nWhere option can be N
Definition: JMuonPostfit.sh:37
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
__beginbegin of data
__endend of data
Returns
minimal distance

Definition at line 555 of file JGeometry2DToolkit.hh.

556  {
557  using namespace std;
558 
559  sort(__begin, __end, compareX);
560 
561  return getDmin(__begin, __end);
562  }
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
static const JCompareX compareX
Function object for sorting elements.
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
__beginbegin of data
__endend of data
deltawidth of strip
Returns
minimal distance

Definition at line 575 of file JGeometry2DToolkit.hh.

576  {
577  using namespace std;
578 
579  double Dmin = delta;
580 
581  sort(__begin, __end, compareX);
582 
583  for (T i = __begin; i != __end; ) {
584 
585  T j = i;
586 
587  for ( ; ++j != __end && (j->getX() - i->getX()) < Dmin; ) {}
588 
589  const double d = getDmin(i, j);
590 
591  if (d < Dmin) {
592  Dmin = d;
593  }
594 
595  i = j;
596  }
597 
598  return Dmin;
599  }
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
static const JCompareX compareX
Function object for sorting elements.
do set_variable OUTPUT_DIRECTORY $WORKDIR T
then JMuonMCEvt f $INPUT_FILE o $INTERMEDIATE_FILE d
Definition: JMuonPath.sh:45
int j
Definition: JPolint.hh:666
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
__beginbegin of data
__endend of data
Dmaxmaximal distance
Returns
pair of elements

Definition at line 612 of file JGeometry2DToolkit.hh.

613  {
614  using namespace std;
615 
616  sort(__begin, __end, compareX);
617 
618  for (T i = __begin; i != __end; ++i) {
619 
620  T j = i;
621 
622  while (++j != __end && (j->getX() - i->getX()) <= Dmax) {}
623 
624  if (distance(i,j) != 1) {
625 
626  if (distance(i,j) == 2) {
627 
628  if (getDistance(*i, *--j) <= Dmax) {
629  return make_pair(i,j);
630  }
631 
632  } else {
633 
634  sort(i, j, compareY);
635 
636  for (T __i = i; __i != j; ++__i) {
637  for (T __j = __i; ++__j != j && (__j->getY() - __i->getY()) <= Dmax; ) {
638 
639  const double d = getDistance(*__i, *__j);
640 
641  if (d <= Dmax) {
642  return make_pair(__i,__j);
643  }
644  }
645  }
646 
647  sort(i, j, compareX);
648  }
649  }
650  }
651 
652  return make_pair(__end,__end);
653  }
static const JCompareX compareX
Function object for sorting elements.
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
double getDistance(const JFirst_t &first, const JSecond_t &second)
Get distance between objects.
do set_variable OUTPUT_DIRECTORY $WORKDIR T
static const JCompareY compareY
Function object for sorting elements.
then JMuonMCEvt f $INPUT_FILE o $INTERMEDIATE_FILE d
Definition: JMuonPath.sh:45
int j
Definition: JPolint.hh:666

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: