fastjet::ClosestPair2D Class Reference

concrete implementation for finding closest pairs in 2D -- will use Chan's (hopefully efficient) shuffle based structures More...

#include <ClosestPair2D.hh>

Inheritance diagram for fastjet::ClosestPair2D:

Inheritance graph
fastjet::ClosestPair2DBase
[legend]
Collaboration diagram for fastjet::ClosestPair2D:

Collaboration graph
fastjet::ClosestPair2DBasefastjet::ClosestPair2D::triplet\< unsigned int \>fastjet::ClosestPair2D::triplet\< T \>fastjet::ClosestPair2D::triplet\< std::auto_ptr\< Tree \> \>fastjet::Coord2D
[legend]
List of all members.

Public Member Functions

 ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner)
 constructor from a vector of 2D positions -- number of objects after insertion and deletion must never exceed positions.size(); objects are given IDs that correspond to their index in the vector of positions
 ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner, const unsigned int max_size)
 constructor which allows structure to grow beyond positions.size(), up to max_size
void closest_pair (unsigned int &ID1, unsigned int &ID2, double &distance2) const
 provides the IDs of the closest pair as well as the distance between them
void remove (unsigned int ID)
 removes the entry labelled by ID from the object;
unsigned int insert (const Coord2D &)
 inserts the position into the closest pair structure and returns the ID that has been allocated for the object.
virtual unsigned int replace (unsigned int ID1, unsigned int ID2, const Coord2D &position)
 removes ID1 and ID2 and inserts position, returning the ID corresponding to position.
virtual void replace_many (const std::vector< unsigned int > &IDs_to_remove, const std::vector< Coord2D > &new_positions, std::vector< unsigned int > &new_IDs)
 replaces IDs_to_remove with points at the new_positions indicating the IDs allocated to the new points in new_IDs
void print_tree_depths (std::ostream &outdev) const
unsigned int size ()

Private Types

typedef SearchTree< ShuffleTree
typedef Tree::circulator circulator
typedef Tree::const_circulator const_circulator

Private Member Functions

