c++ - 如何删除 STD::List 中最近的 "Point"对象到某个 x,y？

Question

我有一个点类:

class Point {
public:
    int x, y;
    Point(int x1, int y1)
    {
        x = x1;
        y = y1;
    }
};

和点列表:

std::list <Point> pointList;
std::list <Point>::iterator iter;

我正在将点推送到我的 pointList(尽管如果尚未推送任何点，该列表可能还不包含任何点)。

我有两个问题:

如何从列表中删除最接近任意点 (x, y) 的点？

假设我有 x,y (5,12)，我想在列表中找到最接近该点的点并将其从 STD::List 中删除。

我知道我必须使用距离公式并且我必须使用迭代器遍历列表但是我在概念化如何在我迭代时跟踪哪个点最近时遇到了一些问题通过列表。

如何返回给定 (x,y) 的 x 半径范围内的数组或点列表？

与上一个问题类似，只是我需要一个指向给定 (x,y) 半径 5 以内的“点”对象的指针列表。另外，我应该返回一个数组还是一个列表？

如果有人能帮助我，我仍然在努力学习 C++，我很感激。

Answer 1

使用 std::list::iterator 变量在列表中循环时跟踪最近的点。当您到达列表的末尾时，它将包含最近的点并可用于删除该项目。

void erase_closest_point(const list<Point>& pointList, const Point& point)
{
    if (!pointList.empty())
    {
        list<Point>::iterator closestPoint = pointList.begin();
        float closestDistance = sqrt(pow(point.x - closestPoint->x, 2) +
                                     pow(point.y - closestPoint->y, 2));

        // for each point in the list
        for (list<Point>::iterator it = closestPoint + 1;
             it != pointList.end(); ++it)
        {
            const float distance = sqrt(pow(point.x - it->x, 2) +
                                        pow(point.y - it->y, 2));

            // is the point closer than the previous best?
            if (distance < closestDistance)
            {
                // replace it as the new best
                closestPoint = it;
                closestDistance = distance
            }
        }

        pointList.erase(closestPoint);
    }
}

构建给定点半径范围内的点列表是类似的。请注意，空半径列表通过引用传递到函数中。通过引用将点添加到列表中将消除在按值返回 vector 时复制所有点的需要。

void find_points_within_radius(vector<Point>& radiusListOutput,
                               const list<Point>& pointList,
                               const Point& center, float radius)
{
    // for each point in the list
    for (list<Point>::iterator it = pointList.begin();
         it != pointList.end(); ++it)
    {
        const float distance = sqrt(pow(center.x - it->x, 2) +
                                    pow(center.y - it->y, 2));

        // if the distance from the point is within the radius
        if (distance > radius)
        {
            // add the point to the new list
            radiusListOutput.push_back(*it);
        }
    }
}

再次使用复制，如果:

struct RadiusChecker {
    RadiusChecker(const Point& center, float radius)
        : center_(center), radius_(radius) {}

    bool operator()(const Point& p)
    {
        const float distance = sqrt(pow(center_.x - p.x, 2) +
                                    pow(center_.y - p.y, 2));
        return distance < radius_;
    }

private:
    const Point& center_;
    float radius_;
};

void find_points_within_radius(vector<Point>& radiusListOutput,
                               const list<Point>& pointList,
                               const Point& center, float radius)
{
    radiusListOutput.reserve(pointList.size());
    remove_copy_if(pointList.begin(), pointList.end(),
                   radiusListOutput.begin(),
                   RadiusChecker(center, radius));
}

请注意，如果您需要额外的性能，可以删除 sqrt，因为幅度的平方同样适用于这些比较。另外，如果你真的想提高性能而不是考虑一个允许像 quadtree 这样的场景分区的数据结构。 .第一个问题与collision detection密切相关并且有大量关于该主题的有值(value)信息。