«فرمول بند کفش» یا «الگوریتم بند کفش» که با نام فرمول مساحت گاوس و فرمول نقشه بردار نیز شناخته می شود یک الگوریتم ریاضی برای تعیین مساحت یک چند ضلعی ساده است که رئوس آن با مختصات کارتزین در صفحه داده شده است. برای یافتن مساحت چند ضلعی عملیات ضربِ ضربدری روی مختصات متناظر باید انجام شود. این روش فرمول بند کفش نامیده می شود چرا که انجام عملیات ضرب قطری بین مختصات چند ضلعی مانند نحوه بسته شدن بندهای کفش است! گاهی اوقات به این الگوریتم «روش بند کفش» هم می گویند. این روش محاسباتی در نقشه برداری و جنگلداری کاربرد دارد.
الگوریتم بند کفش در سال ۱۷۶۹ توسط آلبرشت لودویگ فردریش میستر (Albrecht Ludwig Friedrich Meister) و در سال ۱۷۹۵ توسط کارل فردریش گاوس (Carl Friedrich Gauss) مطرح شد. این الگوریتم را می توان با تقسیم چند ضلعی به مثلث اثبات کرد، و همچنین می توان آن را حالت خاصی از قضیه گرین دانست.
فرمول مساحت با در نظر گرفتن هر ضلع AB و محاسبه مساحت مثلث ABO با رأس O در مبدأ از طریق انجام ضرب برداری (خارجی) که مساحت متوازی الاضلاع را محاسبه می کند و یک تقسیم بر ۲ نیاز است به دست می آید. با ادامه محاسبات به همین ترتیب برای چند ضلعی، این مثلث ها با مساحت های مثبت و منفی هم پوشانی خواهند داشت و مساحت های بین مبدأ و چند ضلعی حذف و صفر خواهد شد و تنها مساحت داخلی هر مثلث باقی خواهد ماند. این همان دلیلی است که به این الگوریتم فرمول نقشه بردار می گویند، چرا که با فرض استقرار نقشه بردار در مبدأ، در حرکت پاد ساعتگرد، با حرکت از چپ به راست مساحت مثبت اضافه می شود و مساحت منفی زمانی اضافه می شود که از راست به چپ حرکت کنیم.
فرمول بند کفش یا فرمول مساحت گاوس برای هر چند ضلعی غیر منتظم محدب و مقعر که اضلاعش با هم تلاقی نداشته باشند برقرار و دقیق است.
تعریف
مساحت یک چند ضلعی در واقع همان ناحیه دو بعدی محصور به چند ضلعی است. برای یک چند ضلعی ساده (چند ضلعی ای که اضلاع آن همدیگر را قطع نمی کنند)، مساحت از رابطه زیر به دست می آید:
که در این جا A مساحت، n تعداد اضلاع و (xi, yi) به ازای i = ۱, ۲,…, n مختصات رئوس (یا گوشه های) چند ضلعی هستند.
با بیانی دیگر:
که در آن xn+1 = x1 و x0 = xn و yn+1 = y1 و y0 = yn
برای بستن چند ضلعی، اولین و آخرین رأس یکسان هستند، یعنی xn, yn = x0, y0 . رئوس باید مطابق با جهت های مثبت و منفی (به ترتیب پاد ساعتگرد و ساعتگرد) مرتب شوند؛ اگر نقاط در جهت خلاف عقربه های ساعت شماره گذاری شوند، دترمینان های بالا مثبت خواهد شد و می توان از قدر مطلق صرف نظر نمود. اگر به طور منفی (ساعتگرد) مرتب شوند، مقدار محاسبه شده از فرمول مساحت منفی خواهد بود ولی همچنان از نظر قدر مطلقی صحیح است.
مثال ها
کاربر باید مختصات نقاط را در صفحه کارتزین داشته باشد. برای مثال مثلثی را با مختصات {(۲, ۱), (۴, ۵), (۷, ۸)} در نظر بگیرید. اولین مؤلفه x را با دومین مؤلفه y ضرب کنید، سپس دومین مؤلفه x را برداشته و آن را با سومین مقدار y ضرب کنید، و همین روند را تکرار کنید تا اینکه این ضرب ها را برای تمام نقاط انجام داده باشید. این مراحل با فرمول زیر تعریف می شود:
که (xi, yi) معرف مختصات رأس iام هستند. این رابطه همان بسط روابط قبلی در حالت n=3 است. با استفاده از این رابطه می توانیم مساحت مثلث را از طریق محاسبه نصف قدر مطلق مقدار ۱۰ + ۳۲ + ۷ − ۴ − ۳۵ − ۱۶ که برابر ۳ است به دست آورد. تعداد جملات بسط به تعداد اضلاع چند ضلعی بستگی دارد. به عنوان نمونه برای یک پنج ضلعی که تا x5 و y5 تعریف می شود داریم:
همین طور برای یک چهارضلعی که تا x4 و y4 تعریف می شود فرمول محاسبه مساحت به شکل زیر خواهد بود:
مثالی دیگر
چند ضلعی با مختصات (۳,۴)، (۵,۱۱)، (۱۲,۸)، (۹,۵) و (۵,۶) مفروض است و در شکل زیر رسم شده است:
مساحت این چند ضلعی عبارت است از:
A = ۱/۲ | ۳×۱۱ + ۵×۸ + ۱۲×۵ + ۹×۶ + ۵×۴ − ۴×۵ − ۱۱×۱۲ − ۸×۹ − ۵×۵ − ۶×۳ | = ۶۰/۲ = ۳۰
فرمول بند کفش یک فرمول فوق العاده برای محاسبه دقیق مساحت یک چند ضلعی با مختصات رئوس معلوم است.
توضیح نامگذاری
علت نامگذاری این فرمول به فرمول بند کفش به خاطر شیوه ای است که برای محاسبه آن استفاده می شود. این روش از ماتریس ها استفاده می کند. به عنوان یک مثال مثلثی با رئوس (۲,۴)، (۸−,۳) و (۱,۲) را در نظر بگیرید. برای این مثلث ماتریس زیر را با حرکت در یک جهت مشخص بسازید. ماتریسی که با مختصات اولیه پایان می یابد:
در گام اول، خطوط قطری را در جهت پایین و راست بکشید:
و دو عددی که با خط به هم وصل شدند را در هم ضرب کرده سپس حاصلضرب ها را با هم جمع کنید: ۶− = (۱ × ۴) + (۲ × ۳) + (۸− × ۲)
این کار را با خطوط قطری در جهت پایین و چپ انجام دهید:
۸ = (۲ × ۲) + (۱ × ۸−) + (۳ × ۴)
و در ادامه اختلاف این دو عدد را محاسبه کنید: ۱۴ = | (۸) − (۶−) |
با نصف کردن این مقدار، مساحت مثلث به دست می آید: ۷
دسته بندی اعداد مانند این، فرمول را برای یادآوری و استفاده ساده تر می کند. با رسم تمام خطوط قطری، ماتریس حاصل کفشی را با بندهای بسته نشان می دهد و همین دلیل نامگذاری این الگوریتم است.
محدودیت فرمول بند کفش
همانطور که بالاتر هم به آن اشاره شد الگوریتم بند کفش فقط با چند ضلعی های ساده سازگار است. به عبارت دیگر اگر چند ضلعی با خودش تلاقی یا همپوشانی داشته باشد الگوریتم جواب نمی دهد. بنابراین اگر چند ضلعی شما شبیه به یکی از چند ضلعی های تصویر بالا است این روش را برای محاسبه مساحت آن به کار نگیرید چرا که نتایج نادرست خواهند بود.