void _initialize (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner, const unsigned int max_size)
void _add_label (Point *point, unsigned int review_flag)
 add a label to a point as to the nature of review needed (includes adding it to list of points needing review) [doesn't affect other labels already set for the point]
void _set_label (Point *point, unsigned int review_flag)
 sets the label for the point to be exclusively this review flag (and adds it to list of points needing review if not already there)
void _deal_with_points_to_review ()
 for all entries of the _points_under_review[] vector, carry out the actions indicated by its review flag; the points are then removed from _points_under_review[] and their flags set to zero
void _remove_from_search_tree (Point *point_to_remove)
 carry out the search-tree related operations of point removal
void _insert_into_search_tree (Point *new_point)
 carry out the search-tree related operations of point insertion
void _point2shuffle (Point &, Shuffle &, unsigned int shift)
 takes a point and sets a shuffle with the given shift...
int _ID (const Point *) const
 returns the ID for the specified point...

Private Attributes

triplet< std::auto_ptr< Tree > > _trees
std::auto_ptr< MinHeap_heap
std::vector< Point_points
std::stack< Point * > _available_points
std::vector< Point * > _points_under_review
 points that are "under review" in some way
Coord2D _left_corner
 pieces needed for converting coordinates to integer
double _range
triplet< unsigned int > _shifts
triplet< unsigned int > _rel_shifts
unsigned int _cp_search_range

Static Private Attributes

static const unsigned int _nshift = 3
static const unsigned int _remove_heap_entry = 1
static const unsigned int _review_heap_entry = 2
static const unsigned int _review_neighbour = 4

Classes

class  Point
 class for representing all info needed about a point More...
class  Shuffle
 class that will take care of ordering of shuffles for us More...
class  triplet
 since sets of three objects will crop up repeatedly, useful to have a triplet class? More...

Detailed Description

concrete implementation for finding closest pairs in 2D -- will use Chan's (hopefully efficient) shuffle based structures

Definition at line 46 of file ClosestPair2D.hh.


Member Typedef Documentation

typedef SearchTree<Shuffle> fastjet::ClosestPair2D::Tree [private]

Definition at line 127 of file ClosestPair2D.hh.

typedef Tree::circulator fastjet::ClosestPair2D::circulator [private]

Definition at line 128 of file ClosestPair2D.hh.

typedef Tree::const_circulator fastjet::ClosestPair2D::const_circulator [private]

Definition at line 129 of file ClosestPair2D.hh.


Constructor & Destructor Documentation

fastjet::ClosestPair2D::ClosestPair2D ( const std::vector< Coord2D > &  positions,
const Coord2D left_corner,
const Coord2D right_corner 
) [inline]

constructor from a vector of 2D positions -- number of objects after insertion and deletion must never exceed positions.size(); objects are given IDs that correspond to their index in the vector of positions

Definition at line 52 of file ClosestPair2D.hh.

00053                                                                            {
00054     _initialize(positions, left_corner, right_corner, positions.size());
00055   };

fastjet::ClosestPair2D::ClosestPair2D ( const std::vector< Coord2D > &  positions,
const Coord2D left_corner,
const Coord2D right_corner,
const unsigned int  max_size 
) [inline]

constructor which allows structure to grow beyond positions.size(), up to max_size

Definition at line 59 of file ClosestPair2D.hh.

00061                                              {
00062     _initialize(positions, left_corner, right_corner, max_size);
00063   };


Member Function Documentation

void fastjet::ClosestPair2D::closest_pair ( unsigned int &  ID1,
unsigned int &  ID2,
double &  distance2 
) const [virtual]

provides the IDs of the closest pair as well as the distance between them

Implements fastjet::ClosestPair2DBase.

Definition at line 181 of file ClosestPair2D.cc.

References _heap, _ID(), and _points.

Referenced by fastjet::ClusterSequence::_CP2DChan_cluster(), and fastjet::ClusterSequence::_CP2DChan_limited_cluster().

00182                                                            {
00183   ID1 = _heap->minloc();
00184   ID2 = _ID(_points[ID1].neighbour);
00185   distance2 = _points[ID1].neighbour_dist2;
00186   if (ID1 > ID2) swap(ID1,ID2);
00187 }

void fastjet::ClosestPair2D::remove ( unsigned int  ID  )  [virtual]

removes the entry labelled by ID from the object;

Implements fastjet::ClosestPair2DBase.

Definition at line 213 of file ClosestPair2D.cc.

References _deal_with_points_to_review(), _points, and _remove_from_search_tree().

00213                                           {
00214 
00215   //cout << "While removing " << ID <<endl;
00216 
00217   Point * point_to_remove = & (_points[ID]);
00218 
00219   // remove this point from the search tree
00220   _remove_from_search_tree(point_to_remove);
00221 
00222   // the above statement labels certain points as needing "review" --
00223   // deal with them...
00224   _deal_with_points_to_review();
00225 }

unsigned int fastjet::ClosestPair2D::insert ( const Coord2D  )  [virtual]

inserts the position into the closest pair structure and returns the ID that has been allocated for the object.

Implements fastjet::ClosestPair2DBase.

Definition at line 345 of file ClosestPair2D.cc.

References _available_points, _deal_with_points_to_review(), _ID(), and _insert_into_search_tree().

00345                                                             {
00346 
00347   // get hold of a point
00348   assert(_available_points.size() > 0);
00349   Point * new_point = _available_points.top();
00350   _available_points.pop();
00351 
00352   // set the point's coordinate
00353   new_point->coord = new_coord;
00354   
00355   // now find it's neighbour in the search tree
00356   _insert_into_search_tree(new_point);
00357 
00358   // sort out other points that may have been affected by this, 
00359   // and/or for which the heap needs to be updated
00360   _deal_with_points_to_review();
00361 
00362   // 
00363   return _ID(new_point);
00364 }

unsigned int fastjet::ClosestPair2D::replace ( unsigned int  ID1,
unsigned int  ID2,
const Coord2D position 
) [virtual]

removes ID1 and ID2 and inserts position, returning the ID corresponding to position.

..

Reimplemented from fastjet::ClosestPair2DBase.

Definition at line 367 of file ClosestPair2D.cc.

References _available_points, _deal_with_points_to_review(), _ID(), _insert_into_search_tree(), _points, _remove_from_search_tree(), and fastjet::ClosestPair2D::Point::coord.

Referenced by fastjet::ClusterSequence::_CP2DChan_cluster().

00368                                                               {
00369   
00370   // deletion from tree...
00371   Point * point_to_remove = & (_points[ID1]);
00372   _remove_from_search_tree(point_to_remove);
00373 
00374   point_to_remove = & (_points[ID2]);
00375   _remove_from_search_tree(point_to_remove);
00376 
00377   // insertion into tree
00378   // get hold of a point
00379   Point * new_point = _available_points.top();
00380   _available_points.pop();
00381 
00382   // set the point's coordinate
00383   new_point->coord = position;
00384   
00385   // now find it's neighbour in the search tree
00386   _insert_into_search_tree(new_point);
00387 
00388   // the above statement labels certain points as needing "review" --
00389   // deal with them...
00390   _deal_with_points_to_review();
00391 
00392   //
00393   return _ID(new_point);
00394 
00395 }

void fastjet::ClosestPair2D::replace_many ( const std::vector< unsigned int > &  IDs_to_remove,
const std::vector< Coord2D > &  new_positions,
std::vector< unsigned int > &  new_IDs 
) [virtual]

replaces IDs_to_remove with points at the new_positions indicating the IDs allocated to the new points in new_IDs

Reimplemented from fastjet::ClosestPair2DBase.

Definition at line 399 of file ClosestPair2D.cc.

References _available_points, _deal_with_points_to_review(), _ID(), _insert_into_search_tree(), _points, and _remove_from_search_tree().

Referenced by fastjet::ClusterSequence::_CP2DChan_limited_cluster().

00402                                                      {
00403 
00404   // deletion from tree...
00405   for (unsigned int i = 0; i < IDs_to_remove.size(); i++) {
00406     _remove_from_search_tree(& (_points[IDs_to_remove[i]]));
00407   }
00408 
00409   // insertion into tree
00410   new_IDs.resize(0);
00411   for (unsigned int i = 0; i < new_positions.size(); i++) {
00412     Point * new_point = _available_points.top();
00413     _available_points.pop();
00414     // set the point's coordinate
00415     new_point->coord = new_positions[i];
00416     // now find it's neighbour in the search tree
00417     _insert_into_search_tree(new_point);
00418     // record the ID
00419     new_IDs.push_back(_ID(new_point));
00420   }
00421 
00422   // the above statement labels certain points as needing "review" --
00423   // deal with them...
00424   _deal_with_points_to_review();
00425 
00426 }

void fastjet::ClosestPair2D::print_tree_depths ( std::ostream &  outdev  )  const [inline]

Definition at line 89 of file ClosestPair2D.hh.

00089                                                            {
00090     outdev    << _trees[0]->max_depth() << " "
00091               << _trees[1]->max_depth() << " "
00092               << _trees[2]->max_depth() << "\n";
00093   };

unsigned int fastjet::ClosestPair2D::size (  )  [inline, virtual]

Implements fastjet::ClosestPair2DBase.

Definition at line 226 of file ClosestPair2D.hh.

References _available_points, and _points.

Referenced by _deal_with_points_to_review(), _insert_into_search_tree(), and _remove_from_search_tree().

00226                                         {
00227   return _points.size() - _available_points.size();
00228 }

void fastjet::ClosestPair2D::_initialize ( const std::vector< Coord2D > &  positions,
const Coord2D left_corner,
const Coord2D right_corner,
const unsigned int  max_size 
) [private]

Definition at line 78 of file ClosestPair2D.cc.

References _available_points, _cp_search_range, _heap, _left_corner, _nshift, _point2shuffle(), _points, _points_under_review, _range, _rel_shifts, _shifts, _trees, fastjet::ClosestPair2D::Point::circ, fastjet::ClosestPair2D::Point::distance2(), fastjet::ClosestPair2D::Point::neighbour, fastjet::ClosestPair2D::Point::neighbour_dist2, fastjet::twopow31, fastjet::Coord2D::x, and fastjet::Coord2D::y.

00081                                                     {
00082 
00083   unsigned int n_positions = positions.size();
00084   assert(max_size >= n_positions);
00085 
00086   //_points(positions.size())
00087 
00088   // allow the points array to grow to the following size
00089   _points.resize(max_size);
00090   // currently unused points are immediately made available on the
00091   // stack
00092   for (unsigned int i = n_positions; i < max_size; i++) {
00093     _available_points.push(&(_points[i]));
00094   }
00095 
00096   _left_corner = left_corner;
00097   _range       = max((right_corner.x - left_corner.x),
00098                      (right_corner.y - left_corner.y));
00099 
00100   // initialise the coordinates for the points and create the zero-shifted
00101   // shuffle array
00102   vector<Shuffle> shuffles(n_positions);
00103   for (unsigned int i = 0; i < n_positions; i++) {
00104     // set up the points
00105     _points[i].coord = positions[i];
00106     _points[i].neighbour_dist2 = numeric_limits<double>::max();
00107     _points[i].review_flag = 0;
00108 
00109     // create shuffle with 0 shift.
00110     _point2shuffle(_points[i], shuffles[i], 0);
00111   }
00112 
00113   // establish what our shifts will be
00114   for (unsigned ishift = 0; ishift < _nshift; ishift++) {
00115     // make sure we use double-precision for calculating the shifts
00116     // since otherwise we will hit integer overflow.
00117    _shifts[ishift] = static_cast<unsigned int>(((twopow31*1.0)*ishift)/_nshift);
00118     if (ishift == 0) {_rel_shifts[ishift] = 0;}
00119     else {_rel_shifts[ishift] = _shifts[ishift] - _shifts[ishift-1];}
00120   }
00121   //_shifts[0] = 0;
00122   //_shifts[1] = static_cast<unsigned int>((twopow31*1.0)/3.0);
00123   //_shifts[2] = static_cast<unsigned int>((twopow31*2.0)/3.0);
00124   //_rel_shifts[0] = 0;
00125   //_rel_shifts[1] = _shifts[1];
00126   //_rel_shifts[2] = _shifts[2]-_shifts[1];
00127 
00128   // and how we will search...
00129   //_cp_search_range = 49;
00130   _cp_search_range = 30;
00131   _points_under_review.reserve(_nshift * _cp_search_range);
00132 
00133   // now initialise the three trees
00134   for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00135 
00136     // shift the shuffles if need be.
00137     if (ishift > 0) {
00138       unsigned rel_shift = _rel_shifts[ishift];
00139       for (unsigned int i = 0; i < shuffles.size(); i++) {
00140         shuffles[i] += rel_shift; }
00141     }
00142 
00143     // sort the shuffles
00144     sort(shuffles.begin(), shuffles.end());
00145 
00146     // and create the search tree
00147     _trees[ishift] = auto_ptr<Tree>(new Tree(shuffles, max_size));
00148 
00149     // now we look for the closest-pair candidates on this tree
00150     circulator circ = _trees[ishift]->somewhere(), start=circ;
00151     // the actual range in which we search 
00152     unsigned int CP_range = min(_cp_search_range, n_positions-1);
00153     do {
00154       Point * this_point = circ->point;
00155       //cout << _ID(this_point) << " ";
00156       this_point->circ[ishift] = circ;
00157       // run over all points within _cp_search_range of this_point on tree
00158       circulator other = circ;
00159       for (unsigned i=0; i < CP_range; i++) {
00160         ++other;
00161         double dist2 = this_point->distance2(*other->point);
00162         if (dist2 < this_point->neighbour_dist2) {
00163           this_point->neighbour_dist2 = dist2;
00164           this_point->neighbour       = other->point;
00165         }
00166       }
00167     } while (++circ != start);
00168     //cout << endl<<endl;
00169   }
00170 
00171   // now initialise the heap object...
00172   vector<double> mindists2(n_positions);
00173   for (unsigned int i = 0; i < n_positions; i++) {
00174     mindists2[i] = _points[i].neighbour_dist2;}
00175   
00176   _heap = auto_ptr<MinHeap>(new MinHeap(mindists2, max_size));
00177 }

