How do I delete the closest "Point" object in a STD::List to some x,y?

Question

I have a point class like:

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

and a list of points:

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

I'm pushing points on to my pointList (although the list might contain no Points yet if none have been pushed yet).

I have two questions:

How can I delete the closest point to some arbitrary (x, y) from the list?

Lets say I have the x,y (5,12) and I want to find the Point in the list closest to that point and remove it from the STD::List.

I know I'll have to use the distance formula and I'll have to iterate through the list using an iterator but I'm having some trouble conceptualizing how I'll keep track of which point is the closest as I iterate through the list.

How can I return an array or list of points within x radius of a given (x,y)?

Similar to the last question except I need a list of pointers to the "Point" objects within say 5 radius of a given (x,y). Also, should I return an array or a List?

If anyone can help me out, I'm still struggling my way through C++ and I appreciate it.

Answer 1

Use a std::list::iterator variable to keep track of the closest point as you loop through the list. When you get to the end of the list it will contain the closest point and can be used to erase the item.

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

Building a list of points within a radius of a given point is similar. Note that an empty radius list is passed into the function by reference. Adding the points to the list by reference will eliminate the need for copying all of the points when returning the vector by value.

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

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

Note that the sqrt can be removed if you need extra performance since the square of the magnitude works just as well for these comparisons. Also, if you really want to increase performance than consider a data structure that allows for scene partitioning like a quadtree. The first problem is closely related to collision detection and there is a ton of valuable information about that topic available.