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


{{ :آموزش:الگوریتم:image_of_proof_2.png?200 |}}


$$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)$ می‌باشد.
===== پیاده‌سازی اولیه =====

<code c 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);
}    

</code>


===== جمع زوایا =====

به طور کلی مجموع زوایای داخلی هر $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)$



===== مراجع =====

- [[http://geomalgorithms.com/a01-_area.html|محاسبه مساحت]]

----------------

- [[http://stackoverflow.com/questions/451426/how-do-i-calculate-the-area-of-a-2d-polygon|پیاده سازی اولیه]]  

----------------


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


~~DISCUSSION~~