void fastjet::ClosestPair2D::_add_label ( Point point,
unsigned int  review_flag 
) [inline, private]

add a label to a point as to the nature of review needed (includes adding it to list of points needing review) [doesn't affect other labels already set for the point]

Definition at line 191 of file ClosestPair2D.cc.

References _points_under_review, and fastjet::ClosestPair2D::Point::review_flag.

Referenced by _insert_into_search_tree(), and _remove_from_search_tree().

00191                                                                              {
00192 
00193   // if it's not already under review, then put it on the list of
00194   // points needing review
00195   if (point->review_flag == 0) _points_under_review.push_back(point);
00196 
00197   // OR the point's current flag with the requested review flag
00198   point->review_flag |= review_flag;
00199 }

void fastjet::ClosestPair2D::_set_label ( Point point,
unsigned int  review_flag 
) [inline, private]

sets the label for the point to be exclusively this review flag (and adds it to list of points needing review if not already there)

Definition at line 202 of file ClosestPair2D.cc.

References _points_under_review, and fastjet::ClosestPair2D::Point::review_flag.

Referenced by _insert_into_search_tree(), and _remove_from_search_tree().

00202                                                                              {
00203 
00204   // if it's not already under review, then put it on the list of
00205   // points needing review
00206   if (point->review_flag == 0) _points_under_review.push_back(point);
00207 
00208   // SET the point's current flag to the requested review flag
00209   point->review_flag = review_flag;
00210 }

void fastjet::ClosestPair2D::_deal_with_points_to_review (  )  [private]

for all entries of the _points_under_review[] vector, carry out the actions indicated by its review flag; the points are then removed from _points_under_review[] and their flags set to zero

Definition at line 295 of file ClosestPair2D.cc.

References _cp_search_range, _heap, _ID(), _nshift, _points_under_review, _remove_heap_entry, _review_neighbour, and size().

Referenced by insert(), remove(), replace(), and replace_many().

00295                                                 {
00296 
00297   // the range in which we carry out searches for new neighbours on
00298   // the search tree
00299   unsigned int CP_range = min(_cp_search_range, size()-1);
00300 
00301   // now deal with the points that are "under review" in some way
00302   // (have lost their neighbour, or need their heap entry updating)
00303   while(_points_under_review.size() > 0) {
00304     // get the point to be considered
00305     Point * this_point = _points_under_review.back();
00306     // remove it from the list
00307     _points_under_review.pop_back();  
00308     
00309     if (this_point->review_flag & _remove_heap_entry) {
00310       // make sure no other flags are on (it wouldn't be consistent?)
00311       assert(!(this_point->review_flag ^ _remove_heap_entry));
00312       _heap->remove(_ID(this_point));
00313     } 
00314     // check to see if the _review_neighbour flag is on
00315     else {
00316       if (this_point->review_flag & _review_neighbour) {
00317         this_point->neighbour_dist2 = numeric_limits<double>::max();
00318         // among all three shifts
00319         for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00320           circulator other = this_point->circ[ishift];
00321           // among points within CP_range
00322           for (unsigned i=0; i < CP_range; i++) {
00323             ++other;
00324             double dist2 = this_point->distance2(*other->point);
00325             if (dist2 < this_point->neighbour_dist2) {
00326               this_point->neighbour_dist2 = dist2;
00327               this_point->neighbour       = other->point;
00328             }
00329           }
00330         }
00331       }
00332 
00333       // for any non-zero review flag we'll have to update the heap
00334       _heap->update(_ID(this_point), this_point->neighbour_dist2);
00335     }
00336 
00337     // "delabel" the point
00338     this_point->review_flag = 0; 
00339 
00340   }
00341 
00342 }

