C++ - 比较向量的有效方法

Question

目前我正在使用相机来检测标记.我使用opencv和Aruco Libary.

我现在才遇到问题.我需要检测2标记之间的距离是否小于特定值.我有一个计算距离的功能,我可以比较一切.但我正在寻找最有效的方法来跟踪所有标记(大约5/6)以及它们在一起的距离.

有一个带标记的列表,但我找不到比较所有标记的有效方法.

我有一个

Vector <Marker> 

我也有一个叫做的函数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; 
}

在Marker小号包含一个Point2f,这样我就可以轻松地对它们进行比较.

Answer 1

提高性能的一种方法是保持所有距离的平方并避免使用平方根函数.如果你对正在检查的具体值进行平方,那么这应该可以正常工作.

Answer 2

没有太多值得推荐的东西.如果我理解了这个问题并且我正确计算了对,那么当你有5个点时你需要计算10个距离,当你有6个点时你需要计算15个距离.如果您需要确定所有距离,那么您别无选择,只能计算所有距离.我没有看到任何解决方法.我可以给出的唯一建议是确保只计算每对之间的距离(例如,一旦知道点A和B之间的距离,就不需要计算B和A之间的距离).

也许可以对矢量进行排序,以便可以使循环短路.例如,如果您正确排序并且A点和B点之间的距离大于阈值,则A和C以及A​​和D之间的距离也将大于阈值.但请记住,排序不是免费的,并且对于小的点集,可能更快地计算所有距离("当n很小时,花式算法很慢,n通常很小.花式算法很大常数.直到你知道n经常变大,不要花哨....例如,二叉树总是比splay树更快,因为工作日问题.").

较新版本的C和C++标准库具有hypot计算点之间距离的功能:

#include <cmath>

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

它不一定更快,但它应该以避免在点相距很远时溢出的方式实现.

一个小的优化是简单地检查X的变化或Y的变化是否超过阈值.如果是,则可以忽略这两点之间的距离,因为总距离也将超过阈值:

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