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

یکی از مسایل مهم در زمینه پردازش تصویر و بررسی الگوریتم‌های هندسی محاسبه مساحت چند ضلعی‌هاست.فرض کنید چند ضلعی $Q$ دارای رئوس $X_1 , X_2,...,X_n$ می‌باشد که به ترتیب پیمایش شده‌اند. حال نقطه ای دلخواه مانند $p$ در صفحه درنظر بگیرید. ادعا می‌کنیم که مساحت $Q$ با در نظر گرفتن علامت برابر است با حاصل جمع علامت‌دار مساحت مثلث‌های$ pX_iX_{i+1} $.با بیانی واضح‌تر، مساحت چند ضلعی $Q$ برابر است با حاصل جمع ضرب خارجی‌های متوالی بردارهای $pX_i$.

$$S_P=\sum_{i=1}^{n+1}\overrightarrow{pA_i} \times \overrightarrow{pA_{i+1}} \,\,\,\,\,\, A_{n+1}=A_1$$

ادعا را با استقرا به روی تعداد رئوس $Q$ اثبات می‌کنیم. به این ترتیب که ابتدا چندضلعی را با کشیدن یک قطر داخلی مثلا $A_iA_j$ (البته با این شرط که این قطر کاملا درون چندضلعی قرار گیرد که نیز نیاز به اثبات داردو بر عهده خواننده می‌باشد!) به دو چندضلعی کوچک تر $Q_1$ و$Q_2$ تقسیم می‌کنیم. حال مقدار $pA_i\times pA_j$ را یک بار با علامت مثبت و یک بار با علامت منفی با حاصل جمع ذکر شده در ابتدای صفحه جمع کرده و با استفاده از فرض استقرا حکم را نتیجه می‌گیریم:

$$S_P= (pA_i \times pA_{i+1} +...+pA_{j-1} \times pA_j +pA_j \times pA_i )$$ $$+(pA_i \times pA_j +( pA_1 \times pA_2 + ...+pA_i-1 \times pA_i)$$ $$+(pA_j \times pA_j+1+...+pA_n \times pA_{n+1}) )\,\,\,\,\,\, A_{n+1}=A_1$$

الگوریتم ذکر شده از مرتبه زمانی $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$ ضلعی منتظم برابر است با $(n-2) \times 180 $ .از طرفی برای محاسبه مجموع زوایا با استفاده از پیمایش روی رئوس می‌بایست به ترتیب ساعت‌گرد راس های چند ضلعی را پیمایش کرده و با استفاده از مقدار ضرب داخلی دو برداری که از یک راس خارج می‌شوند و تقسیم آن بر مقدار حاصل ضرب طول آن دو بردار کسینوس آن زاویه را پیدا کرده و با استفاده از تابع $Cos^{-1}(x)$ مقدار زاویه را محاسبه کنیم. ( با مرتبه زمانی $O(n)$ مجموع زوایا را می‌توان محاسبه کرد.)

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

$V_1 , V_2 , V_3 , V_4 , V_ 5 =(0,0) , (2,3) , (4,5) , (6,8) , (100,0)$

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

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

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