std :: 목록에서 가장 가까운 "포인트"객체를 일부 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 :: 목록에서 제거하고 싶습니다.
나는 거리 공식을 사용해야한다는 것을 알고 있으며 반복기를 사용하여 목록을 반복해야하지만 목록을 반복 할 때 가장 가까운 지점을 추적하는 방법을 개념화하는 데 어려움을 겪고 있습니다. .
주어진 (x, y)의 x 반경 내의 배열 또는 점 목록을 어떻게 반환 할 수 있습니까?
주어진 (x, y)의 반경 5 반경 내에서 "포인트"객체에 대한 포인터 목록이 필요한 경우를 제외하고 마지막 질문과 유사합니다. 또한 배열이나 목록을 반환해야합니까?
누군가가 나를 도울 수 있다면, 나는 여전히 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);
}
}
주어진 지점의 반경 내에 점 목록을 구축하는 것은 비슷합니다. 빈 반경 목록은 참조별로 함수로 전달됩니다. 참조별로 목록에 포인트를 추가하면 벡터를 값으로 반환 할 때 모든 점을 복사 할 필요가 없습니다.
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);
}
}
}
다시 복사를 사용합니다.
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과 boost.iterators 그리고 부스트 - 나는 당신의 편의를 위해 당신의 문제에 대한 솔루션의 전체 소스를 여기에서 여기에 붙이고 있습니다.
#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).
나는 이전 해결책에 동의하고 다른 생각을 추가하고 싶었습니다. 포인트 클래스는 크지 않기 때문에 사본이 실제로 문제가되지 않지만 목록에 포인트*를 사용하는 것을 고려할 수 있습니다. 이렇게하면 두 번째 목록을 만들 때 포인터를 동일한 클래스에 저장합니다. 이 쪽의 다운 측은 생성 된 모든 포인트를 관리하는 "마스터"없이 여러 목록에서 삭제 한 경우 기본 클래스를 삭제하지 않으면 메모리 누출을 만들 수 있거나 실수로 여전히 한 클래스를 삭제할 수 있습니다. 다른 목록에서 사용됩니다. 그러나 시스템의 진화 방식에 따라 고려해야 할 사항이 있습니다.
나중에 삭제하려면 반복자를 유지해야합니다.
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);
