ساحات المسير

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

يمكن أن تكون الخطوط الخارجية من نوعين:

• الخطوط المتساوية - خطوط تتبع مستوى بيانات واحد، أو قيمة متساوية .
• نطاقات التساوي - مناطق مملوءة بين خطوط التساوي.

تشمل التطبيقات النموذجية خطوط الكنتور على الخرائط الطبوغرافية أو توليد خطوط الضغط الجوي لخرائط الطقس .

تعتمد خوارزمية المربعات المتحركة على نهج مشابه لخوارزمية المكعبات المتحركة ثلاثية الأبعاد :

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

فيما يلي خطوات الخوارزمية:

قم بتطبيق عتبة على الحقل ثنائي الأبعاد لإنشاء صورة ثنائية تحتوي على:

• 1 حيث تكون قيمة البيانات أعلى من قيمة التساوي
• 0 حيث تكون قيمة البيانات أقل من قيمة التساوي

ملاحظة: يجب التعامل مع البيانات التي تساوي قيمة التساوي على أنها أعلى أو أسفل بطريقة متسقة.

كل مجموعة من البكسلات بحجم 2×2 في الصورة الثنائية تُشكّل خلية تحديد، لذا تُمثَّل الصورة بأكملها بشبكة من هذه الخلايا (موضحة باللون الأخضر في الصورة أدناه). لاحظ أن شبكة تحديد هذه أصغر بخلية واحدة في كل اتجاه من الحقل ثنائي الأبعاد الأصلي.

لكل خلية في شبكة تحديد المحيط:

1. لتكوين فهرس ثنائي، قم بتجميع البتات الأربعة الموجودة في زوايا الخلية: تحرك حول الخلية باتجاه عقارب الساعة، وأضف البت إلى الفهرس باستخدام عملية OR الثنائية والإزاحة إلى اليسار ، بدءًا من البت الأكثر أهمية في أعلى اليسار، وصولًا إلى البت الأقل أهمية في أسفل اليسار. يمكن أن يحتوي الفهرس الناتج المكون من 4 بتات على 16 قيمة ممكنة في النطاق من 0 إلى 15.
2. استخدم فهرس الخلية للوصول إلى جدول بحث مُعد مسبقًا يحتوي على 16 مدخلًا تسرد الحواف اللازمة لتمثيل الخلية (كما هو موضح في الجزء السفلي الأيمن من الصورة أدناه).
3. قم بتطبيق الاستيفاء الخطي بين قيم بيانات الحقل الأصلية لإيجاد الموضع الدقيق لخط الكفاف على طول حواف الخلية.

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

الخلية المثلثية مستوية دائمًا ، لأنها ثنائية الأبعاد (أي محددة بـ n + 1 رأس في فضاء ذي n بُعد). يوجد دائمًا مُستكمِل خطي فريد عبر المثلث، ولا توجد إمكانية لوجود نقطة سرجية غامضة.

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

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

تتميز الخوارزمية بقدرتها الفائقة على المعالجة المتوازية ، لأن جميع الخلايا تُعالج بشكل مستقل. من السهل كتابة خوارزمية متوازية بافتراض ما يلي:

• حقل إدخال عددي مشترك للقراءة فقط.
• دفق إخراج هندسي مشترك للإضافة فقط.

في تطبيق بسيط لخوارزمية المربعات المتحركة، حيث تُعالج كل خلية على حدة، يتم تنفيذ كل عملية استيفاء خطي مرتين (خطوط متساوية) أو أربع مرات (نطاقات متساوية). وبالمثل، سيحتوي الناتج على نسختين من رؤوس ثنائية الأبعاد للخطوط المنفصلة (خطوط متساوية) أو أربع نسخ للمضلعات (نطاقات متساوية). [بافتراض أن: الشبكة كبيرة، بحيث تكون معظم الخلايا داخلية؛ ويتم إنشاء مجموعة متصلة كاملة من النطاقات المتساوية.]

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

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

• مابل، سي. (2003). "التصميم الهندسي وتخطيط الفضاء باستخدام خوارزميات المربعات المتحركة والمكعبات المتحركة". المؤتمر الدولي للنمذجة الهندسية والرسومات، 2003. وقائع المؤتمر . الصفحات 90-95 . doi : 10.1109/GMAG.2003.1219671 . ISBN  978-0-7695-1985-2. S2CID 11320513 . 
• بانكس، دي سي (2004) . "حساب الحالات في خوارزميات الاستبدال". معاملات IEEE في التصور ورسومات الحاسوب . 10 (4): 371-384 . CiteSeerX 10.1.1.582.7221 . doi : 10.1109/TVCG.2004.6 . PMID 18579966. S2CID 2450480 .   
• لاغوارديا، جيه جيه؛ كويتو، إي؛ دوبلاري، إم. (2005). "طريقة غاليركين للجوار الطبيعي مع بنية شجرة رباعية" . المجلة الدولية للطرق العددية في الهندسة . 63 (6): 789-812 . Bibcode : 2005IJNME..63..789L . doi : 10.1002/nme.1297 . S2CID 122746298 . 
• شيفر، سكوت؛ وارن، جو (2005). "مكعبات المسيرة المزدوجة: التحديد الأولي للشبكات المزدوجة". منتدى رسومات الحاسوب . 24 (2): 195-201 . doi : 10.1111/j.1467-8659.2005.00843.x . S2CID 10015045 . 
• مانتز، هوبر؛ جاكوبس، كارين؛ ميكي، كلاوس (2008). "استخدام دوال مينكوفسكي لتحليل الصور: خوارزمية المربع المتحرك". مجلة الميكانيكا الإحصائية: النظرية والتجربة . 2008 (12) 12015. Bibcode : 2008JSMTE..12..015M . doi : 10.1088/1742-5468/2008/12/P12015 . S2CID 122873298 . 
• سيبوليتي، مارينا ب.؛ ديلريو، كلاوديو أ.؛ بيريلو، جيراردو م. إ.؛ بيكولو، م. سينتيا (2012). "تجزئة وقياس حدود الصور فائقة الدقة في صور الاستشعار عن بعد". الحوسبة وعلوم الأرض . 40 : 87-97 . Bibcode : 2012CG.....40...87C . doi : 10.1016/j.cageo.2011.07.015 .

• خوارزمية المربع المتحرك في برنامج Matlab - خوارزمية مربع متحرك سهلة الفهم ومفتوحة المصدر.
• التنفيذ بلغة جافا
• كود خوارزمية المربعات المتحركة في جافا. عند إعطاء مجموعة بيانات ثنائية الأبعاد وعتبات، يُرجع مصفوفة GeneralPath[] لتسهيل عملية الرسم البياني.
• شرح المثلثات المتعرجة وتطبيقها العملي باستخدام لغة بايثون.
• كود المربعات المتحركة بلغة C - مكتبة رأسية واحدة للمربعات المتحركة يمكنها تصدير شبكات المثلثات لسهولة العرض.