أي مراجع حول كيفية تنفيذ Quadstrees مع حدود دورية؟

Question

لدي بيانات مكانية - (x، y) نقاط على متن طائرة - التي أقسمها باستخدام Quadstrees. تتمثل الفكرة في العثور على النقاط التي جيرانها إلى نقطة معينة (أ، ب). النقاط هي جيران إذا كان هناك بعض المسافة (قل ذلك) بين الاثنين. المشكلة هي أن المساحة دورية، أي إذا كانت هناك نقطة قريبة جدا من الحافة (<l) يجب أن تكون هذه النقطة جارة نقطة بالقرب من الحافة المعاكسة. (عن طريق الدورية في هذه الحالة يعني أن الطائرة تكرر نفسها)

|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
| ================== | ===================|

هذه النقاط (أ، ب) و (ج، د) و (ح، أنا) يجب أن تكون جيرانا. جيران (أ، ب) هم النقاط داخل الدائرة مع دائرة نصف قطرها مع المركز (أ، ب).

أوراق، وكيف تكون كلها موضع ترحيب.

شكرا،

---

رفاق:

شكرا لإجاباتك، لا أتحقق من Stackoverflow لفترة من الوقت كان مشغولا في مشروع آخر سيحقق إجاباتك على الفور! شكرا جزيلا.

Answer 1

لماذا لا تقسم "دائرة البحث" في مخططات فطيرة مع زاوية PI / 2؟ دعونا نرى ما إذا كان يمكنني الحصول على هذا من خلال النص وصورة بسيطة.

نص Alt http://img168.imageshack.us/img168/8426/circleinquarters.gif.

هذه الفكرة هي رؤية "بحث الدائرة" كأربعة "مخططات فطيرة"، لذلك عند إجراء عملية بحث مع C (A، B، L) تحتاج إلى مراعاة ذلك عند المرور في Quadtree، لا تعمل الدائرة " تتقاطع فقط من الركن الأيسر العلوي من Quadtree، لذلك في هذه الحالة، عليك أن تتفرع إلى أربعة فروع (وليس فقط، إذا لم تكن هذه المنطقة دورية).

Answer 2

xdist = min( (x1-x2) % px, (x2-x1) % px )

حيث px هي الفترة ×.

يغادر Ydist والباقي كممارسة لممارسة القارئ :-)

Answer 3

يبدو أبسط أن تبقي Quadtree كما هو، لأن مستوى الجذر فقط يتم نسخه بشكل دوري. لاتخاذ الدورية في الاعتبار، قم بعدة الطلبات (x+i*dx,y+j*dy,L) لكل طلب (x,y,L). وبعد حلقة على I، J بحيث يتقاطع قرص الاستعلام عقدة الجذر للشجرة.