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

Question

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

كيف أقوم بذلك؟ من الواضح أن الطريقة التافهة هي حساب كل مسافة ، لكنني بحاجة إلى خوارزمية أخرى للمقارنة.

Answer 1

http://en.wikipedia.org/wiki/closest_pair_of_points

يمكن حل المشكلة في وقت O (n log n) باستخدام مقاربة الفجوة والقهر العودية ، على سبيل المثال ، على النحو التالي:

• فرز النقاط على طول الإحداثيات X
• اقسم مجموعة النقاط إلى مجموعتين فرعيتين متساويتين بواسطة خط عمودي x = xmid
• حل المشكلة بشكل متكرر في مجموعات فرعية اليسار واليمين. هذا سوف يعطي المسافات اليسرى والجزء الأيمن الحد الأدنى DLMIN و DRMIN على التوالي.
• ابحث عن الحد الأدنى من المسافة dlrmin بين زوج النقاط التي تقع فيها نقطة واحدة على يسار العمودي المقسم والنقطة الثانية تقع على اليمين.
• الجواب النهائي هو الحد الأدنى بين DLMIN و DRMIN و DLRMIN.

Answer 2

لا يمكنني التفكير على الفور في بديل أسرع من تقنية القوة الغاشمة (على الرغم من أنه يجب أن يكون هناك الكثير) ولكن مهما كانت الخوارزمية تختارها لا حساب المسافة بين كل نقطة. إذا كنت بحاجة إلى مقارنة المسافات فقط قارن مربعات من المسافات لتجنب الجذر التربيعي باهظ الثمن ومتكرر تمامًا.

Answer 3

يتمثل أحد الاحتمالات في فرز النقاط من خلال إحداثيات X الخاصة بهم (أو Y - لا يهم حقًا ، فكلها متسقة فقط). يمكنك بعد ذلك استخدام ذلك للتخلص من المقارنات مع العديد من النقاط الأخرى. عندما تنظر إلى المسافة بين النقطة [i] والنقطة [j] ، إذا كانت المسافة x وحدها أكبر من أقصر مسافة حاليًا ، يمكن القضاء على النقطة [j+1] ... النقطة [n] حسنا (على افتراض i<j -- إذا j<i, ، ثم النقطة [0] ... نقطة [i] التي تم التخلص منها).

إذا بدأت نقاطك كإحداثيات قطبية ، فيمكنك استخدام تباين في نفس الشيء - فرز المسافة من الأصل ، وإذا كان الفرق في المسافة من الأصل أكبر من أقصر مسافة حالية ، يمكنك القضاء على هذه النقطة ، وجميع الآخرين الذين هم أبعد من (أو أقرب إلى) الأصل من تلك التي تفكر حاليًا.

Answer 4

يمكنك استخراج أقرب زوج في الوقت الخطي من ثلاثوناي التثليث وعلى الأرجح من مخطط Voronoi.

Answer 5

هناك خوارزمية قياسية لهذه المشكلة ، هنا يمكنك العثور عليها:http://www.cs.mcgill.ca/~cs251/closestpair/closestpairps.html

وهنا تنفيذي لهذا algo ، آسف إنه بدون تعليقات:

    static long distSq(Point a, Point b) {
    return ((long) (a.x - b.x) * (long) (a.x - b.x) + (long) (a.y - b.y) * (long) (a.y - b.y));
}

static long ccw(Point p1, Point p2, Point p3) {
    return (long) (p2.x - p1.x) * (long) (p3.y - p1.y) - (long) (p2.y - p1.y) * (long) (p3.x - p1.x);
}

static List<Point> convexHull(List<Point> P) {

    if (P.size() < 3) {
        //WTF
        return null;
    }

    int k = 0;

    for (int i = 0; i < P.size(); i++) {
        if (P.get(i).y < P.get(k).y || (P.get(i).y == P.get(k).y && P.get(i).x < P.get(k).x)) {
            k = i;
        }
    }

    Collections.swap(P, k, P.size() - 1);

    final Point o = P.get(P.size() - 1);
    P.remove(P.size() - 1);


    Collections.sort(P, new Comparator() {

        public int compare(Object o1, Object o2) {
            Point a = (Point) o1;
            Point b = (Point) o2;

            long t1 = (long) (a.y - o.y) * (long) (b.x - o.x) - (long) (a.x - o.x) * (long) (b.y - o.y);

            if (t1 == 0) {
                long tt = distSq(o, a);
                tt -= distSq(o, b);
                if (tt > 0) {
                    return 1;
                } else if (tt < 0) {
                    return -1;
                }
                return 0;

            }
            if (t1 < 0) {
                return -1;
            }
            return 1;

        }
    });



    List<Point> hull = new ArrayList<Point>();
    hull.add(o);
    hull.add(P.get(0));


    for (int i = 1; i < P.size(); i++) {
        while (hull.size() >= 2 &&
                ccw(hull.get(hull.size() - 2), hull.get(hull.size() - 1), P.get(i)) <= 0) {
            hull.remove(hull.size() - 1);
        }
        hull.add(P.get(i));
    }

    return hull;
}

