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

You are right on how it should be made. Just iterate through all items in the list and keep track of the smallest distance already found, and the nearest point you found in two variables, making sure you don't match the point with itself if the problem states so. Then just delete the point you found.

How this is exactly made is kept as an exercise.

If you want to get a list of points in a given radius from another point, iterate the list and build a second list containing only the points within the specified range.

Again, how it's made in code is left to you as an exercise.

Answer 2

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.

Answer 3

You have to keep the iterator to delete it afterwards.

std::list<Point>::iterator closest;
std::list<Point>::iterator it = pointList.begin();
double min_dist=dist(your_point, *it);
++it;
for (; it != pointList.end(); ++it)
{
        double actual_dist = dist(your_point, *it);
        if (actual_dist < min_dist)
        {
                min_dist = actual_dist;
                closest = it;
        }
}

pointList.erase(closest);

Answer 4

If you are bound to use std::list data structure for your particular problem, then there is probably not much more apart from the answers you have received. Linear search of O(Nd) complexity, no complex data structure.

If on the other hand you are not convinced about the linear search and would like to try something different then consider the very broad domain of "Nearest Neighbour Search" research.

Answer 5

I agree with the previous solution, and just wanted to add another thought. Although your Point class isn't very large and so a copy isn't really a problem, you might consider using Point* for your list. This way, when you create your second list, you would store the pointer to the same class. The down-side of this would be if you were deleting from multiple lists without a "master" that manages all created points, you could either create a memory leak if you didn't delete the underlying class or accidentally delete a class that was still being used in another list. Something to consider, though, depending on how your system evolves.

Answer 6

You can do this using a combination of the STL and Boost.Iterators and Boost.Bind -- I'm pasting the whole source of the solution to your problem here for your convenience:

#include <list>
#include <cmath>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/bind.hpp>
#include <cassert>

using namespace std;
using namespace boost;

struct Point {
    int x, y;
    Point() : x(0), y(0) {}
    Point(int x1, int y1) : x(x1), y(y1) {}
    Point(Point const & other) : x(other.x), y(other.y) {}
    Point & operator=(Point rhs) { rhs.swap(*this); return *this; }
    void swap(Point & other) { std::swap(other.x, x); std::swap(other.y, y); }
};

double point_distance(Point const & first, Point const & second) {
    double x1 = first.x;
    double x2 = second.x;
    double y1 = first.y;
    double y2 = second.y;
    return sqrt( ((x2 - x1) * (x2 -x1)) + ((y2 - y1) * (y2 - y1)) );
}

int main(int argc, char * argv[]) {
    list<Point> points;
    points.push_back(Point(1, 1));
    points.push_back(Point(2, 2));
    points.push_back(Point(3, 3));
    Point source(0, 0);
    list<Point>::const_iterator closest = 
        min_element(
                make_transform_iterator(
                    points.begin(),
                    bind(point_distance, source, _1)
                    ),
                make_transform_iterator(
                    points.end(),
                    bind(point_distance, source, _1)
                    )
                ).base();
    assert(closest == points.begin());
    return 0;
}

The meat of the solution is to transform each element in the list using the transform iterator using the point_distance function and then get the minimum distance from all the distances. You can do this while traversing the list, and in the end reach into the transform_iterator to get the base iterator (using the base() member function).

Now that you have that iterator, you can replace the assert(closest == points.begin()) with points.erase(closest).