4

我有一个点类，如：

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

如果有人可以帮助我，我仍然在 C++ 中苦苦挣扎，我很感激。

4

5 回答 5

6

在循环遍历列表时，使用 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));
}

请注意，如果您需要额外的性能，可以删除sqrt ，因为幅度的平方同样适用于这些比较。此外，如果您真的想提高性能而不是考虑允许像四叉树这样的场景分区的数据结构。第一个问题与碰撞检测密切相关，并且有大量关于该主题的有价值信息可用。

于 2009-02-11T21:02:07.660 回答
3

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

这究竟是如何制作的，留作练习。

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

同样，它是如何在代码中生成的，留给您作为练习。

于 2009-02-11T20:59:35.497 回答
3

您可以使用 STL 和Boost.Iterators和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()成员函数）。

现在你有了那个迭代器，你可以assert(closest == points.begin())用points.erase(closest).

于 2009-02-11T22:02:01.400 回答
0

您必须保留迭代器以在之后将其删除。

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);
于 2009-02-11T21:03:38.590 回答
0

我同意以前的解决方案，只是想添加另一个想法。尽管您的 Point 类不是很大，因此副本并不是真正的问题，但您可以考虑将 Point* 用于您的列表。这样，当您创建第二个列表时，您将存储指向同一类的指针。这样做的缺点是，如果您从多个列表中删除而没有管理所有创建点的“主”，则如果您没有删除基础类或意外删除仍然存在的类，则可能会造成内存泄漏在另一个列表中使用。不过，需要考虑的事情取决于您的系统如何发展。

于 2009-02-11T21:19:54.853 回答