void fastjet::ClosestPair2D::_remove_from_search_tree ( Point point_to_remove  )  [private]

carry out the search-tree related operations of point removal

Definition at line 229 of file ClosestPair2D.cc.

References _add_label(), _available_points, _cp_search_range, _nshift, _remove_heap_entry, _review_heap_entry, _review_neighbour, _set_label(), _trees, fastjet::ClosestPair2D::Point::circ, fastjet::ClosestPair2D::Point::neighbour, and size().

Referenced by remove(), replace(), and replace_many().

00229                                                                     {
00230 
00231   // add this point to the list of "available" points (this is
00232   // relevant also from the point of view of determining the range
00233   // over which we circulate).
00234   _available_points.push(point_to_remove);
00235 
00236   // label it so that it goes from the heap
00237   _set_label(point_to_remove, _remove_heap_entry);
00238 
00239   // establish the range over which we search (a) for points that have
00240   // acquired a new neighbour and (b) for points which had ID as their
00241   // neighbour;
00242   
00243   unsigned int CP_range = min(_cp_search_range, size()-1);
00244 
00245   // then, for each shift
00246   for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00247     //cout << "   ishift = " << ishift <<endl;
00248     // get the circulator for the point we'll remove and its successor
00249     circulator removed_circ = point_to_remove->circ[ishift];
00250     circulator right_end = removed_circ.next();
00251     // remove the point
00252     _trees[ishift]->remove(removed_circ);
00253     
00254     // next find the point CP_range points to the left
00255     circulator left_end  = right_end, orig_right_end = right_end;
00256     for (unsigned int i = 0; i < CP_range; i++) {left_end--;}
00257 
00258     if (size()-1 < _cp_search_range) {
00259       // we have a smaller range now than before -- but when seeing who 
00260       // could have had ID as a neighbour, we still need to use the old
00261       // range for seeing how far back we search (but new separation between
00262       // points). [cf CCN28-42]
00263       left_end--; right_end--;
00264     }
00265 
00266     // and then for each left-end point: establish if the removed
00267     // point was its neighbour [in which case a new neighbour must be
00268     // found], otherwise see if the right-end point is a closer neighbour
00269     do {
00270       Point * left_point = left_end->point;
00271 
00272       //cout << "    visited " << setw(3)<<_ID(left_point)<<" (its neighbour was "<<    setw(3)<< _ID(left_point->neighbour)<<")"<<endl;
00273 
00274       if (left_point->neighbour == point_to_remove) {
00275         // we'll deal with it later...
00276         _add_label(left_point, _review_neighbour);
00277       } else {
00278         // check to see if right point has become its closest neighbour
00279         double dist2 = left_point->distance2(*right_end->point);
00280         if (dist2 < left_point->neighbour_dist2) {
00281           left_point->neighbour = right_end->point;
00282           left_point->neighbour_dist2 = dist2;
00283           // NB: (LESSER) REVIEW NEEDED HERE TOO...
00284           _add_label(left_point, _review_heap_entry);
00285         }
00286       }
00287       ++right_end;
00288     } while (++left_end != orig_right_end);
00289   } // ishift...
00290 
00291 }

