أي شيء أفضل من الصناديق المحيطة؟

Question

لدي سيناريو، حيث لدي نقاط خطيرة طول مليون خط طول مليون.

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

حصلت على أي شيء أفضل من الصناديق المحيطة؟

أحب أن أرى الخوارزميات والمراجع وعدد قليل من التطبيقات؛) شكرا لك بلطف!

Answer 1

هناك عدد قليل من الخيارات التي تكون أفضل، في الغالب تقسيم الفضاء.

خيار شائع، وغالبا ما يكون جيدا للغاية (وهو أمر غير صعب للغاية) هو استخدام KD-Tree.. quadstrees أسهل في التنفيذ، ولكن أبطأ للبحث. اعتمادا على توزيع بياناتك، ومتطلباتك، قد تؤدي خوارزميات تقسيم الفضاء الأخرى بشكل أفضل، أو لها انخفاض متطلبات الذاكرة أو المشكلات الأخرى ذات الصلة.

Answer 2

أخبرني أحد الزملاء أنه كان لديه خبرة جيدة مع استخدام مورتون كود كمؤشر مكاني على بيانات GIS، ربما هذا شيء يستحق التحقيق.

Answer 3

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

إذا كان لديك "فقط" بملايين النقاط، ولا يتم تجميعها في البقع الساخنة، والتي قد تحصل عليك.

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