Wie kann ich das nächste „Point“ Objekt in einem STD :: Liste zu einigen x, y löschen?
https://stackoverflow.com/questions/538711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen Punkt Klasse wie:
class Point {
public:
int x, y;
Point(int x1, int y1)
{
x = x1;
y = y1;
}
};
und eine Liste von Punkten:
std::list <Point> pointList;
std::list <Point>::iterator iter;
Ich bin drängen Punkte auf meine Punktliste (obwohl die Liste keine Punkte enthalten könnte noch, wenn noch keiner geschoben wurde).
Ich habe zwei Fragen:
Wie kann ich den nächsten Punkt zu einem beliebigen (x, y) aus der Liste löschen?
Lassen Sie uns sagen ich die x haben, y (5,12) und ich möchte den Punkt in der Liste finden Nähe zu diesem Punkt und entfernen Sie sie aus dem STD :: Liste.
Ich weiß, ich werde die Entfernung Formel verwenden müssen, und ich werde durch die Liste zu durchlaufen haben einen Iterator verwenden, aber ich habe einige Mühe Konzeptionierung, wie ich im Auge behalten werden von diesem Punkt ist in der Nähe, wie ich iterieren durch die Liste.
Wie kann ich ein Array oder eine Liste von Punkten innerhalb x Radius eines bestimmten (x, y) zurückkehren?
Ähnlich wie bei der letzten Frage außer ich eine Liste von Zeigern auf die „Punkt“ Objekte müssen innerhalb sagen 5 Radius eines bestimmten (x, y). Außerdem soll ich ein Array oder eine Liste zurückgeben?
Wenn jemand kann mir helfen, ich bin meinen Weg durch C noch kämpfen ++ und ich schätze es.
Lösung
Verwenden Sie eine std :: list :: Iteratorvariable Spur des nächsten Punktes, wie Sie Schleife durch die Liste zu halten. Wenn Sie zum Ende der Liste zu bekommen wird es den nächsten Punkt enthalten und verwendet werden kann, um das Element zu löschen.
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);
}
}
Eine Liste von Punkten innerhalb eines Radius von einem bestimmten Punkt ähnlich ist. Beachten Sie, dass eine leere Liste Radius in die Funktion als Referenz übergeben wird. Addiert man die Punkte auf der Liste von Referenz beseitigt die Notwendigkeit, für alle Punkte zu kopieren, wenn Sie den Vektor nach Wert zurückkehrt.
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);
}
}
}
Auch mit Kopie, wenn:
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));
}
Beachten Sie, dass die sqrt können entfernt werden, wenn Sie sich zusätzliche Leistung benötigen, da das Quadrat der Größe ebenso gut für diese Vergleiche funktioniert. Auch, wenn Sie wirklich wollen, um die Leistung zu erhöhen als eine Datenstruktur zu berücksichtigen, die für die Szenen Partitionierung wie ein ermöglicht Quadtree . Das erste Problem ist eng verwandt mit Kollisionserkennung und es gibt eine Tonne von wertvollen Informationen zu diesem Thema zur Verfügung.
Andere Tipps
Sie haben Recht, wie sollte es gemacht werden. iterieren einfach durch alle Elemente in der Liste aus und verfolgt den kleinsten Abstand bereits gefunden, und den nächsten Punkt, der Sie in zwei Variablen gefunden, dafür, dass Sie mit mir selbst dem Punkt nicht überein, wenn das Problem so heißt es. Dann löschen Sie einfach den Punkt, den Sie gefunden.
Wie das genau gemacht wird als eine Übung gehalten.
Wenn Sie von einem anderen Punkt eine Liste von Punkten in einem bestimmten Radius zu erhalten, die Liste durchlaufen und eine zweite Liste baut nur die Punkte innerhalb des angegebenen Bereichs enthält.
Auch hier, wie es im Code gemacht hat als eine Übung für Sie links.
Sie können dies tun, eine Kombination aus der STL und Boost.Bind - ich bin die ganze Quelle der Lösung für Ihr Problem hier für Ihre Bequemlichkeit einfügen:
#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;
}
Das Fleisch der Lösung ist jedes Element in der Liste zu transformieren die Iterator-Transformation mit der point_distance-Funktion und dann den Mindestabstand von allen Entfernungen zu bekommen. Sie können diese während tun, um die Liste durchlaufen, und am Ende in die transform_iterator erreichen die Basis Iterator zu erhalten (mit der base() Member-Funktion).
Nun, da Sie diesen Iterator haben, können Sie die assert(closest == points.begin()) mit points.erase(closest) ersetzen.
Ich bin mit der bisherigen Lösung, und wollte nur einen anderen Gedanken hinzuzufügen. Obwohl Ihre Point-Klasse ist nicht sehr groß und so ist eine Kopie nicht wirklich ein Problem, könnte man mit Point * für Ihre Liste prüfen. Auf diese Weise, wenn Sie Ihre zweite Liste erstellen, würden Sie den Zeiger auf die gleiche Klasse speichern. Die Kehrseite davon sein würde, wenn Sie aus mehreren Listen ohne „Master“ Löschen wurden, die alle erstellten Punkte schafft, können Sie entweder einen Speicherverlust erstellen, wenn Sie nicht die zugrunde liegende Klasse gelöscht haben oder versehentlich eine Klasse löschen, die noch war wird in einer anderen Liste verwendet. Etwas zu prüfen, obwohl, je nachdem, wie Ihr System entwickelt.
Sie haben den Iterator halten es anschließend zu löschen.
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);
