matchOneToOne.hh

//
// Utility function for matching elements of one vector to another
// using best matching distance. All pairwise distances are calculated
// and then sorted; the best match corresponds to the smallest
// distance. Both matched elements are removed from the pool,
// then the best match is found among the remaining elements, etc.
//
// I. Volobouev
// April 2008

#ifndef MATCHONETOONE_HH_
#define MATCHONETOONE_HH_

#include <vector>
#include <algorithm>
#include <cfloat>

namespace {
    struct matchOneToOne_MatchInfo
    {
        double distance;
        unsigned i1;
        unsigned i2;

        inline bool operator<(const matchOneToOne_MatchInfo& r) const
        {
            return distance < r.distance;
        }
        inline bool operator>(const matchOneToOne_MatchInfo& r) const
        {
            return distance > r.distance;
        }
    };
}

//
// (*matchFrom1To2)[idx] will be set to the index of the element in v2
// which corresponds to the element at index "idx" in v1. If no match
// to the element at index "idx" in v1 is found, (*matchFrom1To2)[idx]
// is set to -1. All non-negative (*matchFrom1To2)[idx] values will be
// unique. The function returns the total number of matches made.
//
template <class T1, class T2, class DistanceCalculator>
unsigned matchOneToOne(const std::vector<T1>& v1, const std::vector<T2>& v2,
               const unsigned n1, const unsigned n2,
                       const DistanceCalculator& calc,
                       std::vector<int>* matchFrom1To2,
                       const double maxMatchingDistance = DBL_MAX)
{
    unsigned nused = 0;
    matchFrom1To2->clear();

    if (n1)
    {
        matchFrom1To2->reserve(n1);
        for (unsigned i1=0; i1<n1; ++i1)
            matchFrom1To2->push_back(-1);

        if (n2)
        {
            const unsigned nmatches = n1*n2;
            std::vector<matchOneToOne_MatchInfo> distanceTable(nmatches);
            std::vector<int> taken2(n2);

            for (unsigned i2=0; i2<n2; ++i2)
                taken2[i2] = 0;

            matchOneToOne_MatchInfo* m;
            for (unsigned i1=0; i1<n1; ++i1)
                for (unsigned i2=0; i2<n2; ++i2)
                {
                    m = &distanceTable[i1*n2+i2];
                    m->distance = calc(v1[i1], v2[i2]);
                    m->i1 = i1;
                    m->i2 = i2;
                }

            std::sort(distanceTable.begin(), distanceTable.end());
            for (unsigned i=0; i<nmatches && nused<n1 && nused<n2; ++i)
            {
                m = &distanceTable[i];
                if (m->distance > maxMatchingDistance)
                    break;
                if ((*matchFrom1To2)[m->i1] < 0 && !taken2[m->i2])
                {
                    (*matchFrom1To2)[m->i1] = static_cast<int>(m->i2);
                    taken2[m->i2] = 1;
                    ++nused;
                }
            }
        }
    }

    return nused;
}


#endif // MATCHONETOONE_HH_