C++ - Efficient way to compare vectors

Question

At the moment i'm working with a camera to detect a marker. I use opencv and the Aruco Libary.

Only I'm stuck with a problem right now. I need to detect if the distance between 2 marker is less than a specific value. I have a function to calculate the distance, I can compare everything. But I'm looking for the most efficient way to keep track of all the markers (around 5/6) and how close they are together.

There is a list with markers but I cant find a efficient way to compare all of them.

I have a

Vector <Marker> 

I also have a function called getDistance.

double getDistance(cv::Point2f punt1, cv::Point2f punt2)
{
    float xd = punt2.x-punt1.x;
    float yd = punt2.y-punt1.y;
    double Distance = sqrtf(xd*xd + yd*yd);
    return Distance; 
}

The Markers contain a Point2f, so i can compare them easily.

Answer 1

There isn't really a lot to recommend. If I understand the question and I'm counting the pairs correctly, you'll need to calculate 10 distances when you have 5 points, and 15 distances when you have 6 points. If you need to determine all of the distances, then you have no choice but to calculate all of the distances. I don't see any way around that. The only advice I can give is to make sure you calculate the distance between each pair only once (e.g., once you know the distance between points A and B, you don't need to calculate the distance between B and A).

It might be possible to sort the vector in such a way that you can short circuit your loop. For instance, if you sort it correctly and the distance between point A and point B is larger than your threshold, then the distances between A and C and A and D will also be larger than the threshold. But keep in mind that sorting isn't free, and it's likely that for small sets of points it would be faster to just calculate all distances ("Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. ... For example, binary trees are always faster than splay trees for workaday problems.").

Newer versions of the C and C++ standard library have a hypot function for calculating distance between points:

#include <cmath>

double getDistance(cv::Point2f punt1, cv::Point2f punt2)
{
    return std::hypot(punt2.x - punt1.x, punt2.y - punt1.y);
}

It's not necessarily faster, but it should be implemented in a way that avoids overflow when the points are far apart.

---

One minor optimization is to simply check if the change in X or change in Y exceeds the threshold. If it does, you can ignore the distance between those two points because the overall distance will also exceed the threshold:

const double threshold = ...;
std::vector<cv::Point2f> points;
// populate points
...
for (auto i = points.begin(); i != points.end(); ++i) {
    for (auto j = i + 1; j != points.end(); ++j) {
        double dx = std::abs(i->x - j->x), dy = std::abs(i->y - j->y);
        if (dx > threshold || dy > threshold) {
            continue;
        }
        double distance = std::hypot(dx, dy);
        if (distance > threshold) {
            continue;
        }
        ...
    }
}

Answer 2

One way to increase performance is to keep all the distances squared and avoid using the square root function. If you square the specific value you are checking against then this should work fine.

Answer 3

If you're dealing with large amounts of data inside your vector you may want to consider some multithreading using future.

Vector <Marker> could be chunked into X chunks which are asynchronously computed together and stored inside std::future<>, putting to use @Sesame's suggestion will also increase your speed as well.