void fastjet::ClosestPair2D::_insert_into_search_tree ( Point new_point  )  [private]

carry out the search-tree related operations of point insertion

Definition at line 430 of file ClosestPair2D.cc.

References _add_label(), _cp_search_range, _nshift, _point2shuffle(), _review_heap_entry, _review_neighbour, _set_label(), _shifts, _trees, fastjet::ClosestPair2D::Point::distance2(), fastjet::ClosestPair2D::Point::neighbour, fastjet::ClosestPair2D::Point::neighbour_dist2, and size().

Referenced by insert(), replace(), and replace_many().

00430                                                               {
00431 
00432   // this point will have to have it's heap entry reviewed...
00433   _set_label(new_point, _review_heap_entry);
00434 
00435   // set the current distance to "infinity"
00436   new_point->neighbour_dist2 = numeric_limits<double>::max();
00437   
00438   // establish how far we will be searching;
00439   unsigned int CP_range = min(_cp_search_range, size()-1);
00440 
00441   for (unsigned ishift = 0; ishift < _nshift; ishift++) {
00442     // create the shuffle
00443     Shuffle new_shuffle;
00444     _point2shuffle(*new_point, new_shuffle, _shifts[ishift]);
00445     
00446     // insert it into the tree
00447     circulator new_circ = _trees[ishift]->insert(new_shuffle);
00448     new_point->circ[ishift] = new_circ;
00449 
00450     // now get hold of the right and left edges of the region we will be
00451     // looking at (cf CCN28-43)
00452     circulator right_edge = new_circ; right_edge++;
00453     circulator left_edge  = new_circ;
00454     for (unsigned int i = 0; i < CP_range; i++) {left_edge--;}
00455 
00456     // now 
00457     do {
00458       Point * left_point  = left_edge->point;
00459       Point * right_point = right_edge->point;
00460 
00461       // see if the new point is closer to the left-edge than the latter's
00462       // current neighbour
00463       double new_dist2 = left_point->distance2(*new_point);
00464       if (new_dist2 < left_point->neighbour_dist2) {
00465         left_point->neighbour_dist2 = new_dist2;
00466         left_point->neighbour       = new_point;
00467         _add_label(left_point, _review_heap_entry);
00468       }
00469 
00470       // see if the right-point is closer to the new point than it's current
00471       // neighbour
00472       new_dist2 = new_point->distance2(*right_point);
00473       if (new_dist2 < new_point->neighbour_dist2) {
00474         new_point->neighbour_dist2 = new_dist2;
00475         new_point->neighbour = right_point;
00476       }
00477 
00478       // if the right-edge point was the left-edge's neighbour, then
00479       // then it's just gone off-radar and the left-point will need to
00480       // have its neighbour recalculated [actually, this is overdoing
00481       // it a little, since right point may be an less "distant"
00482       // (circulator distance) in one of the other shifts -- but not
00483       // sure how to deal with this...]
00484       if (left_point->neighbour == right_point) {
00485         _add_label(left_point, _review_neighbour);
00486       }
00487 
00488       // shift the left and right edges until left edge hits new_circ
00489       right_edge++;
00490     } while (++left_edge != new_circ);
00491   }
00492 }

