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.

are you being heavily affected by the vectors performance currently? Or do you just wish for a slightly faster solution? — Syntactic Fructose, Jun 03 '14 at 17:53
If you return a `double`, do your intermediate calculations with that type. And what type of comparison do you want? Anyway, if you know there's a constant / small bounded number of elements, a vector might be overkill, consider `std::array`. — Deduplicator, Jun 03 '14 at 17:53
You can consider just the distance^2, and omit the sqrtf for one less operation, if you just want a metric for comparison — Ben, Jun 03 '14 at 17:54
Your problem is very similar to colision detection: http://stackoverflow.com/questions/7107231/best-algorithm-for-efficient-collision-detection-between-objects — Ian Medeiros, Jun 03 '14 at 18:02
Keep in mind that if you're only tracking 6 markers, then you can compare them all with each other using only 15 comparisons. There's probably not going to be much difference between the most efficient and a naive algorithm. — Michael Burr, Jun 03 '14 at 18:08
But if you are dealing with just 6 elements, I really think that doing a simple brute force comparison will not be the bottleneck. Scanning the image searching for the markers is far more expensive. — Ian Medeiros, Jun 03 '14 at 18:08
I will take a look at that post @IanMedeiro I will keep that in mind @ Ben The amount of elements is not constant, at the moment its 5/6 but can grow in the future to 20+ Im a bit affected, but i can think of a good and efficient way. — Joris Mathijssen, Jun 03 '14 at 18:10

score 8 · Answer 1 · answered Jun 03 '14 at 17:55

8

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.

answered Jun 03 '14 at 17:55

Sesame

183
1
9

Thanks for all the fast and good answers! I will try somethings out and will pick a good answer! – Joris Mathijssen Jun 03 '14 at 18:12

Max Lybbert · Accepted Answer · 2014-06-03T21:10:25.263

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;
        }
        ...
    }
}

Thank you for all the work you put in this answer, i tried this and a few other performance tips. I had some really big performance upgrades and i'm very happy with the results. — Joris Mathijssen, Jun 03 '14 at 19:21

score 4 · Answer 3 · answered Jun 03 '14 at 17:59

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.

C++ - Efficient way to compare vectors

3 Answers3