ما قبل RTree الخطوة: تقسيم مجموعة من النقاط إلى مناطق مستطيلة تحتوي كل منها على نقطة واحدة

Question

بالنظر إلى وضعي الحالي (LAT، Long) أريد العثور بسرعة على أقرب جار في نقاط مشكلة الفائدة. وبالتالي، أنوي استخدام قاعدة بيانات R-Tree، والتي تسمح للبحث السريع. ومع ذلك، يجب ملء قاعدة البيانات الأولى - بالطبع. لذلك، أحتاج إلى تحديد المناطق المستطيلة التي تغطي المنطقة، حيث تحتوي كل منطقة على نقطة اهتمام واحدة.

سؤالي هو كيف يمكنني البحث عن البيانات، أي كيف أقوم بتطبيق المنطقة في هذه المناطق الفرعية المستطيلة؟ (أريد مناطق مستطيلة لأنها تضاف بسهولة إلى RTree - على عكس مناطق Voronoi العامة أكثر).

/يوحنا

Answer 1

يحرر: يعمل النهج أدناه، ولكن يتجاهل الميزة الحرجة لأشجار R - أن سلوك تقسيم العقد R-Tree محددة جيدا، ويحافظ على شجرة متوازنة (من خلال خصائص تشبه شجرة B). لذلك في الواقع، كل ما عليك فعله هو:

1. اختيار الحد الأقصى لعدد المستطيلات لكل صفحة
2. إنشاء مستطيلات البذور (استخدام النقاط أبعد بعيدا عن بعضها البعض، والأجزاء الوسطى، أيا كان).
3. لكل نقطة، اختر مستطيل لوضعه في
   4. إذا سقطت بالفعل في مستطيل واحد، ضعها هناك
   5. إذا لم يفعل ذلك، فقم بتوسيع المستطيل الذي يحتاج إلى تمديده على الأقل (طرق مختلفة لقياس مخارج "أقل" - أعمال المنطقة)
   6. إذا تنطبق مستطيلات متعددة - اختر واحدا استنادا إلى كم هو كامل، أو بعضها البعض
4. إذا حدث تجاوز الفضل - استخدم الانقسام التربيعي لتحريك الأشياء حولها ...
5. وهلم جرا، باستخدام خوارزميات R-Tree مباشرة من كتاب نصي.

أعتقد أن الطريقة الواردة أدناه موافق لإيجاد مستطيلات البذور الأولية؛ لكنك لا ترغب في ملء شجرة ص بأكملها بهذه الطريقة. القيام بالانشقاقات وإعادة التوازن في كل وقت يمكن أن تكون مكلفة بعض الشيء، لذلك ربما ترغب في القيام بدقة لائقة من العمل مع نهج KD أدناه؛ ليس فقط كل العمل.

---

نهج KD: أرفق كل شيء في مستطيل.

إذا كان عدد النقاط في المستطيل> عتبة، فاحتياح في الاتجاه D حتى تغطي نصف النقاط.

انقسم إلى مستطيلات اليسار واليمين (أو أعلى وتحت) نقطة الانقسام).

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

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

Answer 2

خرطوشة Oracle المكانية تصف الوثائق خوارزمية التفسير التي يمكن أن تفعل ما تريد. بالمختصر:

• أرفق كل نقاطك في المربع
• إذا كان هناك مربع يحتوي على 1 نقطة - فهرس مربع
• إذا كان مربع لا يحتوي على نقاط - تجاهله
• إذا كان مربع يحتوي على أكثر من 1 نقطة
  • سبليت ساحة إلى 4 مربعات متساوية وتكرار التحليل لكل مربع جديد

يجب أن تكون النتيجة شيئا مثل هذا:
نص Alt http://download-uk.oracle.com/docs/cd/a64702_01/doc/cartridg.805/a53264/sdo_ina5.gif.

Answer 3

أعتقد أنك تفتقد شيئا في بيان المشكلة. افترض أن لديك نقاط N (X، Y) بحيث يحتوي كل نقطة على تنسيق X و Y فريد من نوعه. يمكنك تقسيم منطقتك إلى مستطيلات N ثم من خلال تقسيمه في أعمدة رأسية N. لكن هذا لا يساعدك في حل أقرب مشكلة POI بسهولة، فهل ذلك؟ لذلك أعتقد أنك تفكر في شيء ما حول هيكل المستطيل الذي لم تكن مفصلا بعد.

توضيح:

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

الأرقام هي Pois والأغطية الرأسية تظهر تقسيم تقسيم في 7 مناطق مستطيلة. ولكن من الواضح أنه لا توجد معلومات "مثيرة للاهتمام" في التقسيم الفرعي. هل هناك بعض المعيار الإضافي في التقسيم الذي لم تذكره؟