按向量中的距离对矢量值进行排序

Question

我有两个位置,我的玩家位置(2D)和我循环的实体向量,每个都有一个位置(2D),我希望我的函数返回到我的位置的最近距离,但我不知道如何这样做是因为我卡住了,在c#中我可以使用linq,但我正在学习c ++我的函数看起来像这样:

const Entity GetNearestEntity()
{
    for (Entity i : fb.Entities)
    {
        double xDiff = (double)abs(fb.PlayerLocation.X - i.X);
        double yDiff = (double)abs(fb.PlayerLocation.Y - i.Y);

        //Stuck here.. 
        //How can i get the closest object out of my vector<Entity> collection?
    }
}

帮助赞赏!

Answer 1

既然你是C++的新手(正如你所说的那样),我想给你一个很好的选择,需要一点不同的思考,但是一旦你习惯了它,你就会喜欢它.

基本的想法

您正在寻找一个元素(或您想引用该元素可能在以后修改),这是最小的元素相对于一定的比较方法.C++允许您选择如何比较元素,分别针对特定查询(在这种情况下,不要将比较视为明确定义的"小于"/"大于"运算符,但它是一个类似的概念).

您可以在本地为此特定方案定义此类比较.比较方法可以作为独立函数实现,作为函子(实现所谓的"调用操作符"的函数对象)或lambda函数,您应该更喜欢.

Lambda函数语法

Lambda函数是匿名函数,通常在您按字面意思写入的相同位置使用.lambda函数语法是你必须习惯的东西,但是一旦你这样做,它就是一个强大的东西!

[](Entity a, Entity b) {  return a.X < b.X;  }

这是一个lambda函数,它接受两个Entity实例并简单地比较它们的X坐标.当然这不是你想要的,但我想先向你展示语法.

现在我们要实现一个比较函数,它比较相对于原点的坐标(你的玩家位置),所以这是从函数外部传递的东西,而不是参数(因为比较函数只能取两个值)待比较).这是通过捕获一些上下文变量来完成的.看看这里:

int captured = ...
...
[captured](Entity a, Entity b) {  return a.X + captured < b.X + captured;  }

仍然没有任何意义,它显示了如何引用lambda函数中lambda函数之外定义的变量.

针对您的特定问题的Lambda函数

现在我们可以正确编写比较方法:

[fb](Entity a, Entity b) {
    double ax = fb.PlayerLocation.X - a.X;
    double ay = fb.PlayerLocation.Y - a.Y;
    double a = ax * ax + ay * ay; // we can save the sqrt()
    double bx = fb.PlayerLocation.X - b.X;
    double by = fb.PlayerLocation.Y - b.Y;
    double b = bx * bx + by * by; // we can save the sqrt()
    return a < b;
}

所以我们捕获fb,我们计算两个实体的相对坐标,a并b计算长度的平方(所以我们可以保存sqrt)并比较这些距离.代码看起来有点臃肿; 我们稍后会改进这个.

在STL算法中使用Lambda函数

一旦你理解了如何编写这样的比较函数,最后一步变得微不足道,因为STL提供了许多可以使用的算法,可以使用这些函数:

Entity closest = *std::min_element(fb.Entities.begin(), fb.Entities.end(),
    [fb](Entity a, Entity b) {
        double ax = fb.PlayerLocation.X - a.X;
        double ay = fb.PlayerLocation.Y - a.Y;
        double a = ax * ax + ay * ay; // we can save the sqrt()
        double bx = fb.PlayerLocation.X - b.X;
        double by = fb.PlayerLocation.Y - b.Y;
        double b = bx * bx + by * by; // we can save the sqrt()
        return a < b;
    }
);

正如您所看到的,我只是将lambda函数直接传递给另一个函数调用(没有先定义具有特定名称的函数,因为它是一个匿名函数).此函数调用是std::min_element,它找到两个迭代器之间的最小元素(如果要在整个容器中搜索,请使用begin/end迭代器对).它返回另一个迭代器.使用*前缀运算符,可以访问迭代器指向的元素.

