أقصر مسافة بين النقطة والمسار

Question

بالنسبة إلى لعبة عبر الإنترنت مقرها الجيولوجي ، أبحث عن خوارزمية تجد أقصر مسافة بين نقطة محددة ومسار معروف متصلًا بواسطة X/Y-coordinates ، حتى أتمكن من قتل جميع النقاط/العقد الزائدة. رابط أو كلمة رئيسية لهذه الخوارزمية من شأنه أن يساعدني كثيرًا! شكرا للقراءة

من أجل فهم أفضل:

Answer 1

هل ترغب في حساب هذا من أجل قول شيء مثل "إذا كانت المسافة من نقطة إلى مسار صفر ، ثم إزالة النقطة"؟ إذا كان الأمر كذلك ، فربما تكون هناك طريقة أسهل لإزالة العقد الزائدة. خذ النقاط الثالثة في وقت واحد (اتصل بهم A, B, ، و C). حساب الزاوية بين A و B, ، وكذلك الزاوية بين B و C. إذا كانت الزاويتان متماثلين ، فأني B يكمن في الطريق بين A و C وهو زائد. يمكنك استخدام وظيفة "ATAN2" (أو ما يعادل لغتك) للقيام بحسابات الزاوية.

Answer 2

هذه خوارزمية لإنشاء المسار من نقطة إلى نقطة تستخدم عادة في الألعاب:

خوارزمية البحث*

قد تحتاج إلى تطبيقه عدة مرات بين وجهة نظرك ومسارك ، ولكنه سريع جدًا بشكل عام. تحتوي الخوارزمية على بعض التحسينات لشبكات الخرائط (حيث تكون المسافات بين المربعات أعداد صحيحة). هناك وصف لهذا في: برمجة لعبة الاستراتيجية في الوقت الحقيقي باستخدام MS DirectX 6.0 بقلم ميكي كويك.

خوارزمية Djikstra هي خوارزمية جيدة لتجد المسار من عقدة مصدر واحد إلى جميع العقد الأخرى في الرسم البياني. يمكنك إيقاف الخوارزمية عندما تجد ما تحتاجه - وهو ما سيكون في حالتك عندما وجدت الخوارزمية أقصر مسار لكل عقدة على المسار.

لا أعرف خوارزمية محددة "أقصر مسار من العقدة إلى المسار".

Answer 3

هذا هو تطبيق Java الخاص بي لأقرب نقطة على المسار

private Point getNearestPoint(Point from, List<Point> to_path) {

    int count = to_path.size();

    if (count == 0)
        return null;
    if (count == 1)
        return to_path.get(0);

    double nearest_dist = Double.MAX_VALUE;
    Point nearest_point = null;

    for (int i = 1; i < count; i++) {

        Point p1 = to_path.get(i-1);
        Point p2 = to_path.get(i);

        Point p = getNearestPointOnSegment(from, p1, p2);
        if (p != nearest_point) {
            double dist = dist(from, p);
            if (dist < nearest_dist) {
                nearest_dist = dist;
                nearest_point = p;
            }
        }
    }

    return nearest_point;
}

private Point getNearestPointOnSegment(Point from, Point p1, Point p2) {

    if (dist(p1, p2) < 1e3) {
        Log.d(TAG, "Points are near");
        return p1;
    }

    double d2 = dist2(p1, p2);
    double t = ((from.x - p1.x) * (p2.x - p1.x) + (from.y - p1.y) * (p2.y - p1.y)) / d2;

    if (t < 0) {
        //Log.d(TAG, "p1");
        return p1;
    }
    if (t > 1) {
        //Log.d(TAG, "p2");
        return p2;
    }

    //Log.d(TAG, "t:" + t);
    return new Point((int)(p1.x + t * (p2.x - p1.x)),
        (int)(p1.y + t * (p2.y - p1.y)));
}

private double dist(Point p1, Point p2) {
    return Math.sqrt(dist2(p1, p2));
}

private double dist2(Point p1, Point p2) {
    return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}

private double sqr(double x) {
    return x * x;
}