¿Cómo se elimina el objeto más cercano “Punto” en un std :: Lista de algunos x, y?
https://stackoverflow.com/questions/538711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo una clase de punto como:
class Point {
public:
int x, y;
Point(int x1, int y1)
{
x = x1;
y = y1;
}
};
y una lista de puntos:
std::list <Point> pointList;
std::list <Point>::iterator iter;
Estoy empujando puntos a mi PointList (aunque la lista podría contener ningún punto sin embargo, si ninguno de ellos ha sido empujado aún).
Tengo dos preguntas:
¿Cómo puedo eliminar el punto más cercano a algún arbitrario (x, y) de la lista?
Digamos que tengo las x, y (5,12) y quiero encontrar el punto de la lista más cercano a ese punto y quitarlo de la lista de enfermedades de transmisión sexual ::.
sé que voy a tener que usar la fórmula de la distancia y voy a tener que recorrer la lista mediante un iterador pero estoy teniendo algunos problemas para conceptualizar cómo voy a perder de vista que el punto es el más cercano que yo iterar a través de la lista.
¿Cómo puedo devolver una matriz o una lista de puntos dentro de un radio de x de un dado (x, y)?
Al igual que en la pregunta anterior, excepto que necesito una lista de punteros a los objetos "punto" dentro de un radio de 5 dicen de un dado (x, y). Además, debería devolver una matriz o una lista?
Si alguien me puede ayudar a cabo, todavía estoy luchando por mi camino a través de C ++ y lo aprecio.
Solución
Utilice un std :: vector-lista :: iterador para no perder de vista el punto más cercano a medida que recorrer la lista. Al llegar al final de la lista que contendrá el punto más cercano y se puede utilizar para borrar el elemento.
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);
}
}
construcción de una lista de puntos dentro de un radio de un punto dado es similar. Tenga en cuenta que una lista de radio de vacío se pasa a la función por referencia. La adición de los puntos de la lista por referencia eliminará la necesidad de copiar todos los puntos al devolver el vector 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);
}
}
}
Una vez más utilizando la copia 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));
}
Tenga en cuenta que el sqrt se puede eliminar si se necesita la capacidad ya que el cuadrado de la magnitud funciona igual de bien para estas comparaciones. Además, si usted realmente desea aumentar el rendimiento de considerar una estructura de datos que permite la partición de la escena como un árbol cuádruple . El primer problema está estrechamente relacionado con detección de colisiones y hay un montón de información valiosa acerca de ese tema disponible.
Otros consejos
Estás justo en la forma en que debe hacerse. Sólo iterar a través de todos los elementos de la lista y hacer un seguimiento de la distancia más pequeña ya encontrado, y el punto más cercano que encontró en dos variables, asegurándose de que no hace coincidir el punto consigo mismo si el problema indique así. A continuación, sólo eliminar el punto de que pueda encontrar.
¿Cómo se hace esto exactamente se mantiene como un ejercicio.
Si desea obtener una lista de puntos en un radio determinado desde otro punto, recorrer la lista y construir una segunda lista que contiene sólo los puntos dentro del rango especificado.
Una vez más, como se hace en el código se deja a usted como un ejercicio.
Usted puede hacer esto mediante una combinación de la STL y y href="http://www.boost.org/doc/libs/1_38_0/libs/bind/bind.html" rel="nofollow noreferrer"> Boost.Bind - estoy pegando toda la fuente de la solución a su problema aquí para su conveniencia:
#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 de la solución es transformar cada elemento de la lista utilizando el iterador transformada mediante la función point_distance y luego obtener la distancia mínima desde todas las distancias. Usted puede hacer esto al recorrer la lista, y al final llegar a la transform_iterator para obtener el iterador de base (usando la función miembro base()).
Ahora que tiene que iterador, puede reemplazar la assert(closest == points.begin()) con points.erase(closest).
Estoy de acuerdo con la solución anterior, y sólo quería añadir otro pensamiento. A pesar de su clase Point no es muy grande y por lo que una copia no es realmente un problema, es posible considerar el uso de Punto * para su lista. De esta manera, cuando usted crea su segunda lista, que sería almacenar el puntero a la misma clase. La desventaja de esto sería si estuviera borrando desde múltiples listas sin un "maestro" que gestiona todos los puntos creados, se puede crear ya sea una pérdida de memoria si no se elimina la clase subyacente o por accidente borra una clase que todavía estaba siendo utilizado en otra lista. Algo a tener en cuenta, sin embargo, dependiendo de cómo evoluciona su sistema.
Hay que mantener el iterador para eliminarlo después.
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);
