STD::List 内の x、y に最も近い「Point」オブジェクトを削除するにはどうすればよいですか?

Question

次のようなポイントクラスがあります。

class Point {
public:
    int x, y;
    Point(int x1, int y1)
    {
        x = x1;
        y = y1;
    }
};

そしてポイントのリスト:

std::list <Point> pointList;
std::list <Point>::iterator iter;

ポイントを pointList にプッシュしています (ただし、まだポイントがプッシュされていない場合、リストにはまだポイントが含まれていない可能性があります)。

質問が 2 つあります。

リストから任意の (x, y) に最も近い点を削除するにはどうすればよいですか?

x,y (5,12) があり、その点に最も近いリスト内の点を見つけて、STD::List から削除したいとします。

距離式を使用する必要があり、反復子を使用してリストを反復処理する必要があることはわかっていますが、リストを反復処理するときにどの点が最も近いかをどのように追跡するかを概念化するのに少し苦労しています。 。

指定された (x,y) の x 半径内の点の配列またはリストを返すにはどうすればよいですか?

最後の質問と似ていますが、指定された (x,y) の半径 5 以内にある「Point」オブジェクトへのポインターのリストが必要です。また、配列またはリストを返す必要がありますか?

誰かが私を助けてくれたら、私はまだ C++ を習得するのに苦労しているので、感謝します。

Answer 1

リストをごループとして最も近い点を追跡するためにはstd ::リスト::イテレータ変数を使用します。あなたがリストの最後に到達すると、それは最も近い点が含まれていますし、アイテムを消去するために使用することができます。

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のことに注意してください大きさの正方形はこれらの比較のために同じようにうまく機能するので、あなたが余分なパフォーマンスが必要な場合は削除することができます。また、あなたは本当にクワッド。第一の問題と密接衝突検出するに関連し、そのトピックについての貴重な情報のトンがあるさ利用可能。の

Answer 2

あなたはそれがなされるべきかについて正しいです。ただ、リスト内のすべての項目を反復処理し、すでに見つかっ最小距離、あなたは問題がそう述べている場合は、それ自体でポイントと一致していないことを確認すること、二つの変数で見つかった最も近い点を追跡します。それからちょうどあなたが見つけポイントを削除します。

どのようにこれが正確に行われていることは、運動として保持されます。

あなたが別のポイントから与えられた半径内のポイントのリストを取得したい場合は、

、リストを反復処理し、指定された範囲内でのみポイントを含む第二のリストを作成します。

ここでも、それがコードで作られてどのように練習として、あなたに任されています。

Answer 3

これは、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).

Answer 4

同意する前の溶液<url> <url> <url> <url> <url> <url> <url> <url> <url> <url>を追加した。がポイントクラスな非常に大きい写しいなだけじゃない傷を付けても問題あると考えポイント※お一覧です。このように作成する場合、第二のリスト、お店へのポインタと同じクラスです。下側のこうした場合は削除する複数のリストな"マスター"を管理するすべての作成ポイント、いずれかをメモリリークを行わなかった場合は削除の基本となるクラスや誤って削除クラスが使われ、別の一覧です。何かを考えるが、どのように設定するかは、システムの進化

Answer 5

あなたは後でそれを削除するイテレータを維持する必要があります。

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);