فرمول بند کفش

«فرمول بند کفش» یا «الگوریتم بند کفش» که با نام فرمول مساحت گاوس و فرمول نقشه بردار نیز شناخته می شود یک الگوریتم ریاضی برای تعیین مساحت یک چند ضلعی ساده است که رئوس آن با مختصات کارتزین در صفحه داده شده است. برای یافتن مساحت چند ضلعی عملیات ضربِ ضربدری روی مختصات متناظر باید انجام شود. این روش فرمول بند کفش نامیده می شود چرا که انجام عملیات ضرب قطری بین مختصات چند ضلعی مانند نحوه بسته شدن بندهای کفش است! گاهی اوقات به این الگوریتم «روش بند کفش» هم می گویند. این روش محاسباتی در نقشه برداری و جنگلداری کاربرد دارد.

الگوریتم بند کفش در سال ۱۷۶۹ توسط آلبرشت لودویگ فردریش میستر (Albrecht Ludwig Friedrich Meister) و در سال ۱۷۹۵ توسط کارل فردریش گاوس (Carl Friedrich Gauss) مطرح شد. این الگوریتم را می توان با تقسیم چند ضلعی به مثلث اثبات کرد، و همچنین می توان آن را حالت خاصی از قضیه گرین دانست.

فرمول مساحت با در نظر گرفتن هر ضلع AB و محاسبه مساحت مثلث ABO با رأس O در مبدأ از طریق انجام ضرب برداری (خارجی) که مساحت متوازی الاضلاع را محاسبه می کند و یک تقسیم بر ۲ نیاز است به دست می آید. با ادامه محاسبات به همین ترتیب برای چند ضلعی، این مثلث ها با مساحت های مثبت و منفی هم پوشانی خواهند داشت و مساحت های بین مبدأ و چند ضلعی حذف و صفر خواهد شد و تنها مساحت داخلی هر مثلث باقی خواهد ماند. این همان دلیلی است که به این الگوریتم فرمول نقشه بردار می گویند، چرا که با فرض استقرار نقشه بردار در مبدأ، در حرکت پاد ساعتگرد، با حرکت از چپ به راست مساحت مثبت اضافه می شود و مساحت منفی زمانی اضافه می شود که از راست به چپ حرکت کنیم.

فرمول بند کفش یا فرمول مساحت گاوس برای هر چند ضلعی غیر منتظم محدب و مقعر که اضلاعش با هم تلاقی نداشته باشند برقرار و دقیق است.

مثال

چند ضلعی با مختصات (۳,۴)، (۵,۱۱)، (۱۲,۸)، (۹,۵) و (۵,۶) مفروض است و در شکل زیر رسم شده است:

مساحت این چند ضلعی عبارت است از:

A = ۱/۲ | ۳×۱۱ + ۵×۸ + ۱۲×۵ + ۹×۶ + ۵×۴ − ۴×۵ − ۱۱×۱۲ − ۸×۹ − ۵×۵ − ۶×۳ | = ۶۰/۲ = ۳۰

فرمول بند کفش یک فرمول فوق العاده برای محاسبه دقیق مساحت یک چند ضلعی با مختصات رئوس معلوم است.

توضیح نامگذاری

علت نامگذاری این فرمول به فرمول بند کفش به خاطر شیوه ای است که برای محاسبه آن استفاده می شود. این روش از ماتریس ها استفاده می کند. به عنوان یک مثال مثلثی با رئوس (۲,۴)، (۸−,۳) و (۱,۲) را در نظر بگیرید. برای این مثلث ماتریس زیر را با حرکت در یک جهت مشخص بسازید. ماتریسی که با مختصات اولیه پایان می یابد:

در گام اول، خطوط قطری را در جهت پایین و راست بکشید:

و دو عددی که با خط به هم وصل شدند را در هم ضرب کرده سپس حاصلضرب ها را با هم جمع کنید: ۶− = (۱ × ۴) + (۲ × ۳) + (۸− × ۲)

این کار را با خطوط قطری در جهت پایین و چپ انجام دهید:

 = (۲ × ۲) + (۱ × ۸−) + (۳ × ۴)

و در ادامه اختلاف این دو عدد را محاسبه کنید:  ۱۴ = | (۸) − (۶−) |

با نصف کردن این مقدار، مساحت مثلث به دست می آید:  ۷

دسته بندی اعداد مانند این، فرمول را برای یادآوری و استفاده ساده تر می کند. با رسم تمام خطوط قطری، ماتریس حاصل کفشی را با بندهای بسته نشان می دهد و همین دلیل نامگذاری این الگوریتم است.

محدودیت فرمول بند کفش

همانطور که بالاتر هم به آن اشاره شد الگوریتم بند کفش فقط با چند ضلعی های ساده سازگار است. به عبارت دیگر اگر چند ضلعی با خودش تلاقی یا همپوشانی داشته باشد الگوریتم جواب نمی دهد. بنابراین اگر چند ضلعی شما شبیه به یکی از چند ضلعی های تصویر بالا است این روش را برای محاسبه مساحت آن به کار نگیرید چرا که نتایج نادرست خواهند بود.