ضع مستطيلات عشوائية غير متداخلة على لوحة

Question

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

خوارزمية، أي شخص؟

يحرر: جميع المستطيلات N معروفة في البداية ويمكن اختيارها بأي ترتيب. هل هذا يغير الإجراء؟

Answer 1

يمكنك تصميم هذا من خلال مجموعة من المستطيلات "المجانية"، بدءا من واحد واحد مع إحداثيات 0،0، الحجم (X، Y). في كل مرة تحتاج إلى إضافة مستطيل واحد آخر، اختر واحدة من المستطيلات "المجانية" المتبقية، وتوليد مستطيل جديد (مع الإحداثيات والحجم من أعلى اليسار، بحيث يتم احتواءها بالكامل)، وتقسيم هذا المستطيل وكذلك أي متداخلة أخرى " مجانا "مستطيل، بحيث يعبر الأطفال عن مساحة خالية متبقية. سيؤدي ذلك إلى 0 إلى 4 مستطيلات جديدة (0 إذا كان المستطيل الجديد بالضبط حجم المستطيل الحر القديم؛ 4 إذا كان في الوسط وما إلى ذلك). بمرور الوقت، ستحصل على مجالات مجانية أكثر وأكثر أصغر وأصغر، لذا فإن المستطيلات التي تخلقها ستكون أصغر أيضا.

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

Answer 2

فيما يلي مقالة لائقة عن خوارزميات التعبئة 2D: http://www.devx.com/dotnet/article/36005.

تريد عموما نوعا ما من الخوارزمية باستخدام الاستدلال لتحقيق نتائج لائقة. سيكون الحل البسيط (ولكن غير الأمثل) هو أول خوارزمية تناسب.

Answer 3

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

تتم تهيئة الخوارزمية بحجم اللوحة، ثم تتكرر من خلال جميع المستطيلات والحصول على موقفها. قد يؤثر ترتيب المستطيلات على النتيجة، اعتمادا على العبوة.

Answer 4

أود أن أنصحك باستخدام اقتراح Staxmans.

هنا هو بلدي 2C:

أضف الكثير من المستطيلات بشكل عشوائي (متداخلة بعضها البعض). حذف المستطيلات المتداخلة:

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

للعثور على جميع المستطيلات لمس مستطيل معين، يمكنك استخدام شجرة رباعية أو عدم المساواة القائمة على قيم X1 و Y1 X2 و Y2.

تحرير: في الواقع، تشمل معظم محركات الألعاب مثل Pygame وما إلى ذلك اكتشاف تصادم للمستطيلات التي تعد مشكلة شائعة.

Answer 5

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

لا ينبغي أن يكون من الصعب للغاية إنشاء خوارزمية مخصصة.