void fastjet::ClosestPair2D::_point2shuffle ( Point ,
Shuffle ,
unsigned int  shift 
) [private]

takes a point and sets a shuffle with the given shift...

Definition at line 46 of file ClosestPair2D.cc.

References _left_corner, _range, fastjet::ClosestPair2D::Point::coord, fastjet::ClosestPair2D::Shuffle::point, fastjet::twopow31, fastjet::ClosestPair2D::Shuffle::x, fastjet::Coord2D::x, fastjet::ClosestPair2D::Shuffle::y, and fastjet::Coord2D::y.

Referenced by _initialize(), and _insert_into_search_tree().

00047                                                       {
00048   
00049   Coord2D renorm_point = (point.coord - _left_corner)/_range;
00050   // make sure the point is sensible
00051   //cerr << point.coord.x <<" "<<point.coord.y<<endl;
00052   assert(renorm_point.x >=0);
00053   assert(renorm_point.x <=1);
00054   assert(renorm_point.y >=0);
00055   assert(renorm_point.y <=1);
00056   
00057   shuffle.x = static_cast<unsigned int>(twopow31 * renorm_point.x) + shift;
00058   shuffle.y = static_cast<unsigned int>(twopow31 * renorm_point.y) + shift;
00059   shuffle.point = &point;
00060 }

