LSST Applications  21.0.0-172-gfb10e10a+18fedfabac,22.0.0+297cba6710,22.0.0+80564b0ff1,22.0.0+8d77f4f51a,22.0.0+a28f4c53b1,22.0.0+dcf3732eb2,22.0.1-1-g7d6de66+2a20fdde0d,22.0.1-1-g8e32f31+297cba6710,22.0.1-1-geca5380+7fa3b7d9b6,22.0.1-12-g44dc1dc+2a20fdde0d,22.0.1-15-g6a90155+515f58c32b,22.0.1-16-g9282f48+790f5f2caa,22.0.1-2-g92698f7+dcf3732eb2,22.0.1-2-ga9b0f51+7fa3b7d9b6,22.0.1-2-gd1925c9+bf4f0e694f,22.0.1-24-g1ad7a390+a9625a72a8,22.0.1-25-g5bf6245+3ad8ecd50b,22.0.1-25-gb120d7b+8b5510f75f,22.0.1-27-g97737f7+2a20fdde0d,22.0.1-32-gf62ce7b1+aa4237961e,22.0.1-4-g0b3f228+2a20fdde0d,22.0.1-4-g243d05b+871c1b8305,22.0.1-4-g3a563be+32dcf1063f,22.0.1-4-g44f2e3d+9e4ab0f4fa,22.0.1-42-gca6935d93+ba5e5ca3eb,22.0.1-5-g15c806e+85460ae5f3,22.0.1-5-g58711c4+611d128589,22.0.1-5-g75bb458+99c117b92f,22.0.1-6-g1c63a23+7fa3b7d9b6,22.0.1-6-g50866e6+84ff5a128b,22.0.1-6-g8d3140d+720564cf76,22.0.1-6-gd805d02+cc5644f571,22.0.1-8-ge5750ce+85460ae5f3,master-g6e05de7fdc+babf819c66,master-g99da0e417a+8d77f4f51a,w.2021.48
LSST Data Management Base Package
Classes | Public Member Functions | Public Attributes | List of all members
lsst::jointcal::FastFinder Class Reference

This is an auxillary class for matching objects from starlists. More...

#include <FastFinder.h>

Classes

class  Iterator
 Iterator meant to traverse objects within some limiting distance. More...
 

Public Member Functions

 FastFinder (const BaseStarList &list, const unsigned nXSlice=100)
 Constructor. More...
 
std::shared_ptr< const BaseStarfindClosest (const Point &where, const double maxDist, bool(*SkipIt)(const BaseStar &)=nullptr) const
 Find the closest with some rejection capability. More...
 
std::shared_ptr< const BaseStarsecondClosest (const Point &where, const double maxDist, std::shared_ptr< const BaseStar > &closest, bool(*SkipIt)(const BaseStar &)=nullptr) const
 
void print (std::ostream &out) const
 mostly for debugging More...
 
Iterator beginScan (const Point &where, double maxDist) const
 
void findRangeInSlice (const int iSlice, const double yStart, const double yEnd, pstar &start, pstar &end) const
 
pstar locateYStart (pstar begin, pstar end, double yVal) const
 
pstar locateYEnd (pstar begin, pstar end, double yVal) const
 

Public Attributes

decltype(stars) typedef ::value_type stars_element
 
decltype(stars) typedef ::const_iterator pstar
 
const BaseStarList baselist
 
unsigned count
 
std::vector< std::shared_ptr< const BaseStar > > stars
 
unsigned nslice
 
std::vector< unsigned > index
 
double xmin
 
double xmax
 
double xstep
 

Detailed Description

This is an auxillary class for matching objects from starlists.

It allows to locate rapidly the closest objects from a given position. The very simple strategy is to sort objects according to 1 coordinate x, and to build an index that allows to select the objects with the x coordinate inside an interval. Then every slice in x is sorted according to y, which enables a fast scan inside a x slice. listMatchCollect takes about 10ms (PC 450 MHz, optimized "-O4") for a match between lists of about 2000 objects each, which is fast enough for our needs. The same "locator" is used in listMatchupShift, to avoid scanning the whole input lists. Timing on listMatchCollect and listMatchupShift indicates a gain in speed by more than one order of magnitude after implementation of this FastFinder. Fast locator in starlists.

