Find closest value in a vector of struct

Question

I'm looking for solution how to find the most similar value in a vector of struct:

struct tStruct{
    int nr;
    double data1;
    double data2;};

vector<tStruct> tPoint {
    {3, 32.3247351, 14.6209107},
    {4, 32.3262635, 14.6352101},
    {5, 32.3249088, 14.6497090},
    {6, 32.3240278, 14.6642700},
    {7, 32.3256065, 14.6786958}};

I have two variables double vdata1 = 32.32443, double vdata2 = 14.65692 that I would like compare with tPoint vector and return the nearest found value, e.g. {5, 32.3249088, 14.6497090} to make some other calculations.

Is there any way to achieve this?

It depends what you mean by "most similar". Euclidean distance? Manhattan distance? *Largest* coordinate difference? — meowgoesthedog, Sep 06 '18 at 09:40
Those look like geographic coordinates. If so, then your distance function required by the answers below will probably be the [haversine formula](https://stackoverflow.com/q/27928/1332041). — acraig5075, Sep 06 '18 at 10:05
I want to convert coordinate to kilometre point of the road. Calculate distance by haversine formula will be my next step, when I find the "nearest" index of tPoint vector. — Mac_P, Sep 06 '18 at 10:22

score 3 · Answer 1 · edited Sep 06 '18 at 10:13

3

Of course there is a way, usually you would do something like that:

tStruct result = tPoint.front(); //Assuming there is always at least one point
auto d = distance(result); // distance() is what you define it to be
for(const auto& point : tPoint)
{
    auto current_distance = distance(point);
    if(current_distance < d)
    {
         d = current_distance; 
         result = point;
    }
}

This is pretty much what std::min_element does, but I'm not sure it can cache distances, so it would be a bit less effective. Probably it can be done as a combination of std::min_element and boost::transform_iterator.

edited Sep 06 '18 at 10:13

anatolyg

26,506
9
60
134

answered Sep 06 '18 at 09:55

Ap31

3,244
1
18
25

Thanks for the answer, but could you explain whot you mind by distance()? std :: min_element will return only exact data (same as in the tPoint vector) or also "nearest" to the searched? – Mac_P Sep 06 '18 at 10:58
`distance()` is what you use to select the "nearest" point. If by "nearest" you mean "closest to the origin in Euclidean metric", then you can define distance as `data1*data1 + data2*data2`. If you mean "nearest to the point X", then you need to add X as another parameter, but that's up to you. [std::min_element](https://en.cppreference.com/w/cpp/algorithm/min_element) will return an iterator pointing to the element with the "smallest distance", but again, you have to supply the `distance()` function yourself (as in @lubgr's answer) – Ap31 Sep 06 '18 at 11:23

lubgr · Accepted Answer · 2018-09-06T10:02:01.220

2

I would suggest using std::min_element that ships with the <algorithm> header and pass a custom predicate. This way, the actual notion of what "closest" means can be kept in a function object. An exemplary snippet could look like this:

#include <algorithm>
#include <cmath>

double vdata1 = 32.32443;
double vdata2 = 14.65692;

const auto dist = [vdata1, vdata2](const auto& p){
    // Change the following to your needs
    return std::pow((p.data1 - vdata1), 2) + std::pow((p.data2 - vdata2), 2);
};

const auto closest = std::min_element(tPoint.cbegin(), tPoint.cend(),
        [&dist](const auto& p1, const auto& p2){ return dist(p1) < dist(p2); });

edited Sep 06 '18 at 10:02

answered Sep 06 '18 at 09:52

lubgr

37,368
3
66
117

1

You might get rid of `sqrt` and so compare dist² (which has same order). – Jarod42 Sep 06 '18 at 09:57
@Jarod42 You're right, that's definitely better. Thanks for the hint! – lubgr Sep 06 '18 at 10:01
@lubgr Thank you for the answer, unfortunately I'm using mingw53 32 and I cannot complie it due to auto in lambda parameter (works in msvc2017 though - which I can't to use). – Mac_P Sep 06 '18 at 10:51
2

@Mac_P You can change the `auto` parameter type to the actual type `tStruct`, if it's only the generic lambda that hinders you from compiling this approach. – lubgr Sep 06 '18 at 11:12

Find closest value in a vector of struct

2 Answers2