حسین کعبی: وقتی فیگو را در جام جهانی زدم....
برنامهنویسی؟ ساده است!
محاسبه مساحت چندضلعی
محاسبه چندضلعی، یکی از مسائل پیچیده برنامهنویسی است که حل آن، برخلاف ظاهرش ساده است. فرض بگیرید یک چندضلعی غیرمحدب دارید که 5راس دارد.
برای یافتن مساحت آن،باید آنرا به مثلثهای کوچکتر تقسیم کنیم. بدین ترتیب میتوانیم با بدست آوردن چند مثلث، مساحت آن را بهدست آوریم. شکل زیر را در نظر بگیرید:
در این چندضلعی، مثلثهای ما، ABC، ACD و ADE هستند. ممکن است شما اعتراض کنید که همه این مثلثها جزئی از شکل نیستند، اما اگر تا انتهای مقاله را بخوانید، کارایی این موضوع را درخواهید یافت. نخست باید حاصل ضرب AB* AC را بیابیم تا مساحت ABC بهدست آید.
بهدلیل شیوه قرارگرفتن راسهای A، B و C، نتیجه مقداری منفی خواهد بود. هر چند میتوانیم همین مقدار را به جمع کلی خود اضافه کنیم. بهطور مشابه، نتیجه AC*AD را هم محاسبه میکنیم تا مساحت مثلث ACD نیز بهدست آید (که آن هم مقداری منفی خواهد شد) و در نهایت مقدار ضرب AD* AE را حساب خواهیم کرد و از آنجایی که این سه مقدار بهگونهای مخالف همدیگر قرار گرفتهاند، (دو منفی و یک مثبت)، خودشان از هم کسر خواهند شد و میتوانیم نتیجه را در قدر مطلق گذاشته و جواب را بهدست بیاوریم.
دلیل درستی روش ما این است که اعداد مثبت و منفی با مقدار دقیقی خودشان را از هم کم میکنند. مساحت ABC و ACD طوری با هم قرار میگیرند که نتیجه نهایی با کسر ADE درست بهدست بیاید. به چندضلعی مجددا نگاه کنید. اگر نتیجهای که بهدست آوردیم منفی بود، نشان میدهد که رئوس این چندضلعی را بهصورت ساعتگرد ترسیم کردهاند. بهتر است این محاسبه را پیاده کنیم:
;0 int area =
int N = lengthof(p);
«N; i++){1; i+1 for(int i =
];0][0] - p[0= p[i][ 1int x
];1][0] - p[1= p[i][ 1int y
];0][0] - p[0][1= p[i+ 2int x
];1][0] - p[1][1= p[i+ 2int y
;1*y2- x 2*y1int cross = x
}area += cross;
);2.0return abs(cross/
خب، حال باید راهحل خود را تعمیم بدهیم تا برای همه چندضلعیها کار کند. توجه داشته باشید که اگر چندضلعی ما بهصورت ساعتگرد چیده شده باشد، نتیجه مثبت و در صورتی که پادساعتگرد باشد، نتیجه منفی است (که البته مهم هم نیست و میتوان با یک قدرمطلق نتیجه نهایی را بهدست آورد.)
مثال زیر را در نظر بگیرید:
نیمی از این شکل بهصورت ساعتگرد ترسیم شده و نیمی دیگر بهصورت پادساعتگرد. از این رو نتیجه این دو بخش، عدد صفر خواهد شد. پس باید مواظب باشیم که هر بار تغییر جهت رخ میدهد، قدرمطلق نتیجه قبلی را با قدرمطلق نتیجه فعلی محاسبه کنیم.
در این شکل نیز، همانطور که مشاهده میکنید، شکل در ناحیه آبی رنگ به دو لایه تقسیم شده است پس باید حواسمان باشد که نتیجهای که محاسبه میشود، برابر است با مساحت منطقه خاکستری +مساحت منطقه آبی ضربدر2.
اگر شکلی داشتیم که دارای تغییر جهت بود، در صورتی که دو شکل مثبت و منفی، با همدیگر تداخل داشتند، آن ناحیه تداخلی در مساحت محاسبه نمیشود و قدرمطلق دو بخش باقیمانده بهعنوان مساحت قرار میگیرد. الگوریتم نهایی ما به شکل زیر خواهد بود:
double polygonArea(double *X, double *Y, int points) {
; 0. ; int i, j=0double area=
; i«points; i++) {0for (i=
;0j++; if (j==points) j=
area+=(X[i]+X[j])*(Y[i]-Y[j]); }
;5.return area*
}
امیربهاالدین سبط الشیخ
گفت و گو