Definition at line 54 of file FastFinder.h.

Constructor & Destructor Documentation

◆ FastFinder()

lsst::jointcal::FastFinder::FastFinder ( const BaseStarList list,
const unsigned  nXSlice = 100 
)

Constructor.

Definition at line 38 of file FastFinder.cc.

39  : baselist(list), count(list.size()), stars(count), nslice(nXSlice), index(nslice + 1) {
40  if (count == 0) return;
41 
42  // fill "stars"
43  unsigned j = 0;
44  for (auto const &ci : list) {
45  stars[j] = ci;
46  ++j;
47  }
48 
49  sort(stars.begin(), stars.end(),
50  [](const stars_element &E1, const stars_element &E2) { return (E1->x < E2->x); });
51 
52  xmin = stars[0]->x;
53  xmax = stars[count - 1]->x;
55  if (xmin == xmax) nslice = 1;
56 
57  // the x size of each slice:
58  xstep = (xmax - xmin) / nslice;
59 
60  // fill the index array with the first star beyond the slice limit.
61  index[0] = 0; // first
62  unsigned istar = 0;
63  for (unsigned islice = 1; islice < nslice; ++islice) {
64  double xend = xmin + (islice)*xstep;
65  while (istar < count && stars[istar]->x < xend) ++istar;
66  index[islice] = istar;
67  }
68  index[nslice] = count; // last
69  for (unsigned islice = 0; islice < nslice; ++islice) {
70  sort(stars.begin() + index[islice], stars.begin() + index[islice + 1],
71  [](const stars_element &E1, const stars_element &E2) {
72  return (E1->y < E2->y);
73  }); // sort each slice in y.
74  }
75 }
double x
decltype(stars) typedef ::value_type stars_element
Definition: FastFinder.h:69
const BaseStarList baselist
Definition: FastFinder.h:56
std::vector< unsigned > index
Definition: FastFinder.h:66
std::vector< std::shared_ptr< const BaseStar > > stars
Definition: FastFinder.h:64
daf::base::PropertyList * list
Definition: fits.cc:913
T min(T... args)
T sort(T... args)

Member Function Documentation

◆ beginScan()

FastFinder::Iterator lsst::jointcal::FastFinder::beginScan ( const Point where,
double  maxDist 
) const

Definition at line 174 of file FastFinder.cc.

174  {
175  return FastFinder::Iterator(*this, where, maxDist);
176 }
FastFinder::Iterator Iterator
Definition: FastFinder.cc:178

◆ findClosest()

std::shared_ptr< const BaseStar > lsst::jointcal::FastFinder::findClosest ( const Point where,
const double  maxDist,
bool(*)(const BaseStar &)  SkipIt = nullptr 
) const

Find the closest with some rejection capability.

Definition at line 83 of file FastFinder.cc.

84  {
85  if (count == 0) return nullptr;
86  FastFinder::Iterator it = beginScan(where, maxDist);
87  if (*it == nullptr) return nullptr;
89  double minDist2 = maxDist * maxDist;
90  for (; *it != nullptr; ++it) {
91  if (SkipIt && SkipIt(**it)) continue;
92  double dist2 = where.computeDist2(**it);
93  if (dist2 < minDist2) {
94  pbest = *it;
95  minDist2 = dist2;
96  }
97  }
98  return pbest;
99 }
Iterator beginScan(const Point &where, double maxDist) const
Definition: FastFinder.cc:174

◆ findRangeInSlice()

void lsst::jointcal::FastFinder::findRangeInSlice ( const int  iSlice,
const double  yStart,
const double  yEnd,
pstar start,
pstar end 
) const

Definition at line 168 of file FastFinder.cc.

169  {
170  start = locateYStart(stars.begin() + index[iSlice], stars.begin() + index[iSlice + 1], yStart);
171  end = locateYEnd(start, stars.begin() + index[iSlice + 1], yEnd);
172 }
int end
pstar locateYStart(pstar begin, pstar end, double yVal) const
Definition: FastFinder.cc:134
pstar locateYEnd(pstar begin, pstar end, double yVal) const
Definition: FastFinder.cc:152

◆ locateYEnd()

