پرش به محتویات

محاسبه مساحت چندضلعی ساده در $O(N)$

یک چندضلعی ساده (یعنی بدون خود-تقاطعی و نه لزوماً محدب) داده شده است. می‌خواهیم مساحت آن را با داشتن مختصات رئوسش محاسبه کنیم.

روش اول

این کار با پیمایش تمام یال‌ها و جمع زدن مساحت ذوزنقه‌های محصور بین هر یال و محور x به راحتی قابل انجام است. مساحت باید به صورت علامت‌دار در نظر گرفته شود تا مساحت‌های اضافی حذف شوند. بنابراین، فرمول به شرح زیر است:

$$A = \sum_{(p,q)\in \text{یال‌ها}} \frac{(p_x - q_x) \cdot (p_y + q_y)}{2}$$

کد:

double area(const vector<point>& fig) {
    double res = 0;
    for (unsigned i = 0; i < fig.size(); i++) {
        point p = i ? fig[i - 1] : fig.back();
        point q = fig[i];
        res += (p.x - q.x) * (p.y + q.y);
    }
    return fabs(res) / 2;
}

روش دوم

می‌توانیم یک نقطه دلخواه $O$ انتخاب کرده، تمام یال‌ها را پیمایش کنیم و مساحت جهت‌دار مثلثی که توسط هر یال و نقطه $O$ تشکیل می‌شود را به مجموع اضافه کنیم. در این روش نیز به دلیل علامت‌دار بودن مساحت، قسمت‌های اضافی حذف می‌شوند.

این روش بهتر است زیرا می‌توان آن را به موارد پیچیده‌تر (مانند زمانی که برخی از اضلاع به جای خطوط مستقیم، کمان هستند) تعمیم داد.