مربعات سيارة

خوارزمية المربعات السيارة (بالإنجليزية: Marching squares)‏ هي خوارزمية في الرسوميات الحاسوبية تقوم بتوليد خطوط كونتور contour lines في حقل سلمي ثنائي البعد. يكون تعميم هذه الخوارزمية في الفضاء الثلاثي الأبعاد ما يسمى بخوارزمية المكعبات السيارة Marching cubes.

الخوارزمية[عدل]

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

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