সরল পলিগনের ক্ষেত্রফল $O(N)$-এ নির্ণয়#

একটি সরল পলিগন (simple polygon) দেওয়া আছে — মানে এটা নিজেকে ছেদ করে না, তবে কনভেক্স (convex) হতেই হবে এমন কোনো কথা নেই। এর ভার্টেক্সগুলো (vertices) দেওয়া থাকলে ক্ষেত্রফল বের করতে হবে।

পদ্ধতি ১#

প্রতিটি বাহু ধরে সামনে এগিয়ে, প্রতিটি বাহু আর x-অক্ষ দিয়ে তৈরি ট্র্যাপিজয়েডের ক্ষেত্রফল যোগ করলেই এটা সহজে করা যায়। ক্ষেত্রফল চিহ্নসহ নিতে হবে যাতে বাড়তি অংশ বাদ পড়ে যায়। তাই, সূত্রটা এরকম:

কোড:

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$ দিয়ে তৈরি ত্রিভুজের চিহ্নিত ক্ষেত্রফল যোগ করতে পারি। এখানেও, ক্ষেত্রফলের চিহ্নের কারণে বাড়তি অংশ বাদ পড়ে যাবে।

এই পদ্ধতিটা ভালো কারণ এটা আরো জটিল কেসে জেনারালাইজ করা যায় — যেমন যখন কিছু বাহু সরলরেখার বদলে বক্ররেখা হয়।