#include <ClosestPair2D.hh>
Inheritance diagram for fastjet::ClosestPair2D:
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< Shuffle > | Tree |
| 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... | |
Definition at line 46 of file ClosestPair2D.hh.
|
|
Definition at line 128 of file ClosestPair2D.hh. |
|
|
Definition at line 129 of file ClosestPair2D.hh. |
|
|
Definition at line 127 of file ClosestPair2D.hh. |
|
||||||||||||||||
|
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 };
|
|
||||||||||||||||||||
|
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 };
|
|
||||||||||||
|
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 192 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(). 00192 {
00193
00194 // if it's not already under review, then put it on the list of
00195 // points needing review
00196 if (point->review_flag == 0) _points_under_review.push_back(point);
00197
00198 // OR the point's current flag with the requested review flag
00199 point->review_flag |= review_flag;
00200 }
|
|
|
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 296 of file ClosestPair2D.cc. References _cp_search_range, _heap, _ID(), _nshift, _points_under_review, _remove_heap_entry, _review_neighbour, fastjet::ClosestPair2D::Point::circ, fastjet::ClosestPair2D::Point::distance2(), fastjet::ClosestPair2D::Point::neighbour, fastjet::ClosestPair2D::Point::neighbour_dist2, fastjet::ClosestPair2D::Point::review_flag, and size(). Referenced by insert(), remove(), replace(), and replace_many(). 00296 {
00297
00298 // the range in which we carry out searches for new neighbours on
00299 // the search tree
00300 unsigned int CP_range = min(_cp_search_range, size()-1);
00301
00302 // now deal with the points that are "under review" in some way
00303 // (have lost their neighbour, or need their heap entry updating)
00304 while(_points_under_review.size() > 0) {
00305 // get the point to be considered
00306 Point * this_point = _points_under_review.back();
00307 // remove it from the list
00308 _points_under_review.pop_back();
00309
00310 if (this_point->review_flag & _remove_heap_entry) {
00311 // make sure no other flags are on (it wouldn't be consistent?)
00312 assert(!(this_point->review_flag ^ _remove_heap_entry));
00313 _heap->remove(_ID(this_point));
00314 }
00315 // check to see if the _review_neighbour flag is on
00316 else {
00317 if (this_point->review_flag & _review_neighbour) {
00318 this_point->neighbour_dist2 = numeric_limits<double>::max();
00319 // among all three shifts
00320 for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00321 circulator other = this_point->circ[ishift];
00322 // among points within CP_range
00323 for (unsigned i=0; i < CP_range; i++) {
00324 ++other;
00325 double dist2 = this_point->distance2(*other->point);
00326 if (dist2 < this_point->neighbour_dist2) {
00327 this_point->neighbour_dist2 = dist2;
00328 this_point->neighbour = other->point;
00329 }
00330 }
00331 }
00332 }
00333
00334 // for any non-zero review flag we'll have to update the heap
00335 _heap->update(_ID(this_point), this_point->neighbour_dist2);
00336 }
00337
00338 // "delabel" the point
00339 this_point->review_flag = 0;
00340
00341 }
00342
00343 }
|
|
|
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 }
|
|
||||||||||||||||||||
|
Definition at line 79 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. 00082 {
00083
00084 unsigned int n_positions = positions.size();
00085 assert(max_size >= n_positions);
00086
00087 //_points(positions.size())
00088
00089 // allow the points array to grow to the following size
00090 _points.resize(max_size);
00091 // currently unused points are immediately made available on the
00092 // stack
00093 for (unsigned int i = n_positions; i < max_size; i++) {
00094 _available_points.push(&(_points[i]));
00095 }
00096
00097 _left_corner = left_corner;
00098 _range = max((right_corner.x - left_corner.x),
00099 (right_corner.y - left_corner.y));
00100
00101 // initialise the coordinates for the points and create the zero-shifted
00102 // shuffle array
00103 vector<Shuffle> shuffles(n_positions);
00104 for (unsigned int i = 0; i < n_positions; i++) {
00105 // set up the points
00106 _points[i].coord = positions[i];
00107 _points[i].neighbour_dist2 = numeric_limits<double>::max();
00108 _points[i].review_flag = 0;
00109
00110 // create shuffle with 0 shift.
00111 _point2shuffle(_points[i], shuffles[i], 0);
00112 }
00113
00114 // establish what our shifts will be
00115 for (unsigned ishift = 0; ishift < _nshift; ishift++) {
00116 // make sure we use double-precision for calculating the shifts
00117 // since otherwise we will hit integer overflow.
00118 _shifts[ishift] = static_cast<unsigned int>(((twopow31*1.0)*ishift)/_nshift);
00119 if (ishift == 0) {_rel_shifts[ishift] = 0;}
00120 else {_rel_shifts[ishift] = _shifts[ishift] - _shifts[ishift-1];}
00121 }
00122 //_shifts[0] = 0;
00123 //_shifts[1] = static_cast<unsigned int>((twopow31*1.0)/3.0);
00124 //_shifts[2] = static_cast<unsigned int>((twopow31*2.0)/3.0);
00125 //_rel_shifts[0] = 0;
00126 //_rel_shifts[1] = _shifts[1];
00127 //_rel_shifts[2] = _shifts[2]-_shifts[1];
00128
00129 // and how we will search...
00130 //_cp_search_range = 49;
00131 _cp_search_range = 30;
00132 _points_under_review.reserve(_nshift * _cp_search_range);
00133
00134 // now initialise the three trees
00135 for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00136
00137 // shift the shuffles if need be.
00138 if (ishift > 0) {
00139 unsigned rel_shift = _rel_shifts[ishift];
00140 for (unsigned int i = 0; i < shuffles.size(); i++) {
00141 shuffles[i] += rel_shift; }
00142 }
00143
00144 // sort the shuffles
00145 sort(shuffles.begin(), shuffles.end());
00146
00147 // and create the search tree
00148 _trees[ishift] = auto_ptr<Tree>(new Tree(shuffles, max_size));
00149
00150 // now we look for the closest-pair candidates on this tree
00151 circulator circ = _trees[ishift]->somewhere(), start=circ;
00152 // the actual range in which we search
00153 unsigned int CP_range = min(_cp_search_range, n_positions-1);
00154 do {
00155 Point * this_point = circ->point;
00156 //cout << _ID(this_point) << " ";
00157 this_point->circ[ishift] = circ;
00158 // run over all points within _cp_search_range of this_point on tree
00159 circulator other = circ;
00160 for (unsigned i=0; i < CP_range; i++) {
00161 ++other;
00162 double dist2 = this_point->distance2(*other->point);
00163 if (dist2 < this_point->neighbour_dist2) {
00164 this_point->neighbour_dist2 = dist2;
00165 this_point->neighbour = other->point;
00166 }
00167 }
00168 } while (++circ != start);
00169 //cout << endl<<endl;
00170 }
00171
00172 // now initialise the heap object...
00173 vector<double> mindists2(n_positions);
00174 for (unsigned int i = 0; i < n_positions; i++) {
00175 mindists2[i] = _points[i].neighbour_dist2;}
00176
00177 _heap = auto_ptr<MinHeap>(new MinHeap(mindists2, max_size));
00178 }
|
|
|
carry out the search-tree related operations of point insertion
Definition at line 431 of file ClosestPair2D.cc. References _add_label(), _cp_search_range, _nshift, _point2shuffle(), _review_heap_entry, _review_neighbour, _set_label(), _shifts, _trees, fastjet::ClosestPair2D::Point::circ, fastjet::ClosestPair2D::Point::distance2(), fastjet::ClosestPair2D::Point::neighbour, fastjet::ClosestPair2D::Point::neighbour_dist2, and size(). Referenced by insert(), replace(), and replace_many(). 00431 {
00432
00433 // this point will have to have it's heap entry reviewed...
00434 _set_label(new_point, _review_heap_entry);
00435
00436 // set the current distance to "infinity"
00437 new_point->neighbour_dist2 = numeric_limits<double>::max();
00438
00439 // establish how far we will be searching;
00440 unsigned int CP_range = min(_cp_search_range, size()-1);
00441
00442 for (unsigned ishift = 0; ishift < _nshift; ishift++) {
00443 // create the shuffle
00444 Shuffle new_shuffle;
00445 _point2shuffle(*new_point, new_shuffle, _shifts[ishift]);
00446
00447 // insert it into the tree
00448 circulator new_circ = _trees[ishift]->insert(new_shuffle);
00449 new_point->circ[ishift] = new_circ;
00450
00451 // now get hold of the right and left edges of the region we will be
00452 // looking at (cf CCN28-43)
00453 circulator right_edge = new_circ; right_edge++;
00454 circulator left_edge = new_circ;
00455 for (unsigned int i = 0; i < CP_range; i++) {left_edge--;}
00456
00457 // now
00458 do {
00459 Point * left_point = left_edge->point;
00460 Point * right_point = right_edge->point;
00461
00462 // see if the new point is closer to the left-edge than the latter's
00463 // current neighbour
00464 double new_dist2 = left_point->distance2(*new_point);
00465 if (new_dist2 < left_point->neighbour_dist2) {
00466 left_point->neighbour_dist2 = new_dist2;
00467 left_point->neighbour = new_point;
00468 _add_label(left_point, _review_heap_entry);
00469 }
00470
00471 // see if the right-point is closer to the new point than it's current
00472 // neighbour
00473 new_dist2 = new_point->distance2(*right_point);
00474 if (new_dist2 < new_point->neighbour_dist2) {
00475 new_point->neighbour_dist2 = new_dist2;
00476 new_point->neighbour = right_point;
00477 }
00478
00479 // if the right-edge point was the left-edge's neighbour, then
00480 // then it's just gone off-radar and the left-point will need to
00481 // have its neighbour recalculated [actually, this is overdoing
00482 // it a little, since right point may be an less "distant"
00483 // (circulator distance) in one of the other shifts -- but not
00484 // sure how to deal with this...]
00485 if (left_point->neighbour == right_point) {
00486 _add_label(left_point, _review_neighbour);
00487 }
00488
00489 // shift the left and right edges until left edge hits new_circ
00490 right_edge++;
00491 } while (++left_edge != new_circ);
00492 }
00493 }
|
|
||||||||||||||||
|
takes a point and sets a shuffle with the given shift...
Definition at line 47 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(). 00048 {
00049
00050 Coord2D renorm_point = (point.coord - _left_corner)/_range;
00051 // make sure the point is sensible
00052 //cerr << point.coord.x <<" "<<point.coord.y<<endl;
00053 assert(renorm_point.x >=0);
00054 assert(renorm_point.x <=1);
00055 assert(renorm_point.y >=0);
00056 assert(renorm_point.y <=1);
00057
00058 shuffle.x = static_cast<unsigned int>(twopow31 * renorm_point.x) + shift;
00059 shuffle.y = static_cast<unsigned int>(twopow31 * renorm_point.y) + shift;
00060 shuffle.point = &point;
00061 }
|
|
|
carry out the search-tree related operations of point removal
Definition at line 230 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::distance2(), fastjet::ClosestPair2D::Point::neighbour, fastjet::ClosestPair2D::Point::neighbour_dist2, and size(). Referenced by remove(), replace(), and replace_many(). 00230 {
00231
00232 // add this point to the list of "available" points (this is
00233 // relevant also from the point of view of determining the range
00234 // over which we circulate).
00235 _available_points.push(point_to_remove);
00236
00237 // label it so that it goes from the heap
00238 _set_label(point_to_remove, _remove_heap_entry);
00239
00240 // establish the range over which we search (a) for points that have
00241 // acquired a new neighbour and (b) for points which had ID as their
00242 // neighbour;
00243
00244 unsigned int CP_range = min(_cp_search_range, size()-1);
00245
00246 // then, for each shift
00247 for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
00248 //cout << " ishift = " << ishift <<endl;
00249 // get the circulator for the point we'll remove and its successor
00250 circulator removed_circ = point_to_remove->circ[ishift];
00251 circulator right_end = removed_circ.next();
00252 // remove the point
00253 _trees[ishift]->remove(removed_circ);
00254
00255 // next find the point CP_range points to the left
00256 circulator left_end = right_end, orig_right_end = right_end;
00257 for (unsigned int i = 0; i < CP_range; i++) {left_end--;}
00258
00259 if (size()-1 < _cp_search_range) {
00260 // we have a smaller range now than before -- but when seeing who
00261 // could have had ID as a neighbour, we still need to use the old
00262 // range for seeing how far back we search (but new separation between
00263 // points). [cf CCN28-42]
00264 left_end--; right_end--;
00265 }
00266
00267 // and then for each left-end point: establish if the removed
00268 // point was its neighbour [in which case a new neighbour must be
00269 // found], otherwise see if the right-end point is a closer neighbour
00270 do {
00271 Point * left_point = left_end->point;
00272
00273 //cout << " visited " << setw(3)<<_ID(left_point)<<" (its neighbour was "<< setw(3)<< _ID(left_point->neighbour)<<")"<<endl;
00274
00275 if (left_point->neighbour == point_to_remove) {
00276 // we'll deal with it later...
00277 _add_label(left_point, _review_neighbour);
00278 } else {
00279 // check to see if right point has become its closest neighbour
00280 double dist2 = left_point->distance2(*right_end->point);
00281 if (dist2 < left_point->neighbour_dist2) {
00282 left_point->neighbour = right_end->point;
00283 left_point->neighbour_dist2 = dist2;
00284 // NB: (LESSER) REVIEW NEEDED HERE TOO...
00285 _add_label(left_point, _review_heap_entry);
00286 }
00287 }
00288 ++right_end;
00289 } while (++left_end != orig_right_end);
00290 } // ishift...
00291
00292 }
|
|
||||||||||||
|
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 203 of file ClosestPair2D.cc. References _points_under_review. Referenced by _insert_into_search_tree(), and _remove_from_search_tree(). 00203 {
00204
00205 // if it's not already under review, then put it on the list of
00206 // points needing review
00207 if (point->review_flag == 0) _points_under_review.push_back(point);
00208
00209 // SET the point's current flag to the requested review flag
00210 point->review_flag = review_flag;
00211 }
|
|
||||||||||||||||
|
provides the IDs of the closest pair as well as the distance between them
Implements fastjet::ClosestPair2DBase. Definition at line 182 of file ClosestPair2D.cc. References _heap, _ID(), and _points. Referenced by fastjet::ClusterSequence::_CP2DChan_cluster(), and fastjet::ClusterSequence::_CP2DChan_limited_cluster(). 00183 {
00184 ID1 = _heap->minloc();
00185 ID2 = _ID(_points[ID1].neighbour);
00186 distance2 = _points[ID1].neighbour_dist2;
00187 if (ID1 > ID2) swap(ID1,ID2);
00188 }
|
|
|
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 346 of file ClosestPair2D.cc. References _available_points, _deal_with_points_to_review(), _ID(), _insert_into_search_tree(), and fastjet::ClosestPair2D::Point::coord. 00346 {
00347
00348 // get hold of a point
00349 assert(_available_points.size() > 0);
00350 Point * new_point = _available_points.top();
00351 _available_points.pop();
00352
00353 // set the point's coordinate
00354 new_point->coord = new_coord;
00355
00356 // now find it's neighbour in the search tree
00357 _insert_into_search_tree(new_point);
00358
00359 // sort out other points that may have been affected by this,
00360 // and/or for which the heap needs to be updated
00361 _deal_with_points_to_review();
00362
00363 //
00364 return _ID(new_point);
00365 }
|
|
|
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 };
|
|
|
removes the entry labelled by ID from the object;
Implements fastjet::ClosestPair2DBase. Definition at line 214 of file ClosestPair2D.cc. References _deal_with_points_to_review(), _points, and _remove_from_search_tree(). 00214 {
00215
00216 //cout << "While removing " << ID <<endl;
00217
00218 Point * point_to_remove = & (_points[ID]);
00219
00220 // remove this point from the search tree
00221 _remove_from_search_tree(point_to_remove);
00222
00223 // the above statement labels certain points as needing "review" --
00224 // deal with them...
00225 _deal_with_points_to_review();
00226 }
|
|
||||||||||||||||
|
removes ID1 and ID2 and inserts position, returning the ID corresponding to position. .. Reimplemented from fastjet::ClosestPair2DBase. Definition at line 368 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(). 00369 {
00370
00371 // deletion from tree...
00372 Point * point_to_remove = & (_points[ID1]);
00373 _remove_from_search_tree(point_to_remove);
00374
00375 point_to_remove = & (_points[ID2]);
00376 _remove_from_search_tree(point_to_remove);
00377
00378 // insertion into tree
00379 // get hold of a point
00380 Point * new_point = _available_points.top();
00381 _available_points.pop();
00382
00383 // set the point's coordinate
00384 new_point->coord = position;
00385
00386 // now find it's neighbour in the search tree
00387 _insert_into_search_tree(new_point);
00388
00389 // the above statement labels certain points as needing "review" --
00390 // deal with them...
00391 _deal_with_points_to_review();
00392
00393 //
00394 return _ID(new_point);
00395
00396 }
|
|
||||||||||||||||
|
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 400 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_limited_cluster(). 00403 {
00404
00405 // deletion from tree...
00406 for (unsigned int i = 0; i < IDs_to_remove.size(); i++) {
00407 _remove_from_search_tree(& (_points[IDs_to_remove[i]]));
00408 }
00409
00410 // insertion into tree
00411 new_IDs.resize(0);
00412 for (unsigned int i = 0; i < new_positions.size(); i++) {
00413 Point * new_point = _available_points.top();
00414 _available_points.pop();
00415 // set the point's coordinate
00416 new_point->coord = new_positions[i];
00417 // now find it's neighbour in the search tree
00418 _insert_into_search_tree(new_point);
00419 // record the ID
00420 new_IDs.push_back(_ID(new_point));
00421 }
00422
00423 // the above statement labels certain points as needing "review" --
00424 // deal with them...
00425 _deal_with_points_to_review();
00426
00427 }
|
|
|
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 }
|
|
|
Definition at line 135 of file ClosestPair2D.hh. Referenced by _initialize(), _remove_from_search_tree(), insert(), replace(), replace_many(), and size(). |
|
|
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(). |
|
|
Definition at line 133 of file ClosestPair2D.hh. Referenced by _deal_with_points_to_review(), _initialize(), and closest_pair(). |
|
|
pieces needed for converting coordinates to integer
Definition at line 171 of file ClosestPair2D.hh. Referenced by _initialize(), and _point2shuffle(). |
|
|
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(). |
|
|
Definition at line 134 of file ClosestPair2D.hh. Referenced by _ID(), _initialize(), closest_pair(), remove(), replace(), replace_many(), and size(). |
|
|
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(). |
|
|
Definition at line 172 of file ClosestPair2D.hh. Referenced by _initialize(), and _point2shuffle(). |
|
|
Definition at line 177 of file ClosestPair2D.hh. Referenced by _initialize(). |
|
|
Definition at line 141 of file ClosestPair2D.hh. Referenced by _deal_with_points_to_review(), and _remove_from_search_tree(). |
|
|
Definition at line 142 of file ClosestPair2D.hh. Referenced by _insert_into_search_tree(), and _remove_from_search_tree(). |
|
|
Definition at line 143 of file ClosestPair2D.hh. Referenced by _deal_with_points_to_review(), _insert_into_search_tree(), and _remove_from_search_tree(). |
|
|
Definition at line 176 of file ClosestPair2D.hh. Referenced by _initialize(), and _insert_into_search_tree(). |
|
|
Definition at line 132 of file ClosestPair2D.hh. Referenced by _initialize(), _insert_into_search_tree(), and _remove_from_search_tree(). |
1.4.2