Como faço para excluir o objeto mais próximo “Point” em um std :: list para algum x, y?

Question

Eu tenho uma classe de pontos como:

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

e uma lista de pontos:

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

Eu estou empurrando pontos no meu pointList (embora a lista pode conter nenhum ponto ainda se nenhum ainda foi empurrado).

Eu tenho duas perguntas:

Como posso eliminar o ponto mais próximo a alguns arbitrário (x, y) na lista?

Vamos dizer que eu tenho o x, y (5,12) e eu quero encontrar o ponto na lista de mais próximo a esse ponto e removê-lo do std :: list.

Eu sei que vou ter que usar a fórmula de distância e eu vou ter que percorrer a lista usando um iterador, mas eu estou tendo alguns problemas conceptualização como eu vou manter o controle de qual ponto é o mais próximo que eu iterate através da lista.

Como posso retornar um array ou lista de pontos dentro x raio de um determinado (x, y)?

Semelhante à última pergunta, exceto eu preciso de uma lista de ponteiros para os objetos "point" dentro de digamos 5 raio de um determinado (x, y). Além disso, devo retornar um array ou uma lista?

Se alguém puder me ajudar, eu ainda estou lutando meu caminho através de C ++ e eu aprecio isso.

Answer 1

Use um std :: list :: iterator variável para acompanhar o ponto mais próximo como você percorrer a lista. Quando você chegar ao final da lista que conterá o ponto mais próximo e pode ser usado para apagar o 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);
    }
}

Criar uma lista de pontos dentro de um raio de um determinado ponto é similar. Note-se que uma lista vazia raio é transmitido para a função por referência. Adicionando os pontos para a lista por referência vai eliminar a necessidade de copiar todos os pontos ao retornar o vetor por valor.

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

Novamente usando cópia se:

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

Note que o sqrt pode ser removido se você precisar de performance extra desde o quadrado da magnitude funciona tão bem para essas comparações. Além disso, se você realmente quiser aumentar o desempenho de considerar uma estrutura de dados que permite o particionamento cena como um quadtree . O primeiro problema está intimamente relacionado com detecção de colisão e há uma tonelada de informações valiosas sobre o assunto disponíveis.

Answer 2

Você está certo sobre como deve ser feita. Apenas percorrer todos os itens na lista e faixa de manter a menor distância já encontrado, eo ponto mais próximo que você encontrou em duas variáveis, certificando-se de que você não coincidir com o ponto com a própria Se o problema estados assim. Em seguida, basta apagar o ponto que você encontrou.

Como isso é feito exatamente é mantido como um exercício.

Se você deseja obter uma lista de pontos em um determinado raio de um outro ponto, iterate a lista e construir uma segunda lista contendo apenas os pontos dentro do intervalo especificado.

Mais uma vez, como é feito no código é deixado para você como um exercício.

Answer 3

Você pode fazer isso usando uma combinação do STL e Boost.Iterators e Boost.Bind - estou colando toda a fonte da solução para o seu problema aqui para sua conveniência:

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

A carne da solução é transformar cada elemento da lista usando o iterador transformação usando a função point_distance e então obter a distância mínima de todas as distâncias. Você pode fazer isso ao atravessar a lista, e no alcance extremidade na transform_iterator para obter o iterador base (usando a função de membro base()).

Agora que você tem que iterator, você pode substituir o assert(closest == points.begin()) com points.erase(closest).

Answer 4

Eu concordo com a solução anterior, e só queria acrescentar outro pensamento. Apesar de sua classe Point não é muito grande e por isso uma cópia não é realmente um problema, você pode considerar o uso Point * para a sua lista. Desta forma, quando você cria a sua segunda lista, você iria armazenar o ponteiro para a mesma classe. O lado negativo disso seria se você estivesse apagar a partir de várias listas sem um "mestre" que gerencia todos os pontos criados, você poderia criar uma fuga de memória se você não excluir a classe subjacente ou excluir acidentalmente uma classe que ainda estava sendo usado em outra lista. Algo a considerar, no entanto, dependendo de como seu evolui sistema.

Answer 5

Você tem que manter o iterador para excluí-lo mais tarde.

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