FastFinder::pstar lsst::jointcal::FastFinder::locateYEnd ( pstar  begin,
pstar  end,
double  yVal 
) const

Definition at line 152 of file FastFinder.cc.

152  {
153  if (begin == stars.end()) return stars.end();
154  int span = end - begin - 1;
155  while (span > 1) {
156  int half_span = span / 2;
157  pstar middle = end - half_span;
158  if ((*middle)->y > yVal) {
159  end -= half_span;
160  span -= half_span;
161  } else {
162  span -= (span - half_span);
163  }
164  }
165  return end - 1;
166 }
T begin(T... args)
decltype(stars) typedef ::const_iterator pstar
Definition: FastFinder.h:70

◆ locateYStart()

FastFinder::pstar lsst::jointcal::FastFinder::locateYStart ( pstar  begin,
pstar  end,
double  yVal 
) const

Definition at line 134 of file FastFinder.cc.

134  {
135  if (begin == stars.end() || begin == end) return stars.end();
136  int span = end - begin - 1;
137  while (span > 1) {
138  int half_span = span / 2;
139  pstar middle = begin + half_span;
140  if ((*middle)->y < yVal) {
141  begin += half_span;
142  span -= half_span;
143  } else {
144  span -= (span - half_span);
145  }
146  }
147  return begin;
148 }

◆ print()

void lsst::jointcal::FastFinder::print ( std::ostream out) const

mostly for debugging

Definition at line 77 of file FastFinder.cc.

77  {
78  for (unsigned i = 0; i < count; ++i) {
79  stars[i]->print(out);
80  }
81 }

◆ secondClosest()

std::shared_ptr< const BaseStar > lsst::jointcal::FastFinder::secondClosest ( const Point where,
const double  maxDist,
std::shared_ptr< const BaseStar > &  closest,
bool(*)(const BaseStar &)  SkipIt = nullptr 
) const

Definition at line 101 of file FastFinder.cc.

103  {
104  closest = nullptr;
105  if (count == 0) return nullptr;
106  FastFinder::Iterator it = beginScan(where, maxDist);
107  if (*it == nullptr) return nullptr;
108  std::shared_ptr<const BaseStar> pbest1; // closest
109  std::shared_ptr<const BaseStar> pbest2; // second closest
110  double minDist1_2 = maxDist * maxDist;
111  double minDist2_2 = maxDist * maxDist;
112  for (; *it != nullptr; ++it) {
113  if (SkipIt && SkipIt(**it)) continue;
114  double dist2 = where.computeDist2(**it);
115  if (dist2 < minDist1_2) {
116  pbest2 = pbest1;
117  minDist2_2 = minDist1_2;
118  pbest1 = *it;
119  minDist1_2 = dist2;
120  } else if (dist2 < minDist2_2) {
121  pbest2 = *it;
122  minDist2_2 = dist2;
123  }
124  }
125  closest = pbest1;
126  return pbest2;
127 }

Member Data Documentation

◆ baselist

const BaseStarList lsst::jointcal::FastFinder::baselist

Definition at line 56 of file FastFinder.h.

◆ count

unsigned lsst::jointcal::FastFinder::count

Definition at line 58 of file FastFinder.h.

◆ index

std::vector<unsigned> lsst::jointcal::FastFinder::index

Definition at line 66 of file FastFinder.h.

◆ nslice

unsigned lsst::jointcal::FastFinder::nslice

Definition at line 65 of file FastFinder.h.

◆ pstar

decltype(stars) typedef ::const_iterator lsst::jointcal::FastFinder::pstar

Definition at line 70 of file FastFinder.h.

◆ stars

std::vector<std::shared_ptr<const BaseStar> > lsst::jointcal::FastFinder::stars

Definition at line 64 of file FastFinder.h.

◆ stars_element

decltype(stars) typedef ::value_type lsst::jointcal::FastFinder::stars_element

Definition at line 69 of file FastFinder.h.

◆ xmax

double lsst::jointcal::FastFinder::xmax

Definition at line 67 of file FastFinder.h.

◆ xmin

double lsst::jointcal::FastFinder::xmin

Definition at line 67 of file FastFinder.h.

◆ xstep

double lsst::jointcal::FastFinder::xstep

Definition at line 67 of file FastFinder.h.


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