Как мне удалить ближайший объект "Point" в STD :: List с некоторым x, y?

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;

Я добавляю точки в свой список точек (хотя список может еще не содержать точек, если они еще не были переданы).

У меня два вопроса:

Как я могу удалить ближайшую точку к некоторому произвольному (x, y) из списка?

Допустим, у меня есть x, y (5,12), и я хочу найти точку в списке, ближайшую к этой точке, и удалить ее из STD :: List.

Я знаю, что мне придется использовать формулу расстояния, и мне придется перебирать список с помощью итератора, но у меня возникают некоторые проблемы с концептуализацией того, как я буду отслеживать, какая точка является ближайшей при итерации через список.

Как я могу вернуть массив или список точек в радиусе x от заданного (x, y)?

Аналогично последнему вопросу, за исключением того, что мне нужен список указателей на объекты "Point" в пределах, скажем, 5 радиуса заданного (x, y). Кроме того, я должен вернуть массив или список?

Если кто-нибудь может мне помочь, я все еще пытаюсь пробиться через 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));
}

Обратите внимание, что sqrt можно удалить, если вам нужна дополнительная производительность, так как квадрат величины работает также хорошо для этих сравнений. Кроме того, если вы действительно хотите повысить производительность, рассмотрите структуру данных, которая допускает разбиение сцены, например quadtree . Первая проблема тесно связана с обнаружением столкновений , и имеется масса ценной информации по этой теме.

Answer 2

Вы можете сделать это, используя комбинацию 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).

Answer 3

Вы правы в том, как это нужно сделать. Просто переберите все элементы в списке и отследите наименьшее расстояние, которое уже найдено, и ближайшую точку, которую вы нашли в двух переменных, чтобы убедиться, что вы не сопоставляете точку с самим собой, если проблема об этом говорит Затем просто удалите найденную точку.

Как именно это сделано, сохраняется в качестве упражнения.

Если вы хотите получить список точек в данном радиусе из другой точки, выполните итерацию списка и создайте второй список, содержащий только точки в указанном диапазоне.

Опять же, как это сделано в коде, оставлено вам в качестве упражнения.

Answer 4

Я согласен с предыдущим решением и просто хотел добавить еще одну мысль. Хотя ваш класс Point не очень большой, и поэтому его копирование не является проблемой, вы можете рассмотреть возможность использования Point * для своего списка. Таким образом, когда вы создаете свой второй список, вы сохраняете указатель на тот же класс. Обратной стороной этого является то, что если вы удаляете из нескольких списков без «мастера», который управляет всеми созданными точками, вы можете создать утечку памяти, если не удалили базовый класс, или случайно удалить класс, который все еще используется в другом списке. Но кое-что нужно учитывать, в зависимости от того, как развивается ваша система.

Answer 5

Вы должны сохранить итератор, чтобы потом удалить его.

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