كيف يمكنني تحديد ما هي المكعبات التي توجد بها نقطة دون تكرارها جميعا؟

Question

لدي عدد من المكعبات التي تعطى مواقفها وأحجامها بالحد الأدنى والحد الأقصى x, y و z ينسق (حتى الآن موازية للمحاور الرئيسية).

على سبيل المثال، قد يكون لدي مكعبات 3 التالية:

10.5 <= x <= 39.4، 90.73 <= y <= 110.2، 90.23 <= z <= 95.87 20.1 <= x <= 30.05، 9.4 <= y <= 37.6، 0.1 <= z <= 91.2 10.2 <= x <= 10.3، 0.1 <= y <= 99.8، 23.7 <= z <= 24.9

إذا أعطي بعد ذلك نقطة (على سبيل المثال (25.3,10.2,90.65))، هل هناك طريقة لتحديد ما هي مكعبة (ق) بسرعة أنا؟

• من الواضح أنني يمكن أن تكرر فقط من جميع المكعبات، ولكن من المحتمل أن تكون هناك ملايين منهم، وأحتاج إلى هذا للذهاب بشكل أسرع من التكرار البسيط (شيء س (سجل N) أو أفضل سيكون رائعا).

• هذا يبدو لي مثل مشكلة نوع "مطابقة غامض"، وألاحظ ذلك اباتشي لوسين يدعم استعلامات النطاق, ، ولكن يبدو أن هذا يعمل على جولة الاتجاه المعاكس (العثور على نقطة في مكعب بدلا من مكعب يحتوي على نقطة).

• لعدم تعقيد الأمور بشكل طفيف، قد يكون عدد الأبعاد أكبر من 3 (قد يصل إلى 20)؛ أي قد أبحث عن "hypercuboids" بدلا من المكعبات.)

Answer 1

طريقة واحدة واضحة لتسريع هذا الاستعلام هو بناء ما يلي شبكة موحدة هيكل البيانات (غالبا ما تسمى الصناديق) كخطوة مسبقة: ضع n x n x n (في 3D) شبكة على مشهدك ولكل خلية من الشبكة تخزن مؤشر لجميع المكعبات تقاطع تلك الخلية. الآن، للحصول على نقطة استعلام يمكنك حسابها مباشرة في أي خلية هي في الشبكة الموحدة، ثم عليك التحقق من المكعبات فقط المرتبطة بهذه الخلية، وليس كل المكعبات.

اعتمادا على حجم المساحة الكبيرة وكيف تختلف أحجام المكعب هذه الطريقة قد لا تكون فعالة للغاية لأنك قد يكون من الصعب اختيار جيد n قرار لتسريع ما يكفي وليس بحاجة إلى كمية هائلة من الخلايا. للتغلب على هذا قد ترغب في محاولة النظر في طرق أكثر تكيفا لتقسيم المساحة، مثل KD-TREES. (الأشجار دينار كويتي في ويكيبيديا), ، التي هي الأشجار الثنائية أساسا تقسم مساحة المحور مع الطائرات المحاذاة: انظر مثالا هنا حيث تقسم الطائرة الحمراء المربع إلى قسمين ثم الأخضر في أجزاء أصغر، ثم الأزرق ...

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

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

Answer 2

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

هل بحث جوجل على Octrees.

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