Как мне удалить ближайший объект “Point” в STD::List к некоторым x, y?
https://stackoverflow.com/questions/538711
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть класс точек, такой как:
class Point {
public:
int x, y;
Point(int x1, int y1)
{
x = x1;
y = y1;
}
};
и список пунктов:
std::list <Point> pointList;
std::list <Point>::iterator iter;
Я добавляю точки в свой список точек (хотя список может еще не содержать точек, если ни одна из них еще не была введена).
У меня есть два вопроса:
Как я могу удалить ближайшую точку к некоторому произволу (x, y) из списка?
Допустим, у меня есть x, y (5,12), и я хочу найти точку в списке, ближайшую к этой точке, и удалить ее из STD::List .
Я знаю, что мне придется использовать формулу расстояния, и мне придется выполнять итерации по списку с помощью итератора, но у меня возникли некоторые проблемы с концептуализацией того, как я буду отслеживать, какая точка находится ближе всего, при выполнении итерации по списку.
Как я могу вернуть массив или список точек в радиусе x от заданного (x, y)?
Аналогично последнему вопросу, за исключением того, что мне нужен список указателей на "точечные" объекты в радиусе, скажем, 5 от заданного (x, y).Кроме того, должен ли я возвращать массив или Список?
Если кто-нибудь может мне помочь, я все еще пробиваюсь через C ++, и я ценю это.
Решение
Используйте переменную std::list::iterator, чтобы отслеживать ближайшую точку при циклическом просмотре списка.Когда вы дойдете до конца списка, он будет содержать ближайшую точку и может быть использован для удаления элемента.
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);
}
}
Аналогично строится список точек в радиусе от заданной точки.Обратите внимание, что пустой список radius передается в функцию по ссылке.Добавление точек в список по ссылке устранит необходимость копирования всех точек при возврате вектора по значению.
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);
}
}
}
Снова используя copy, если:
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));
}
Обратите внимание, что sqrt ( площадь ) может быть удален, если вам нужна дополнительная производительность, поскольку квадрат величины работает так же хорошо для этих сравнений.Кроме того, если вы действительно хотите повысить производительность, рассмотрите структуру данных, которая допускает разделение сцены, например квадродерево.Первая проблема тесно связана с обнаружение столкновений и существует масса ценной информации по этой теме.
Другие советы
Вы правы в том, как это должно быть сделано.Просто выполните итерацию по всем элементам в списке и отслеживайте наименьшее уже найденное расстояние и ближайшую точку, которую вы нашли в двух переменных, убедившись, что вы не сопоставили точку с самой собой, если так указано в задаче.Затем просто удалите найденную точку.
Как именно это делается, приведено в качестве упражнения.
Если вы хотите получить список точек в заданном радиусе из другой точки, повторите список и создайте второй список, содержащий только точки в пределах указанного диапазона.
Опять же, то, как это делается в коде, остается вам в качестве упражнения.
Вы можете сделать это, используя комбинацию STL и Повышение.Итераторы и Подталкивать.Привязывать -- Я вставляю весь исходный код решения вашей проблемы сюда для вашего удобства:
#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;
}
Суть решения заключается в преобразовании каждого элемента в списке с помощью итератора преобразования с использованием point_distance выполните функцию, а затем получите минимальное расстояние из всех расстояний.Вы можете сделать это во время обхода списка, и в конце концов добраться до transform_iterator чтобы получить базовый итератор (используя base() функция-член).
Теперь, когда у вас есть этот итератор, вы можете заменить assert(closest == points.begin()) с points.erase(closest).
Я согласен с предыдущим решением и просто хотел добавить еще одну мысль.Хотя ваш класс Point не очень большой, и поэтому копирование на самом деле не проблема, вы могли бы рассмотреть возможность использования Point * для вашего списка.Таким образом, когда вы создадите свой второй список, вы сохраните указатель на тот же класс.Недостатком этого было бы то, что если бы вы удаляли из нескольких списков без "мастера", который управляет всеми созданными точками, вы могли бы либо создать утечку памяти, если бы не удалили базовый класс, либо случайно удалить класс, который все еще использовался в другом списке.Однако есть кое-что, что следует учитывать, в зависимости от того, как развивается ваша система.
Вы должны сохранить итератор, чтобы впоследствии удалить его.
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);
