العثور على جميع الكائنات د 3 ضمن مسافة معينة من نقطة

Question

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

هذا يبدو بلا شك غير واضح بعض الشيء ، لذلك اسمحوا لي أن أضعه بطريقة أخرى:إذا كانت النقطة الأولى في points لديه إحداثيات <x, y, z>, ، وأود أن معرفة أي من الكائنات في points لديه مسافة أقل من [بعض القيمة التعسفية] من النقطة الأولى.

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

تحرير:لاحظ أن قيم موضع هذه الكائنات ستتغير

Answer 1

شجرة ص * هي بنية بيانات جيدة جدا لهذا ، لا سيما عندما تتغير النقاط.إنه مصمم للتغييرات ، في الواقع.

شجرة ك د هو أبسط ، لكنه لا يدعم التغييرات بشكل جيد للغاية.وهي مصممة لبناء السائبة لمرة واحدة.

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

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

Answer 2

تحرير :مربع = مكعب (ولكن تخيل ذلك في الفضاء 2 د سيكون ربما أفضل ، ثم يمكنك تحويله إلى 3 د بسهولة)

كنت أفكر وأعتقد أنني حلها.ولكن هذا هو مجرد "بلدي" الحل ، ليس لدي أي إشارة لذلك.

يمكنك إنشاء فئة "مربع" ، والتي لديها موقف وعرض وقائمة من النقاط في هذا الكائن.

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

سيتم توزيع جميع المربعات بانتظام ، لذلك-من وجهة نظر" مثيل النقطة " - ليس عليك معرفة جميع المربعات الموجودة لمعرفة الوقت الثابت الذي تنتمي إليه.(مثال :أعلم أن هناك مربعات بعرض 40 ويتم توزيعها بمسافة 20.أنا في الموضع 10001 ، لذلك أعرف أنني أنتمي إلى مربعات في الموضع 9980 و 10000)

سيتم عبور المربعات من قبل بعضها البعض ، وبالتالي يمكن أن تكون نقطة واحدة في المزيد من المربعات.

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

عندما تتحرك النقاط ، فهي مسؤولة عن التسجيل وإلغاء التسجيل في المربعات.

---

1د مثال :

الفصول الدراسية : Line segment و Point

Attrributes:

Line segment : int position, List<Points> points

Point : int position, List<LineSegment> lineSegments

أريد أن أتفاعل فقط مع النقاط في مسافة 20.

لذلك أنا خلق حالات من Line segments مع عرض 40 وأنا وضعت لهم واحدا تلو الآخر في مسافة 20.

لذلك سيكونون في المواضع 0 ، 20 ، 40 ، 60 ....

سيغطي فريست المنطقة 0-40 ، الثانية 20-60 إلخ.

أنا وضعت لهم في مجموعة ومع موقف معروف ، يمكنني الوصول إليها بسرعة : arrayOfLineSegments[position/20]

عندما أقوم بإنشاء نقطة ، أضفه إلى line segments إنه ينتمي إلى.

عندما أقوم بالتحديث ، تتفاعل كل نقطة فقط مع النقاط في شرائح الخطوط.

عندما أتحرك نقطة ، فإنه تسجيل وإلغاء تسجيل لينيسيغمنتس أنه ينتمي إلى.

Answer 3

يمكنك استخدام حلقة للتحقق من خلال صفيف الكائن.

استخدم الصيغة التالية: d = sqrt[(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2]

س1, ص1, ض1 كونها النقطة الأولى في Points و س2 ، ص2 ، ض2 كونها نقاط الكائن الذي تقوم بفحصه.سيؤدي هذا إلى التحقق من وجهة نظرك المعروفة مقابل جميع النقاط الأخرى.إذا كانت المسافة (د) أقل من المسافة التي تريدها x ثم افعل ما تريد أن تقوم به البرنامج.