Fastest way to find closest value in a vector

Hi,

I have a serious issue in matlab. I have 2 vectors v1 and v2 and length(v1) = 1376872, length(v2) = 1350228. Vector v2 contains information about position in the original coordinate system. Vector v1 is coordinates from the wanted coordinate system, transformed to the same type of coordinates as v2.

I need to find the closest match between the coordinate systems for each point. So to say, I want a vector of the same length as v1, each element containing the index of the closest point in v2.

I have solved the problem by using a for loop.

    ind = -1*ones(length(v1),1);
    for k = 1:length(v1)
        diff = v1(k)-v2;
        [~,minInd] = min(abs(diff));
        if abs(real(diff(minInd)))<2.5 && abs(imag(diff(minInd)))<2.5
            ind(k) = minInd;
        end
    end

This is however a really slow process (will take around 10 hours). This time consumption is unacceptable for the application and thus I need to find a faster solution.

If anyone knows how to solve this please help. Also, if there are better ways of mapping values between coordinate systems (which there probably are) this would also be accepted.

BR Patrik

Answer 1

[John D'Errico]

It is important to know if vector v2 is sorted. If it is, then use histc, which will quickly give you the index of the elements just under each element of v1.

Then you check to see if the element above the ones you just found is closer.

Finally, if the vector v2 is NOT sorted, then it is still simple. Just do s sort on v2, to create a vector v3. Keep the tags from that sort. Now, use the scheme I mentioned above to find the closest point in v3. Use the tags from the sort to back out the original index of those elements. If all you needed is the actual closest value, then there is no need to do this last step.

Note that ALL of the above ops are vectorizable. No explicit loops are necessary to do anything I suggested above.

[Patrik Ek]

However, I just found an issue with this. The elements that I have is 2 dimensional (a surface), and is for now represented with complex values. SORT then sorts it after absolute value. Is it possible to create a representation that goes well with the above method?

/Patrik

[Patrik Ek]

Sorry for my stupidity. Of course I should treat the dimensions separately. Thank you so much, this works amazing (1 second compared to 10 hours)!