How to delete the nearest "Point" object in STD :: List to some x, y?

Question

I have a point class, for example:

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

and list of points:

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

I click the dots on my pointList (although the list may not contain points if none were clicked).

I have two questions:

How can I remove the nearest point for some arbitrary (x, y) from a list?

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

I know that I will have to use the distance formula and I will have to iterate over the list using an iterator, but I have some problems conceptualizing how I will keep track of which point is the closest when I repeat through the list.

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

Similar to the last question, except that I need a list of pointers to Point objects within the 5th radius of the given (x, y). Also, should an array or list be returned?

If anyone can help me, I'm still trying to get through C ++, and I appreciate that.

Answer 1

Use the std :: list :: iterator variable to keep track of the closest point as you go through the list. When you get to the end of the list, it will contain the nearest point and can be used to delete an 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 the radius of a given point is similar. Note that an empty radius list is passed to the function by reference. Adding points to the list by reference eliminates the need to copy all points when returning a 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); } } } 

Use a copy again 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 - px, 2) + pow(center_.y - py, 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 sqrt can be removed if you need extra performance, as the squared value works just as well for these comparisons. Also, if you really want to improve performance, than consider a data structure that allows you to split scenes like quadtree . The first issue is closely related to conflict detection , and there is a lot of useful information about this topic.

Answer 2

You are right about how to do this. Just iterate over all the items in the list and track the smallest distance traveled and the closest point that you found in the two variables, making sure that you don't agree with the point with yourself if the problem claims it. Then simply delete the found point.

How it is exactly done is saved 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 points in the specified range.

Again, as this is done in code, you are left with the exercise.

Answer 3

You can do this using a combination of STL and Boost.Iterators and Boost.Bind - I am applying the entire 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 solution ball is to convert each item to a list using the conversion iterator using the point_distance function, and then get the minimum distance from all distances. You can do this by going through the list, and eventually go to transform_iterator to get the base iterator (using the base() member function).

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

Answer 4

You must save the iterator to remove it later.

 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 5

I agree with the previous decision and just wanted to add one more thought. Although your Point class is not very large and therefore the copy is not really a problem, you might consider using Point * for your list. Thus, when creating a second list, you will keep the pointer to the same class. The downside of this would be if you deleted from multiple lists without a “wizard” that manages all the created points, you could either create a memory leak if you didn’t delete the base class or accidentally delete a class that was still used in another the list. Something to consider, depending on how your system evolves.