المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:مساحت چندضلعی و جمع زوایا

مساحت چند ضلعی و جمع زوایا

مساحت چند ضلعی

یکی از مسایل مهم در زمینه پردازش تصویر و بررسی الگوریتم‌های هندسی محاسبه مساحت چند ضلعی‌هاست.فرض کنید چند ضلعی Q دارای رئوس X1,X2,...,Xn می‌باشد که به ترتیب پیمایش شده‌اند. حال نقطه ای دلخواه مانند p در صفحه درنظر بگیرید. ادعا می‌کنیم که مساحت Q با در نظر گرفتن علامت برابر است با حاصل جمع علامت‌دار مساحت مثلث‌هایpXiXi+1.با بیانی واضح‌تر، مساحت چند ضلعی Q برابر است با حاصل جمع ضرب خارجی‌های متوالی بردارهای pXi.

SP=n+1i=1pAi×pAi+1An+1=A1

اثبات ادعا

ادعا را با استقرا به روی تعداد رئوس Q اثبات می‌کنیم. به این ترتیب که ابتدا چندضلعی را با کشیدن یک قطر داخلی مثلا AiAj (البته با این شرط که این قطر کاملا درون چندضلعی قرار گیرد که نیز نیاز به اثبات داردو بر عهده خواننده می‌باشد!) به دو چندضلعی کوچک تر Q1 وQ2 تقسیم می‌کنیم. حال مقدار pAi×pAj را یک بار با علامت مثبت و یک بار با علامت منفی با حاصل جمع ذکر شده در ابتدای صفحه جمع کرده و با استفاده از فرض استقرا حکم را نتیجه می‌گیریم:

SP=(pAi×pAi+1+...+pAj1×pAj+pAj×pAi)

+(pAi×pAj+(pA1×pA2+...+pAi1×pAi)
+(pAj×pAj+1+...+pAn×pAn+1))An+1=A1

پیچیدگی الگوریتم

الگوریتم ذکر شده از مرتبه زمانی O(n) و حافطه مصرف شده از مرتبه O(1) می‌باشد.

پیاده‌سازی اولیه

A.c
int cross(vct a,vct b,vct c)
{
    vct ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}    
double area(vct p[],int n)
{ 
    int ar=0;
    for(i=1;i+1<n;i++)
    {
        vct a=p[i]-p[0];
        vct b=p[i+1]-p[0];
        area+=cross(a,b);
    }
    return abs(area/2.0);
}

جمع زوایا

به طور کلی مجموع زوایای داخلی هر n ضلعی منتظم برابر است با (n2)×180 .از طرفی برای محاسبه مجموع زوایا با استفاده از پیمایش روی رئوس می‌بایست به ترتیب ساعت‌گرد راس های چند ضلعی را پیمایش کرده و با استفاده از مقدار ضرب داخلی دو برداری که از یک راس خارج می‌شوند و تقسیم آن بر مقدار حاصل ضرب طول آن دو بردار کسینوس آن زاویه را پیدا کرده و با استفاده از تابع Cos1(x) مقدار زاویه را محاسبه کنیم. ( با مرتبه زمانی O(n) مجموع زوایا را می‌توان محاسبه کرد.)

مسائل نمونه

برای مثال می‌توانید مساحت 5 ضلعی زیر را با استفاده از روش ذکر شده محاسبه کنید:

V1,V2,V3,V4,V5=(0,0),(2,3),(4,5),(6,8),(100,0)

مراجع

- محاسبه مساحت


- پیاده سازی اولیه


خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:

نظرات

نظر خود را وارد کنید. دستورات ویکی مجاز است:
 

ابزار صفحه