كيف يمكنني حذف أقرب كائن "نقطة" في قائمة STD :: إلى بعض X، Y؟

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;

أنا أدفع نقاط إلى بقائمة موجزة (على الرغم من أن القائمة قد لا تحتوي على نقاط بعد إذا لم يتم دفع أي شيء بعد).

لدي سؤالان:

كيف يمكنني حذف أقرب نقطة إلى بعض التعسفي (x، y) من القائمة؟

دعنا نقول أن لدي X، Y (5،12) وأريد أن أجد النقطة في القائمة الأقرب إلى تلك النقطة وإزالتها من قائمة STD ::

أعلم أنني سأضطر إلى استخدام صيغة المسافة وسوف أضطر إلى التكرار من خلال القائمة باستخدام جهاز كمتضائي لكنني أواجه بعض المتاعب تصور كيف سآخذ هذه النقطة هي الأقرب في القائمة وبعد

كيف يمكنني إرجاع مجموعة أو قائمة النقاط داخل دائرة نصف قطرها X معين (X، Y)؟

على غرار السؤال الأخير إلا أنني بحاجة إلى قائمة من المؤشرات على كائنات "النقطة" ضمن القول 5 نصف قطرها المعطى (X، Y). أيضا، هل يجب علي إرجاع مجموعة أو قائمة؟

إذا كان بإمكان أي شخص مساعدتي، ما زلت أعوض طريقي من خلال C ++ وأنا أقدر ذلك.

Answer 1

استخدم المتغير STD :: INERATOR لتتبع أقرب نقطة عند حلقة من خلال القائمة. عند الوصول إلى نهاية القائمة، سيحتوي على أقرب نقطة ويمكن استخدامها لمحو العنصر.

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. يمكن إزالتها إذا كنت بحاجة إلى أداء إضافي لأن مربع حجم الحجم يعمل أيضا لهذه المقارنات. أيضا، إذا كنت ترغب حقا في زيادة الأداء من النظر في بنية بيانات تسمح بتقسيم المشهد مثل quadtree. وبعد المشكلة الأولى مرتبطة ارتباطا وثيقا اكتشاف الاصطدام وهناك طن من المعلومات القيمة حول هذا الموضوع المتاحة.

Answer 2

أنت على حق كيفية إجراء ذلك. تكرر فقط من خلال جميع العناصر الموجودة في القائمة وتتبع أصغر مسافة وجدت بالفعل، وأقرب نقطة وجدت في متغيرتين، والتأكد من أنك لا تتطابق مع النقطة مع نفسها إذا كانت المشكلة تنص على ذلك. ثم مجرد حذف النقطة التي وجدتها.

كيف يتم الاحتفاظ بهذا بالضبط كممارسة.

إذا كنت ترغب في الحصول على قائمة من النقاط في دائرة نصف قطرها معينة من نقطة أخرى، قم بتكرير القائمة وبناء قائمة ثانية تحتوي فقط على النقاط داخل النطاق المحدد.

مرة أخرى، كيف يتم تركك في التعليمات البرمجية لك كممارسة تمرين.

Answer 3

يمكنك القيام بذلك باستخدام مزيج من STL و تعزيز و boost.bind. - أنا جعل المصدر بأكمله للحل لمشكلتك هنا لراحتك:

#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;
}

لحوم الحل هو تحويل كل عنصر في القائمة باستخدام محول IMERATOR باستخدام point_distance وظيفة ثم احصل على الحد الأدنى للمسافة من جميع المسافات. يمكنك القيام بذلك أثناء اجتياز القائمة، وفي النهاية تصل إلى transform_iterator للحصول على قاعدة التدريب الأساسية (باستخدام base() وظيفة الأعضاء).

الآن بعد أن لديك هذا الماء، يمكنك استبدال assert(closest == points.begin()) مع points.erase(closest).

Answer 4

وأنا أتفق مع الحل السابق، وأردت فقط إضافة فكر آخر. على الرغم من أن فئة النقاط ليست كبيرة جدا، إلا أن النسخة ليست مشكلة حقا، فقد تفكر في استخدام النقطة * لقائمتك. بهذه الطريقة، عند إنشاء قائمتك الثانية، يمكنك تخزين المؤشر إلى نفس الفصل. سيكون الجانب الخلفي من هذا إذا كنت حذف من قوائم متعددة دون "ماجستير" يدير جميع النقاط التي تم إنشاؤها، فيمكنك إما إنشاء تسرب للذاكرة إذا لم تقم بحذف الطبقة الأساسية أو حذف فئة غير قابلة للسلطة يجري استخدامها في قائمة أخرى. شيء يجب مراعاته، اعتمادا على كيفية تطور نظامك.

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