أقرب الجيران - ك-د الشجرة - ويكيبيديا دليل

Question

على ويكيبيديا الدخول على k-d الأشجار, خوارزمية عرض من أجل القيام أقرب جار البحث على k-d الشجرة.ما لا أفهمه هو تفسير خطوة 3.2.كيف يمكنك أن تعرف أنه ليس هناك أقرب نقطة فقط لأن الفرق بين تقسيم تنسيق البحث نقطة العقدة الحالية أكبر من الفرق بين تقسيم تنسيق البحث نقطة الحالي أفضل ؟

أقرب جار البحث المتحركة من NN البحث مع د. ك شجرة في 2D

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

1. بدءا من عقدة الجذر ، خوارزمية يتحرك إلى أسفل الشجرة بشكل متكرر في نفس الطريقة التي لو في نقطة تفتيش يجري إدراج (أيفإنه يذهب إلى اليمين أو اليسار اعتمادا على ما إذا كانت نقطة أكبر أو أقل من العقدة الحالية في تقسيم البعد).
2. مرة واحدة الخوارزمية تصل إلى عقدة ورقة ، فإنه يحفظ تلك العقدة نقطة "الحالي أفضل"
3. الخوارزمية بالمرافعة العودية من الشجرة ، وأداء الخطوات التالية في كل عقدة:1.إذا كانت العقدة الحالية هو أقرب من الحالي أفضل, ثم يصبح الحالية أفضل.2.خوارزمية التحقق من ما إذا كان يمكن أن يكون هناك أي نقاط الجانب الآخر من تقسيم الطائرة التي هي أقرب إلى نقطة تفتيش من أفضل الحالية.في المفهوم ، ويتم ذلك عن طريق المتقاطعة تقسيم hyperplane مع hypersphere حول نقطة البحث التي لديها دائرة نصف قطرها يساوي الحالي أقرب مسافة.منذ hyperplanes كل محور الانحياز هذا نفذت مقارنة بسيطة لمعرفة ما إذا كان الفرق بين تقسيم تنسيق البحث نقطة العقدة الحالية أقل من المسافة (عموما الإحداثيات) من نقطة تفتيش الحالي أفضل.1.إذا كان hypersphere يعبر الطائرة ، يمكن أن يكون هناك أقرب نقطة على الجانب الآخر من الطائرة حتى الخوارزمية يجب أن تتحرك إلى أسفل في فرع آخر من فروع شجرة من العقدة الحالية تبحث عن أقرب النقاط التالية نفس العودية عملية البحث بأكمله.2.إذا كان hypersphere لا تتقاطع تقسيم الطائرة ، ثم الخوارزمية تواصل المشي حتى الشجرة ، فرع كامل على الجانب الآخر من هذا هو عقدة القضاء عليها.
4. عندما الخوارزمية انتهاء هذه العملية على عقدة الجذر ، ثم البحث كاملة.

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

Answer 1

ننظر بعناية في 6 إطار الرسوم المتحركة على تلك الصفحة.

الخوارزمية هو يعود الى العودية ، فمن الممكن أن هناك أقرب نقطة على الجانب الآخر من hyperplane أنه على.لقد تحققنا من نصف واحد, ولكن يمكن أن يكون هناك حتى أقرب نقطة على النصف الآخر.

لقد اتضح أننا في بعض الأحيان يمكن أن تجعل التبسيط.إذا كان مستحيل أن يكون هناك نقطة على النصف الآخر أقرب من لدينا أفضل (الأقرب) نقطة, ثم يمكننا تخطي هذا hyperplane النصف تماما.هذا التبسيط هو مبين على 6 الإطار.

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

إذا كان أبعد من نقطة تفتيش إلى hyperplane من من نقطة تفتيش الحالية أقرب نقطة, ثم لا يوجد أي سبب للبحث الماضي أن تقسيم تنسيق.

حتى لو كان شرحي لا الرسم.بالتوفيق في المشروع الخاص بك!

Answer 2

نعم وصف NN (أقرب جار) البحث في دينار كويتي شجرة في ويكيبيديا هو قليلا من الصعب متابعة.انه لا يساعد أن الكثير من أعلى نتائج بحث Google على NN دينار كويتي شجرة البحث هي خاطئة تماما!

هنا بعض رمز C++ أن تظهر لك كيفية الحصول على ذلك الحق:

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

API NN البحث على دينار كويتي شجرة:

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

الافتراضي المسافة وظيفة:

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

تحرير:بعض الناس يطلبون المساعدة مع هياكل البيانات أيضا (وليس فقط NN الخوارزمية), حتى هنا هو ما كنت قد تستخدم.اعتمادا على الغرض الخاص بك, قد ترغب في تعديل هياكل البيانات قليلا.(ملاحظة:ولكن يكاد يكون من المؤكد لا لا ترغب في تعديل NN الخوارزمية.)

KDPoint الدرجة:

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

KDNode الدرجة:

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

KDTree الدرجة:(ملاحظة:سوف تحتاج إلى إضافة وظيفة عضو لبناء/ملء شجرة الخاص بك.)

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};