Come è possibile eliminare l'oggetto più vicino “Punto” in uno std :: list per qualche x, y?
https://stackoverflow.com/questions/538711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho una classe punto, come:
class Point {
public:
int x, y;
Point(int x1, int y1)
{
x = x1;
y = y1;
}
};
e un elenco di punti:
std::list <Point> pointList;
std::list <Point>::iterator iter;
sto spingendo punti alla mia pointList (anche se la lista potrebbe contenere Non hai punti se nessuno è stato ancora spinto).
Ho due domande:
Come faccio a cancellare il punto più vicino a qualche arbitraria (x, y) dalla lista?
Diciamo che ho la x, y (5,12) e voglio trovare il punto nell'elenco più vicino a quel punto e rimuoverlo dalla lista std ::.
So che dovrò utilizzare la formula della distanza e dovrò per scorrere l'elenco utilizzando un iteratore ma sto avendo qualche problema concettualizzare come mi terrò al corrente di che punto è il più vicino come ho iterare l'elenco.
Come posso restituire un array o una lista di punti all'interno x raggio di un dato (x, y)?
Simile a quest'ultima domanda, tranne Ho bisogno di una lista di puntatori agli oggetti "punto" entro dicono 5 raggio di un dato (x, y). Inoltre, dovrei restituire un array o un elenco?
Se qualcuno mi può aiutare, sto ancora lottando la mia strada attraverso C ++ e lo apprezzo.
Soluzione
Utilizzare una variabile list :: iterator std :: per tenere traccia del punto più vicino come si esegue un ciclo attraverso la lista. Quando si arriva alla fine della lista conterrà il punto più vicino e può essere utilizzato per cancellare la voce.
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);
}
}
Costruzione di un elenco di punti entro un raggio di un dato punto è simile. Si noti che un elenco di raggio vuoto viene passato alla funzione per riferimento. Sommando i punti all'elenco con riferimento eliminerà la necessità per la copia di tutti i punti in cui la restituzione del vettore per valore.
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);
}
}
}
Anche in questo caso utilizzando la copia 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));
}
Si noti che il sqrt può essere rimosso se avete bisogno di prestazioni dal momento che il quadrato della grandezza funziona altrettanto bene per questi confronti. Inoltre, se si vuole veramente aumentare le prestazioni di prendere in considerazione una struttura dati che permette di scena il partizionamento come un quadtree . Il primo problema è strettamente legato al rilevamento delle collisioni e c'è un sacco di informazioni preziose su questo argomento disponibili.
Altri suggerimenti
Hai ragione su come dovrebbe essere fatto. Basta scorrere tutti gli elementi dell'elenco e tenere traccia della distanza minima già trovato, e il punto più vicino si trova in due variabili, facendo attenzione a non corrisponde al punto con se stesso se il problema si afferma così. Poi basta eliminare il punto che hai trovato.
Come questo è esattamente fatto è conservato come un esercizio.
Se si desidera ottenere un elenco di punti in un determinato raggio da un altro punto, scorrere la lista e costruire un secondo elenco contenente solo i punti all'interno del campo specificato.
Ancora una volta, come è fatto nel codice viene lasciato a voi come un esercizio.
È possibile farlo utilizzando una combinazione del STL e Boost.Iterators e Boost.Bind - sto incollando l'intero fonte della soluzione al vostro problema qui per comodità:
#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 carne della soluzione è quello di trasformare ogni elemento della lista utilizzando l'iteratore trasformazione utilizzando la funzione point_distance e quindi ottenere la distanza minima da tutte le distanze. È possibile farlo durante l'attraversamento della lista, e alla fine raggiungere nel transform_iterator per ottenere l'iteratore di base (utilizzando la funzione di membro base()).
Ora che avete che iteratore, è possibile sostituire il assert(closest == points.begin()) con points.erase(closest).
Sono d'accordo con la soluzione precedente, e solo voluto aggiungere un altro pensiero. Anche se la classe Point non è molto grande e quindi una copia non è davvero un problema, si potrebbe considerare l'utilizzo Point * per la vostra lista. In questo modo, quando si crea il secondo elenco, si dovrebbe memorizzare il puntatore alla stessa classe. Il rovescio della medaglia di questo sarebbe se si stesse cancellando da più liste senza un "master" che gestisce tutti i punti creati, si potrebbe creare una perdita di memoria se non si elimina la classe sottostante o accidentalmente elimina una classe che era ancora essere utilizzato in un altro elenco. Qualcosa da considerare, però, a seconda di come il sistema si evolve.
È necessario mantenere l'iteratore per eliminarlo successivamente.
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);
