العثور على أقرب جار في دائرة نصف قطرها

Question

لدي مجموعة من النقاط a في الفضاء الخاص بي (نقاط جغرافية ولكن يمكنني أن أفترض أنها على متن طائرة 2D).

لدي مجموعة أخرى من النقاط b .

مقابل كل نقطة في b أريد أن أجد كل نقطة في a داخل دائرة نصف قطرها r مع مركز في النقطة التي حدثت من B مجموعة.

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

الحد الأدنى مثال على فشل Kdtree :

أثناء استكشاف KDTREE النقطة المستهدفة (الأحمر) تحت خط رقم النقطة 1. سيتبع ذلك لاستكشاف النقطة تحت الخط، وسوف يفوت ذلك النقطة الحقيقية داخل دائرة نصف قطرها الحمراء.

p>

ما هي خوارزمية أو هيكل البيانات تتيح صحة 100٪؟

أعلم بالتأكيد أنني سأؤدي أسوأ ولكني أبحث عن توازن بين سرعة البحث والصحة الكاملة.

Answer 1

Tree K-D هيكل بيانات جيد لحل هذا.ومع ذلك، لا يمكنك تطبيق إجراء البحث عمياء فقط على نقطة المركز، يجب أن تكون أكثر ذكاء بعض الشيء.

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

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