int fastjet::ClosestPair2D::_ID ( const Point  )  const [inline, private]

returns the ID for the specified point...

Definition at line 220 of file ClosestPair2D.hh.

References _points.

Referenced by _deal_with_points_to_review(), closest_pair(), insert(), replace(), and replace_many().

00220                                                        {
00221   return point - &(_points[0]);
00222 }


Member Data Documentation

const unsigned int fastjet::ClosestPair2D::_nshift = 3 [static, private]

Definition at line 103 of file ClosestPair2D.hh.

Referenced by _deal_with_points_to_review(), _initialize(), _insert_into_search_tree(), and _remove_from_search_tree().

triplet<std::auto_ptr<Tree> > fastjet::ClosestPair2D::_trees [private]

Definition at line 132 of file ClosestPair2D.hh.

Referenced by _initialize(), _insert_into_search_tree(), and _remove_from_search_tree().

std::auto_ptr<MinHeap> fastjet::ClosestPair2D::_heap [private]

Definition at line 133 of file ClosestPair2D.hh.

Referenced by _deal_with_points_to_review(), _initialize(), and closest_pair().

std::vector<Point> fastjet::ClosestPair2D::_points [private]

Definition at line 134 of file ClosestPair2D.hh.

Referenced by _ID(), _initialize(), closest_pair(), remove(), replace(), replace_many(), and size().

