مرشح الفهرس المكاني: هل تقاطع الصندوق يعني تقاطع الشكل؟

الخلاصة السريعة

تبدأ query بتقاطع الصناديق المحيطة؛ ومع predicate تصفي المرشحات بالعلاقة المحددة. ^[1] نقطة مثالنا مرشح بالصندوق، لكنها خارج المثلث.

• تعيد query مرشحات الصناديق عند غياب predicate؛ وجوده يضيف اختبار العلاقة بترتيب هندسة الاستعلام ثم هندسة الشجرة. ^[1]
• مثلثنا رؤوسه س وص: 0 و 0 ، ثم 4 و 0 ، ثم 0 و 4 ؛ صندوقه يغطي من 0 إلى 4 في المحورين.
• النقطة ن عند 3 و 3 داخل الصندوق، لكن مجموع إحداثييها 6 يتجاوز حد المثلث 4 ؛ لذلك لا تحقق intersects مع المثلث في ورقتنا.
• احفظ معرف المرشح ومرحلة الفحص والعلاقة؛ عدم تحقق العلاقة المختارة لا يعني غياب السجل أو خطأ مكانه، ولم نشغل الاستعلام.

ما الذي يفحصه الاستعلام الأولي؟

توثق STRtree.query تقاطع الصناديق المحيطة، ثم تصفية المرشحات بعلاقة predicate إن قدمت. تطبق العلاقة بترتيب هندسة الاستعلام ثم هندسة الشجرة. ^[1]

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

المطلوب من مساعد تجهيز البيانات أن يميز اسم المرحلة. كلمة «مرشح» تعني في تمريننا أن الشكل اجتاز شرط الصندوق، ولا نستبدل بها تلقائيًا كلمة «متقاطع» التي تخص العلاقة النهائية.

أي مساحة يضيفها الصندوق إلى المثلث؟

نؤلف مثلثًا قائمًا برؤوس أصل المحورين، ونقطة س = 4 وص = 0 ، ونقطة س = 0 وص = 4. حد الضلع المائل في مثالنا يحقق س + ص = 4 ، والداخل في الربع غير السالب يحقق س + ص أقل من 4.

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

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

لماذا تمر النقطة بالشرط الأول وتفشل في الثاني؟

نضع النقطة ن عند س = 3 وص = 3. كل من الرقمين داخل مجال الصندوق، ولذلك يمر موضعها بشرط الصندوق المعلن. لا تقع النقطة على حد الصندوق أو على ضلع المثلث.

لكن جمع 3 و 3 يعطي 6 ، وهو أكبر من 4. النقطة أعلى الضلع المائل وخارج المثلث نفسه. عند طلب intersects بين هذه النقطة والمثلث لا توجد نقطة مشتركة بين الشكلين؛ فلا تحقق العلاقة في ورقتنا.

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

كيف نعرض نتيجة لا تتجاوز ما فحصناه؟

نقترح تسجيل معرف ن ومعرف المثلث، ثم خانة للمرشح بالصندوق وخانة للعلاقة النهائية واسمها. لا نختزل الخانتين إلى علامة «داخل» مبهمة في ملف يدخل إلى النموذج.

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

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