كيفية تقسيم منطقة مكونة من مربعات صغيرة إلى مستطيلات أكبر؟

Question

وأين أذهب للبحث عن الخوارزميات التي تأخذ شبكة 2D والقيم التي هي إما 0 أو 1 كمدخل ومن ثم يحدد جميع المستطيلات غير متداخلة الممكنة في ذلك؟

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

لا حاجة أقصى قدر من الكفاءة والسرعة هي أكثر أهمية.

وإضافة: على ما يبدو ما أنا أبحث عن ويبدو أن تقنية تسمى Tesselation. والان انا بحاجة فقط لتجد وصفا جيدا لهذه الحالة المحددة.

وإضافة 2: إن حدود المربعات "1" يكون غير منتظم وفي بعض الحالات ولا حتى اتصال، وتوزيع الساحات "1" سوف تكون عشوائية تماما. أنا بحاجة لهذه الأشكال غير النظامية الكشف عن هويته وانفصلا إلى مستطيلات العادية.

<قوية> الجواب الصحيح: للحصول على أفضل توازن بين السرعة والكفاءة هو الأمثل لاستخدام بيانات الشبكة لملء رباعية شجرة مع كل عقدة وجود قيمة حالة إما فارغة / وليس صحيحا جزئيا / شغلها.

Answer 1

ولقد فعلت شيئا من هذا القبيل لالتصور فوكسل سريعة وقذرة من صناديق 3D مع برنامج OpenGL.

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

ورسم المستطيل، إذا تم ملئه.

وإذا كان هناك صناديق remaing، كرر recursivly الإجراء لجميع المستطيلات remaing ثلاثة الناجمة عن المستطيل الماضي، والتي هي حق، أسفل وأسفل اليمين:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

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

Answer 3

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

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

0 0 1 1 1 0 0 0 1 1 1 1 0

هل يؤدي الى:

skip 2
draw 3
skip 3
draw 4
skip 1

وهذا سوف يقلل من عدد المكالمات إلى رسم مربع دون أي حاجة التخزين المؤقت (أي يمكنك بناء المربعات على الطاير).

إذا كنت ترغب في إنشاء صناديق الأكبر أود أن أقترح خوارزمية التراجع هناك تجد الأول (1) ومحاولة لتوسيع مربع في كل الاتجاهات. بناء قائمة من صناديق ومسح 1: كما كنت قد استخدمتها

Answer 4

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

Answer 5

وكان علي أن حل مشكلة مماثلة، يا خوارزمية تدعم صفائف خشنة، لقد اختبرت بشكل كبير وعلق عليه لكنه أبطأ من اقتراح جويل في والعودة ل: https://stackoverflow.com/a/13802336