std::stack<Point *> fastjet::ClosestPair2D::_available_points [private]

Definition at line 135 of file ClosestPair2D.hh.

Referenced by _initialize(), _remove_from_search_tree(), insert(), replace(), replace_many(), and size().

std::vector<Point *> fastjet::ClosestPair2D::_points_under_review [private]

points that are "under review" in some way

Definition at line 138 of file ClosestPair2D.hh.

Referenced by _add_label(), _deal_with_points_to_review(), _initialize(), and _set_label().

const unsigned int fastjet::ClosestPair2D::_remove_heap_entry = 1 [static, private]

Definition at line 141 of file ClosestPair2D.hh.

Referenced by _deal_with_points_to_review(), and _remove_from_search_tree().

const unsigned int fastjet::ClosestPair2D::_review_heap_entry = 2 [static, private]

Definition at line 142 of file ClosestPair2D.hh.

Referenced by _insert_into_search_tree(), and _remove_from_search_tree().

const unsigned int fastjet::ClosestPair2D::_review_neighbour = 4 [static, private]

Definition at line 143 of file ClosestPair2D.hh.

Referenced by _deal_with_points_to_review(), _insert_into_search_tree(), and _remove_from_search_tree().

Coord2D fastjet::ClosestPair2D::_left_corner [private]

pieces needed for converting coordinates to integer

Definition at line 171 of file ClosestPair2D.hh.

Referenced by _initialize(), and _point2shuffle().

double fastjet::ClosestPair2D::_range [private]

Definition at line 172 of file ClosestPair2D.hh.

Referenced by _initialize(), and _point2shuffle().

triplet<unsigned int> fastjet::ClosestPair2D::_shifts [private]

Definition at line 176 of file ClosestPair2D.hh.

Referenced by _initialize(), and _insert_into_search_tree().

triplet<unsigned int> fastjet::ClosestPair2D::_rel_shifts [private]

Definition at line 177 of file ClosestPair2D.hh.

Referenced by _initialize().

unsigned int fastjet::ClosestPair2D::_cp_search_range [private]

Definition at line 179 of file ClosestPair2D.hh.

Referenced by _deal_with_points_to_review(), _initialize(), _insert_into_search_tree(), and _remove_from_search_tree().


The documentation for this class was generated from the following files:
Generated on Tue Dec 18 17:05:53 2007 for fastjet by  doxygen 1.5.2