كيفية رسم مخطط تفصيلي لمجموعة من المستطيلات المتعددة؟

Question

أحتاج إلى رسم مضلع محيطي لمجموعة من المستطيلات الموضوعة بجانب بعضها البعض.

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

هل يمكنك التفكير في خوارزمية/إجراء بسيط لرسم مضلع (مسارات مستقيمة متصلة) حول هذه الكائنات.

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

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

أعمل حاليًا على الهدف ج، ولكن أي لغة أو خوارزمية أخرى ستكون موضع تقدير، بما في ذلك اللغة الزائفة.

شكرًا!

Answer 1

IMHO يجب أن يكون مثل هذا.قم بإجراء قائمة بخلاف ومعرفة ما إذا كان البعض تراكب: يجب أن يكون هذا بسيطا إذا تم محاذاة المستطيلات مع محور X، Y.يمكنك فقط العثور على الحواف التي لديها certexes على نفس x أو y والنسبات الأخرى تحتاج إلى أن تكون بينهما.بعد أن يجب أن تشكل الحواف المتبقية الخطوط العريضة.

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

Answer 2

لديك صفين، وثلاثة مختلفة y-قيم.دعنا نقول y0 هو قمة الشيء، y2 هي النهاية السفلية، و y1 يمثل الوسط بين كلا الصفين.
يحتوي كل صف على الحد الأقصى والحد الأدنى لقيمة x، لنفترض أن الصف العلوي يبدأ من x0_min ل x0_max, ، والصف السفلي من x2_min ل x2_max.بالنظر إلى تلك القيم التي ترسمها حول الشيء:

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)