static long nearestPoints(List<Point> P, int l, int r) {


    if (r - l == P.size()) {

        Collections.sort(P, new Comparator() {

            public int compare(Object o1, Object o2) {
                int t = ((Point) o1).x - ((Point) o2).x;
                if (t == 0) {
                    return ((Point) o1).y - ((Point) o2).y;
                }
                return t;
            }
        });
    }

    if (r - l <= 100) {
        long ret = distSq(P.get(l), P.get(l + 1));
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j < r; j++) {
                ret = Math.min(ret, distSq(P.get(i), P.get(j)));
            }
        }
        return ret;

    }

    int c = (l + r) / 2;
    long lD = nearestPoints(P, l, c);
    long lR = nearestPoints(P, c + 1, r);
    long ret = Math.min(lD, lR);
    Set<Point> set = new TreeSet<Point>(new Comparator<Point>() {

        public int compare(Point o1, Point o2) {
            int t = o1.y - o2.y;
            if (t == 0) {
                return o1.x - o2.x;
            }
            return t;
        }
    });
    for (int i = l; i < r; i++) {
        set.add(P.get(i));
    }

    int x = P.get(c).x;

    double theta = Math.sqrt(ret);

    Point[] Q = set.toArray(new Point[0]);
    Point[] T = new Point[Q.length];
    int pos = 0;
    for (int i = 0; i < Q.length; i++) {
        if (Q[i].x - x + 1 > theta) {
            continue;
        }
        T[pos++] = Q[i];
    }

    for (int i = 0; i < pos; i++) {
        for (int j = 1; j < 7 && i + j < pos; j++) {
            ret = Math.min(ret, distSq(T[i], T[j + i]));
        }
    }
    return ret;
}

Answer 6

من سؤالك ، ليس من الواضح ما إذا كنت تبحث عن مسافة الجزء ، أو الجزء نفسه. على افتراض أنك تبحث عن المسافة (الجزء في ذلك الوقت تعديل بسيط ، بمجرد أن تعرف هما النقطتين اللذان تكون مسافة الحد الأدنى) ، تم إعطاء 5 نقاط ، من 1 إلى 5 ، تحتاج إلى ذلك

compare 1 with 2,3,4,5, then 
compare 2, with 3,4,5, then 
compare 3 with 4,5, then 
compare 4 with 5.

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

import numpy as np
def find_min_distance_of_a_cloud(cloud):
        """
        Given a cloud of points in the n-dim space, provides the minimal distance.
        :param cloud: list of nX1-d vectors, as ndarray.
        :return:
        """
        dist_min = None
        for i, p_i in enumerate(cloud[:-1]):
            new_dist_min = np.min([np.linalg.norm(p_i - p_j) for p_j in cloud[(i + 1):]])
            if dist_min is None or dist_min > new_dist_min:
                dist_min = new_dist_min

        return dist_min

يمكن اختباره بشيء مثل الكود التالي:

from nose.tools import assert_equal

def test_find_min_distance_of_a_cloud_1pt():
    cloud = [np.array((1, 1, 1)), np.array((0, 0, 0))]
    min_out = find_min_distance_of_a_cloud(cloud)
    assert_equal(min_out, np.sqrt(3))


def test_find_min_distance_of_a_cloud_5pt():
    cloud = [np.array((0, 0, 0)),
             np.array((1, 1, 0)),
             np.array((2, 1, 4)),
             np.array((3, 4, 4)),
             np.array((5, 3, 4))]
    min_out = find_min_distance_of_a_cloud(cloud)
    assert_equal(min_out, np.sqrt(2))

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