أحاول البحث عن خوازمية سريعة لحل المسألة التالية:

• لدينا مضلع غير منتظم و مغلق.
  
• لدينا مصفوفة من المستطيلات ذات الأحجام المختلفة.

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

الناتج المتوقع من الخوارزمية

• رقم التسلسل للمستطيل الذي تم اختياره من المصفوفة.
• مصفوفة التحويل لكل مستطيل بالنسبة للمضلع.

هذه الصورة توضح مثال محلول يدوياً:


شكراً مسبقاً على أي أفكار أو اقتراحات!

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


مثلاً:
3×4 يضاف أيضاً ك 4×3


أما عن البقية، تذكرني هذه الخوارزمية بمسألة اللص أو Knapsack الشهيرة، لكن الأخيرة ليست ثنائية البعد... همم...

وهذا رابط لمسألة نابساك على ويكيبيديا:
https://en.m.wikipedia.org/wiki/Knapsack_problem

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

تحية طيبة,
استخدم for - each  بدءا من الاكبر الى الاصغر, وداخل كل حلقة استخدم do - while,  وأما الـCondition يكون ان تستخدم نفس المستطيل لعدد خير محدود الى أن تصل للحد الذي لا يمكن استخدامه اكثر من ذلك, ثم انتقل الى المستطيل التالي في For - Each
وطبعا راح تستخدم التدوير ودوال الـ Collision detection في كل مرة لكل مستطيل
قبل كل ذلك, حاول بطريقة او بأخرى ان تملأ المضلع الغير منتظم بعدد من النقاط Vertices  تكون كمواضع وأماكن تضع فيها المستطيلات ,وتختبر امكانية وضع كل مستطيل عليها.


نظريا طبعا 
بمعنى:


For each Rect
         Do        


                   For each Vertex
                            \\ Your stuff :)
                   Next


         While Can fit
Next 
عارف انه احتمال حلي نظريا سهل نظريا لكن تطبيقه صعب, مجرد محاولة اتمنى تتقبلها.


تحياتي

أول فكرة برضو كانت ال knapsack.
تاني فكرة جت في بالي الtesselation عموما وطبعا غير مناسبة ابدا عشان مش مسموح بأي فواصل.
بعد شوية بحث وتفكير عرفت انها تعتبر packing problem، ومن غير ما افتي في ال hardness بتاعتها لوقابلتني المشكلة دي غالبا هبسطها للتالي:


loop while pixel not tested
(find the largest possible rectangle (not from the list of rectanlges but any rectangle at all
mark the rectangle area as tested
end loop


وداخل جوة "اكبر مستطيل" نلاقيه، وهنا متفقين انه اكبر مستطيل ممكن مش اكبر مستطيل من الليستة بتاعتنا ولا حاجة. المهم جواه نخش ننفذ كود يجيبلنا packing of rectangles from our list into an arbitary rectangle وممكن مثلا بgreedy approach بعد ما يتم ترتيب ليستة المستطيلات بتاعتنا.


الحل ده يمكن مش اسرع حل، الحل ده الأكيد انه مش optimal، بل حتى مش unique، اتأكدت بنفسي ان حل مسألة "اكبر مستطيل ممكن جوة مضلع" مش unique، لكن لو اتطلب مني فده اقتراحي لتبسيط المشكلة، وتبسيط المشكلة مش دايما عيب.




-هبه

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

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