Jpp test-rotations-old
the software that should make you happy
Loading...
Searching...
No Matches
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.
 
template<class T >
double operator() (T __begin, T __end) const
 Get smallest distance between two points.
 
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.
 

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.
 

Static Public Attributes

static const JCompareX compareX
 Function object for sorting elements.
 
static const JCompareY compareY
 Function object for sorting elements.
 

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.
 
template<class T >
static double getDmin (T __begin, T __end)
 Recursive method to find the smallest distance.
 

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

◆ JSmallestDistance2D()

JGEOMETRY2D::JSmallestDistance2D::JSmallestDistance2D ( )
inline

Default constructor.

Definition at line 538 of file JGeometry2DToolkit.hh.

539 {}

Member Function Documentation

◆ getDmin() [1/2]

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 JCompareY compareY
Function object for sorting elements.
static const JCompareX compareX
Function object for sorting elements.
int j
Definition JPolint.hh:801

◆ getDmin() [2/2]

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 }
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
counter_type advance(counter_type &counter, const counter_type value, const counter_type limit=std::numeric_limits< counter_type >::max())
Advance counter.

◆ operator()() [1/2]

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 }

◆ operator()() [2/2]

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 }

◆ getPair()

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 }

Member Data Documentation

◆ compareX

const JCompareX JGEOMETRY2D::JSmallestDistance2D::compareX
static

Function object for sorting elements.

Definition at line 542 of file JGeometry2DToolkit.hh.

◆ compareY

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: