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 Types
using	stars_element = decltype(stars)::value_type
using	pstar = decltype(stars)::const_iterator

Public Member Functions
	FastFinder (const BaseStarList &list, unsigned nXSlice=100)
	Constructor.
std::shared_ptr< const BaseStar >	findClosest (const Point &where, double maxDist, bool(*SkipIt)(const BaseStar &)=nullptr) const
	Find the closest with some rejection capability.
std::shared_ptr< const BaseStar >	secondClosest (const Point &where, double maxDist, std::shared_ptr< const BaseStar > &closest, bool(*SkipIt)(const BaseStar &)=nullptr) const
void	print (std::ostream &out) const
	mostly for debugging
Iterator	beginScan (const Point &where, double maxDist) const
void	findRangeInSlice (int iSlice, double yStart, 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
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.

Member Typedef Documentation

pstar

using lsst::jointcal::FastFinder::pstar = decltype(stars)::const_iterator

Definition at line 70 of file FastFinder.h.

stars_element

using lsst::jointcal::FastFinder::stars_element = decltype(stars)::value_type

Definition at line 69 of file FastFinder.h.

Constructor & Destructor Documentation

FastFinder()

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

Constructor.

Definition at line 38 of file FastFinder.cc.

        : baselist(list), count(list.size()), stars(count), nslice(nXSlice), index(nslice + 1) {
    if (count == 0) return;
 
    // fill "stars"
    unsigned j = 0;
    for (auto const &ci : list) {
        stars[j] = ci;
        ++j;
    }
 
    sort(stars.begin(), stars.end(),
         [](const stars_element &E1, const stars_element &E2) { return (E1->x < E2->x); });
 
    xmin = stars[0]->x;
    xmax = stars[count - 1]->x;
    nslice = std::min(nslice, count);
    if (xmin == xmax) nslice = 1;
 
    // the x size of each slice:
    xstep = (xmax - xmin) / nslice;
 
    // fill the index array with the first star beyond the slice limit.
    index[0] = 0;  // first
    unsigned istar = 0;
    for (unsigned islice = 1; islice < nslice; ++islice) {
        double xend = xmin + (islice)*xstep;
        while (istar < count && stars[istar]->x < xend) ++istar;
        index[islice] = istar;
    }
    index[nslice] = count;  // last
    for (unsigned islice = 0; islice < nslice; ++islice) {
        sort(stars.begin() + index[islice], stars.begin() + index[islice + 1],
             [](const stars_element &E1, const stars_element &E2) {
                 return (E1->y < E2->y);
             });  // sort each slice in y.
    }
}

Member Function Documentation

beginScan()

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

Definition at line 174 of file FastFinder.cc.

                                                                                 {
    return FastFinder::Iterator(*this, where, maxDist);
}

findClosest()

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

Find the closest with some rejection capability.

Definition at line 83 of file FastFinder.cc.

                                                                                                {
    if (count == 0) return nullptr;
    FastFinder::Iterator it = beginScan(where, maxDist);
    if (*it == nullptr) return nullptr;
    std::shared_ptr<const BaseStar> pbest;
    double minDist2 = maxDist * maxDist;
    for (; *it != nullptr; ++it) {
        if (SkipIt && SkipIt(**it)) continue;
        double dist2 = where.computeDist2(**it);
        if (dist2 < minDist2) {
            pbest = *it;
            minDist2 = dist2;
        }
    }
    return pbest;
}

findRangeInSlice()

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

Definition at line 168 of file FastFinder.cc.

                                                    {
    start = locateYStart(stars.begin() + index[iSlice], stars.begin() + index[iSlice + 1], yStart);
    end = locateYEnd(start, stars.begin() + index[iSlice + 1], yEnd);
}

locateYEnd()

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

Definition at line 152 of file FastFinder.cc.

                                                                                {
    if (begin == stars.end()) return stars.end();
    int span = end - begin - 1;
    while (span > 1) {
        int half_span = span / 2;
        auto middle = end - half_span;
        if ((*middle)->y > yVal) {
            end -= half_span;
            span -= half_span;
        } else {
            span -= (span - half_span);
        }
    }
    return end - 1;
}

locateYStart()

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

Definition at line 134 of file FastFinder.cc.

                                                                                  {
    if (begin == stars.end() || begin == end) return stars.end();
    int span = end - begin - 1;
    while (span > 1) {
        int half_span = span / 2;
        auto middle = begin + half_span;
        if ((*middle)->y < yVal) {
            begin += half_span;
            span -= half_span;
        } else {
            span -= (span - half_span);
        }
    }
    return begin;
}

print()

void lsst::jointcal::FastFinder::print

(

std::ostream &

out

)

const

mostly for debugging

Definition at line 77 of file FastFinder.cc.

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

secondClosest()

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

Definition at line 101 of file FastFinder.cc.

                                                                                                  {
    closest = nullptr;
    if (count == 0) return nullptr;
    FastFinder::Iterator it = beginScan(where, maxDist);
    if (*it == nullptr) return nullptr;
    std::shared_ptr<const BaseStar> pbest1;  // closest
    std::shared_ptr<const BaseStar> pbest2;  // second closest
    double minDist1_2 = maxDist * maxDist;
    double minDist2_2 = maxDist * maxDist;
    for (; *it != nullptr; ++it) {
        if (SkipIt && SkipIt(**it)) continue;
        double dist2 = where.computeDist2(**it);
        if (dist2 < minDist1_2) {
            pbest2 = pbest1;
            minDist2_2 = minDist1_2;
            pbest1 = *it;
            minDist1_2 = dist2;
        } else if (dist2 < minDist2_2) {
            pbest2 = *it;
            minDist2_2 = dist2;
        }
    }
    closest = pbest1;
    return pbest2;
}

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.

stars

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

Definition at line 64 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:

• /j/snowflake/release/lsstsw/stack/lsst-scipipe-9.0.0/Linux64/jointcal/g82479be7b0+f568feb641/include/lsst/jointcal/FastFinder.h
• /j/snowflake/release/lsstsw/stack/lsst-scipipe-9.0.0/Linux64/jointcal/g82479be7b0+f568feb641/src/FastFinder.cc