CODEWITHSUNDEEP
c++stl
YXD
YXD

Reputation: 32511

Index of closest points between two arrays

Given two vectors foo and bar, I want to output a vector of length foo.size() containing the index to the "closest" element of bar. I don't like reinventing the wheel - are there any STL algorithms or otherwise to do this concisely?

#include <vector>
#include <cmath>
#include <float.h>

int main() {
    vector<double> foo;
    vector<double> bar;

    // example data setup
    double array_foo[] = {0.0, 1.0, 2.0, 3.0, 4.0,
                          5.0, 6.0, 7.0, 8.0, 9.0};
    double array_bar[] = {4.8, 1.5, 12.0};
    foo.assign(array_foo, array_foo + 10);
    bar.assign(array_bar, array_bar + 3);

    // output array
    vector<int> indices;
    indices.resize(foo.size());

    for(int i = 0; i < foo.size(); i++) {
        double dist = DBL_MAX;
        int idx = 0;
        // find index of closest element in foo
        for(int j = 0; j < bar.size(); j++) {
            if(abs(foo[i] - bar[j]) < dist) {
                dist = abs(foo[i] - bar[j]);
                idx = j;
            }
        }
        indices[i] = idx;
    }
    // expected result: indices = [1,1,1,1,0,0,0,0,0,2]
    return 0;
}

Upvotes: 2

Views: 480

Answers (3)

templatetypedef
templatetypedef

Reputation: 372664

If you know that the arrays are sorted, or if you're allowed to sort the arrays, you could use the STL lower_bound or upper_bound algorithms to do a binary search to locate a value from the second array in the first. The returned iterator will point to the first element at least as large as (or strictly greater than in the case of upper_bound) your element, limiting the number of elements out of the first array you need to check to two. This will run in O(m lg n), where m is the number of elements in the second array and n is the number in the first.

Upvotes: 0

valdo
valdo

Reputation: 12923

I see 3 different solutions. They all offer the same complexity O(N * logN).

1.

Store elements if bar within the binary tree (std::map). Then for every element in foo you'll have to find up to two bounding elements, and select the best from them.

Building the tree is O(N * logN), second pass is O(N * logN)

2.

Same as above, except instead of using the binary tree you may use a sorted array. Create an array, each element of which consists of an element of bar and its index (alternatively your array should contain pointers to the elements of bar). Then, instead of the tree search you'll do the array search.

From the complexity point of view this is pretty the same. However practically search in the sorted array will probably be somewhat faster.

3.

Sort both foo and bar. (Yet again you'll have to either have an original index in your sorted array, or just store pointers to the original elements.

Now, for every element in sorted foo you don't have to do the full search in bar. Instead you should only check if you should remain at the current position at sorted bar or move forward.

Upvotes: 3

Peter Alexander
Peter Alexander

Reputation: 54270

This exact algorithm doesn't exist, but you could implement it in an idiomatic STL way by using std::min_element and a custom functor:

template <typename T>
T norm(const T& a, const T& b)
{
    return abs(b - a);
}

template <typename T>
struct closer_compare
{
    closer_compare(const T& to) : to(to) {}
    bool operator()(const T& a, const T& b) const
    {
        return norm(a, to) < norm(b, to);
    }
    const T& to;
};

template <typename It1, typename It2, typename OutIt>
void find_nearest_indices(It1 in1_begin, It1 in1_end, It2 in2_begin, It2 in2_end, OutIt out)
{
    typedef typename std::iterator_traits<It1>::value_type value;
    for (It1 it = in1_begin; it != in1_end; ++it)
    {
        It2 closest = std::min_element(in2_begin, in2_end, closer_compare<value>(*it));
        *out++ = std::distance(in2_begin, closest);
    }
}

Your algorithm would then be replaced with:

find_nearest_indices(foo.begin(), foo.end(), bar.begin(), bar.end(), indices.begin());

I tested with your input and got your expected results.

Upvotes: 2

Related Questions