请注意,一旦将其存储为Entity值,就会将其复制,因此修改不再直接写入向量,而是写入本地副本.为避免这种情况,请使用Entity&,这是对向量中元素的(可修改的)引用,您的函数可以毫无问题地返回(只要引用的值在函数外部有效,在您的情况下就是如此).

改进

如果你写一个比较两个实体的距离函数,这就变得更简单了:(注意缺少abs,这是因为我们无论如何都要对数值求平方,任何负号都会消失)

double distance(Entity p, Entity q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return sqrt(delta_x * delta_x + delta_y * delta_y);
}

或者,再次保存sqrt:

double distanceSquare(Entity p, Entity q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return (delta_x * delta_x + delta_y * delta_y);
}

所以代码变成:

Entity closest = *std::min_element(fb.Entities.begin(), fb.Entities.end(),
    [fb](Entity a, Entity b) {
        return distanceSquare(a, fb.PlayerLocation) <
               distanceSquare(b, fb.PlayerLocation);
    }
);

另一个改进是通过(不可修改的)引用传递变量,而不是按值传递它们.这意味着不需要复制变量.将代码放入您在问题中编写的方法中,代码变为(应用了引用调用概念并返回可修改的引用):

double distanceSquare(const Entity & p, const Entity & q) {
    double delta_x = p.X - q.X;
    double delta_y = p.Y - q.Y;
    return (delta_x * delta_x + delta_y * delta_y);
}

Entity & GetNearestEntity()
{
    return *std::min_element(fb.Entities.begin(), fb.Entities.end(),
        [fb](const Entity & a, const Entity & b) {
            return distanceSquare(a, fb.PlayerLocation) <
                   distanceSquare(b, fb.PlayerLocation);
        }
    );
}

(注意嵌套的返回语句.内部的一个是lambda函数的一部分并返回比较逻辑的结果.外部的返回最终结果,因此具有最小距离的实体.)

最后,它看起来更干净(至少在我看来).一旦你理解了这个概念,你就会看到它的美丽.:)

我将向您展示的最终改进在Andrew Durward对此答案的评论中提到:我们现在编写的Lambda函数,fb为每次调用复制一次值,GetNearestEntity因为它可能在上次调用后发生了变化.我们可以通过引用捕获来避免这种复制操作,这与通过引用调用相同的概念,但对于捕获的变量.只需&在捕获表达式中写入变量名称:

//...
        [&fb](const Entity & a, const Entity & b) {
            return distanceSquare(a, fb.PlayerLocation) <
                   distanceSquare(b, fb.PlayerLocation);
        }
//...

捕获语法在开始时可能看起来有点奇怪,但它提供了对通过引用或值捕获的封闭上下文中的哪些变量的强大控制:

资料来源:http://www.cprogramming.com/c++11/c++11-lambda-closures.html

[]          Capture nothing (or, a scorched earth strategy?)
[&]         Capture any referenced variable by reference
[=]         Capture any referenced variable by making a copy
[=, &foo]   Capture any referenced variable by making a copy, but capture variable foo by reference
[bar]       Capture bar by making a copy; don't copy anything else
[this]      Capture the this pointer of the enclosing class

如果您想了解有关在lambda函数中捕获变量的更多信息,请阅读此处或google以获取"C++ 11 lambda捕获语法".

演示此代码:http://ideone.com/vKAFmx

Answer 2

通过跟踪离您最近的元素的索引，这可能会更容易做到，这在“for”循环中会更容易，例如：

Entity GetNearestEntity()
{
    int closestEnt = 0;
    double smallestDist = -1.0;

    for (int i = 0; i < Entities.length(); i++) 
    {
        double xDiff = (double)abs(fb.PlayerLocation.X - Entities[i].X);
        double yDiff = (double)abs(fb.PlayerLocation.Y - Entities[i].Y);
        double totalDist = sqrt(pow(xDiff, 2) + pow(yDiff, 2));

        if ((totalDist < smallestDist) || (smallestDist == -1.0))
        {
            closestEnt = i;
            smallestDist = totalDist;
        }
    }

    return Entities[closestEnt];
}

这可能无法立即编译，自从我使用 C++ 以来已经有一段时间了，而且我不知道这是否是计算平方根和幂的正确方法。然而，它有一个很好的好处，即只跟踪 double 和 int，而不是对象。