如何刪除某個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())。