أصغر صندوق محيط

في الهندسة ، يُعرف أصغر صندوق محيط ( أو أصغر صندوق محيط ) لمجموعة نقاط S في فضاء ذي N بُعدًا بأنه الصندوق ذو أصغر قياس ( مساحة ، أو حجم ، أو حجم فائق في الأبعاد الأعلى) الذي تقع داخله جميع النقاط. وعند استخدام أنواع أخرى من القياس، يُطلق على أصغر صندوق عادةً اسمٌ مُناسب، مثل "صندوق محيط ذو محيط أدنى".

أصغر صندوق محيط لمجموعة نقاط هو نفسه أصغر صندوق محيط لغلافها المحدب ، وهي حقيقة يمكن استخدامها بشكل استدلالي لتسريع الحساب. ^{[ 1 ]}

في الحالة ثنائية الأبعاد، يُطلق عليها اسم المستطيل المحيط الأدنى .

المربع المحيط الأدنى المحاذي للمحاور ( AABB ) لمجموعة نقاط معينة هو أصغر مربع محيط لها مع مراعاة شرط أن تكون حواف المربع موازية لمحاور الإحداثيات (الديكارتية). وهو حاصل الضرب الديكارتي لـ N فترة، تُحدد كل منها بالقيمة الدنيا والقصوى للإحداثيات المقابلة للنقاط في S.

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

المربع المحيط الأدنى ذو التوجيه العشوائي هو أصغر مربع محيط يتم حسابه دون أي قيود على اتجاه النتيجة. يمكن استخدام خوارزميات المربع المحيط الأدنى القائمة على طريقة الفرجار الدوار لإيجاد أصغر مساحة أو أصغر محيط لمضلع محدب ثنائي الأبعاد في زمن خطي، ولمجموعة نقاط ثلاثية الأبعاد في الزمن اللازم لإنشاء غلافها المحدب متبوعًا بحساب خطي. ^{[ 1 ]} يمكن لخوارزمية الفرجار الدوار ثلاثية الأبعاد إيجاد أصغر حجم للمربع المحيط ذي التوجيه العشوائي لمجموعة نقاط ثلاثية الأبعاد في زمن مكعب. ^{[ 2 ]} تتوفر تطبيقات Matlab لهذه الخوارزمية، بالإضافة إلى الحل الأمثل الذي يوازن بين الدقة ووقت وحدة المعالجة المركزية. ^{[ 3 ]}

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

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

• الكرة المحيطة
• الحجم المحيط
• أصغر مستطيل محيط
• تكامل داربو