如何删除某个x，y的STD :: List中最接近的“Point”对象？

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半径内的“Point”对象的指针列表。另外，我应该返回一个数组或列表？

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

再次使用副本，如果：

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

注意，开方可以，如果你需要额外的性能，因为幅度的平方的作品一样好这些比较中移除。另外，如果您真的想要提高性能，则需要考虑允许场景分区的数据结构，如quadtree。第一个问题与collision detection密切相关，并且存在大量关于该主题的有价值的信息。

Answer 2

你是对的应该如何做。只需遍历列表中的所有项目，并跟踪已找到的最小距离以及您在两个变量中找到的最近点，如果问题状态如此，请确保您与自身不匹配。然后删除你找到的点。

这是如何准确地作为练习。

如果要从另一个点获取给定半径内的点的列表，请迭代列表并构建仅包含指定范围内的点的第二个列表。

再说一遍，它是如何在代码中作为练习留给你的。

Answer 3

你必须保持迭代器以后删除它。

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

我同意以前的解决方案，只是想添加另一个想法。虽然你的Point类不是很大，所以副本并不是一个真正的问题，但你可以考虑使用Point *作为你的列表。这样，当你创建你的第二个列表时，你会将指针存储到同一个类中。如果你从多个列表中删除没有管理所有创建点的“主”，那么你可以创建一个内存泄漏，如果你没有删除底层类或者意外删除了一个仍然存在的类被用在另一个列表中。要考虑的事情，取决于你的系统如何发展。

Answer 5

可以使用STL的组合，并且这样做​​和Boost.Bind - 我粘贴解决方案的整个源代码到你的问题就在这里为您提供方便：

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

解决方案的肉是使用变换迭代器使用point_distance函数变换列表中的每个元素，然后从所有距离中获得最小距离。您可以在遍历列表时完成此操作，最后到达transform_iterator以获取基础迭代器（使用base()成员函数）。

现在您已经有了该迭代器，您可以用points.erase(closest)替换assert(closest == points.begin())。