یکی از مسایل مهم در زمینه پردازش تصویر و بررسی الگوریتمهای هندسی محاسبه مساحت چند ضلعیهاست.فرض کنید چند ضلعی Q دارای رئوس X1,X2,...,Xn میباشد که به ترتیب پیمایش شدهاند. حال نقطه ای دلخواه مانند p در صفحه درنظر بگیرید. ادعا میکنیم که مساحت Q با در نظر گرفتن علامت برابر است با حاصل جمع علامتدار مساحت مثلثهایpXiXi+1.با بیانی واضحتر، مساحت چند ضلعی Q برابر است با حاصل جمع ضرب خارجیهای متوالی بردارهای pXi.
SP=n+1∑i=1→pAi×→pAi+1An+1=A1
ادعا را با استقرا به روی تعداد رئوس Q اثبات میکنیم. به این ترتیب که ابتدا چندضلعی را با کشیدن یک قطر داخلی مثلا AiAj (البته با این شرط که این قطر کاملا درون چندضلعی قرار گیرد که نیز نیاز به اثبات داردو بر عهده خواننده میباشد!) به دو چندضلعی کوچک تر Q1 وQ2 تقسیم میکنیم. حال مقدار pAi×pAj را یک بار با علامت مثبت و یک بار با علامت منفی با حاصل جمع ذکر شده در ابتدای صفحه جمع کرده و با استفاده از فرض استقرا حکم را نتیجه میگیریم:
SP=(pAi×pAi+1+...+pAj−1×pAj+pAj×pAi)
الگوریتم ذکر شده از مرتبه زمانی O(n) و حافطه مصرف شده از مرتبه O(1) میباشد.
به طور کلی مجموع زوایای داخلی هر n ضلعی منتظم برابر است با (n−2)×180 .از طرفی برای محاسبه مجموع زوایا با استفاده از پیمایش روی رئوس میبایست به ترتیب ساعتگرد راس های چند ضلعی را پیمایش کرده و با استفاده از مقدار ضرب داخلی دو برداری که از یک راس خارج میشوند و تقسیم آن بر مقدار حاصل ضرب طول آن دو بردار کسینوس آن زاویه را پیدا کرده و با استفاده از تابع Cos−1(x) مقدار زاویه را محاسبه کنیم. ( با مرتبه زمانی O(n) مجموع زوایا را میتوان محاسبه کرد.)
برای مثال میتوانید مساحت 5 ضلعی زیر را با استفاده از روش ذکر شده محاسبه کنید:
V1,V2,V3,V4,V5=(0,0),(2,3),(4,5),(6,8),(100,0)
خوانندهی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهدهی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:
نظرات