如何将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),我想找到最接近该点的列表中的Point并将其从STD :: List中删除.

我知道我将不得不使用距离公式,我将不得不使用迭代器迭代列表,但是我在描述如何跟踪哪个点最接近我在迭代列表时遇到了一些麻烦.

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

类似于上一个问题,除了我需要一个指向给定(x,y)的5个半径内的"点"对象的指针列表.另外,我应该返回一个数组还是一个List？

如果有人可以帮助我,我仍然在努力通过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);
    }
}

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

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

再次使用copy if:

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,因为幅度的平方对于这些比较同样适用.此外,如果您真的想要提高性能而不是考虑允许像四叉树这样的场景分区的数据结构.第一个问题与碰撞检测密切相关,并且有大量有关该主题的有价值信息.