Como faço para excluir o objeto mais próximo “Point” em um std :: list para algum x, y?
Pergunta
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.
Solução
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.
Outras dicas
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.
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)
.
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.
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);