Comment puis-je supprimer le plus proche objet « Point » dans une std :: Liste à certains x, y?
https://stackoverflow.com/questions/538711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une classe de points comme:
class Point {
public:
int x, y;
Point(int x1, int y1)
{
x = x1;
y = y1;
}
};
et une liste de points:
std::list <Point> pointList;
std::list <Point>::iterator iter;
Je pousse points à mon PointList (bien que la liste peut contenir aucun point encore si aucun n'a encore été poussé).
J'ai deux questions:
Comment puis-je supprimer le point le plus proche de certains arbitraire (x, y) de la liste?
Disons que je les x, y (5,12) et je veux trouver le point dans la liste la plus proche de ce point et le retirer de la STD :: Liste.
Je sais que je vais devoir utiliser la formule de la distance et je vais devoir parcourir la liste en utilisant un itérateur mais je vais avoir quelques problèmes conceptualiser comment je vais garder une trace de quel point est le plus proche que j'itérer dans la liste.
Comment puis-je retourner un tableau ou d'une liste de points dans un rayon X d'un (x, y)?
Dans le même à la dernière question, sauf que je besoin d'une liste de pointeurs vers les objets « Point » dans 5 dire d'un rayon donné (x, y). Aussi, dois-je retourner un tableau ou une liste?
Si quelqu'un peut me aider, je me bats toujours mon chemin à travers C ++ et je l'apprécie.
La solution
Utilisez une variable std :: liste :: iterator de garder une trace de la boucle point le plus proche que vous la liste. Lorsque vous arrivez à la fin de la liste, il contiendra le point le plus proche et peut être utilisé pour effacer l'élément.
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);
}
}
Construire une liste de points dans un rayon d'un point donné est similaire. Notez qu'une liste de rayon vide est passée dans la fonction par référence. Ajout de points à la liste par référence éliminera la nécessité de copier tous les points lors du retour du vecteur par valeur.
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);
}
}
}
Encore une fois en utilisant copie si:
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));
}
Notez que sqrt peut être retiré si vous avez besoin de performances supplémentaires depuis la place de l'ampleur fonctionne aussi bien pour ces comparaisons. En outre, si vous voulez vraiment augmenter les performances que de considérer une structure de données qui permet le partitionnement de la scène comme un quadtree . Le premier problème est étroitement lié à détection de collision et il y a une tonne d'informations précieuses sur ce sujet disponible.
Autres conseils
Vous avez raison sur la façon dont il devrait être. Il suffit de parcourir tous les éléments de la liste et de garder une trace de la plus petite distance déjà trouvé, et le point le plus proche que vous avez trouvé à deux variables, en vous assurant de ne correspond pas au point avec lui-même si le problème dit ainsi. Ensuite, il suffit de supprimer le point que vous avez trouvé.
Comment est-ce exactement fait est conservé comme un exercice.
Si vous voulez obtenir une liste de points dans un rayon donné d'un autre point, itérer la liste et de construire une deuxième liste contenant uniquement les points dans la plage spécifiée.
Encore une fois, comment il est fait dans le code reste à vous comme un exercice.
Vous pouvez le faire en utilisant une combinaison de la STL et Boost.Bind - Je coller toute la source de la solution à votre problème pour votre commodité:
#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;
}
La viande de la solution est de transformer chaque élément de la liste à l'aide de la transformée iterator en utilisant la fonction point_distance puis obtenir la distance minimale de toutes les distances. Vous pouvez le faire en parcourant la liste, et à la fin atteindre dans le transform_iterator pour obtenir le iterator de base (en utilisant la fonction de membre de base()).
Maintenant que vous avez cette iterator, vous pouvez remplacer le assert(closest == points.begin()) avec points.erase(closest).
Je suis d'accord avec la solution précédente, et je voulais juste ajouter une autre pensée. Bien que votre classe Point est pas très grande et donc une copie est pas vraiment un problème, vous pouvez envisager d'utiliser Point * pour votre liste. De cette façon, lorsque vous créez votre deuxième liste, vous pouvez stocker le pointeur à la même classe. Le bas-côté de ceci serait si vous supprimez de plusieurs listes sans « maître » qui gère tous les points créés, vous pouvez soit créer une fuite de mémoire si vous n'avez pas supprimé la classe sous-jacente ou de supprimer accidentellement une classe qui était encore utilisé dans une autre liste. Quelque chose à considérer, cependant, selon la façon dont votre système évolue.
Vous devez garder l'itérateur de le supprimer par la suite.
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);
