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 BaseStar >	findClosest (const Point &where, const double maxDist, bool(*SkipIt)(const BaseStar &)=nullptr) const
	Find the closest with some rejection capability. More...
std::shared_ptr< const BaseStar >	secondClosest (const Point &where, const double maxDist, std::shared_ptr< const BaseStar > &closest, bool(*SkipIt)(const BaseStar &)=nullptr) const
void	dump () 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.

        : 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.
    }
    // dump();
}

Member Function Documentation

beginScan()

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

Definition at line 175 of file FastFinder.cc.

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

dump()

void lsst::jointcal::FastFinder::dump

(

)

const

mostly for debugging

Definition at line 78 of file FastFinder.cc.

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

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 84 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	(	const int	iSlice,
		const double	yStart,
		const double	yEnd,
		pstar &	start,
		pstar &	end
	)		const

Definition at line 169 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 153 of file FastFinder.cc.

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

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 102 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.

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:

• /j/snowflake/release/lsstsw/stack/Linux64/jointcal/19.0.0-2-gb96a1c4+3/include/lsst/jointcal/FastFinder.h
• /j/snowflake/release/lsstsw/stack/Linux64/jointcal/19.0.0-2-gb96a1c4+3/src/FastFinder.cc