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

একটি সরল পলিগন (অর্থাৎ স্ব-ছেদবিহীন, অগত্যা কনভেক্স নয়) দেওয়া আছে। এর শীর্ষবিন্দু দেওয়া থাকলে ক্ষেত্রফল নির্ণয় করতে হবে।

পদ্ধতি ১#

প্রতিটি বাহু ধরে সামনে এগিয়ে প্রতিটি বাহু ও 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$ দ্বারা গঠিত ত্রিভুজের চিহ্নিত ক্ষেত্রফল যোগ করতে পারি। আবারও, ক্ষেত্রফলের চিহ্নের কারণে, অতিরিক্ত ক্ষেত্রফল কমে যাবে।

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