Энгийн олон өнцөгтийн талбайг $O(N)$-д олох¶

Энгийн олон өнцөгт (өөрөөр хэлбэл өөрөө огтлолцохгүй, заавал гүдгэр байх албагүй) өгөгдсөн байг. Түүний оройнууд өгөгдсөн үед талбайг нь тооцоолох шаардлагатай.

1-р арга¶

Хэрэв бид бүх ирмэгийг тойрч, ирмэг бүр ба x тэнхлэгээр хүрээлэгдсэн трапецын талбайг нэмбэл үүнийг хийхэд амархан. Илүү талбай хасагдахын тулд талбайг тэмдэгтэй нь авах хэрэгтэй. Тиймээс томьёо дараах байдалтай байна:

$$A = \sum_{(p,q)\in \text{edges}} \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;
}

2-р арга¶

Бид $O$ цэгийг дурмаар сонгож, бүх ирмэгийг тойрч, ирмэг ба $O$ цэгийн үүсгэсэн гурвалжны чиглэлтэй талбайг нэмж болно. Дахин хэлэхэд талбайн тэмдгийн улмаас илүү талбай хасагдана.

Энэ арга илүү дээр, учир нь үүнийг илүү нарийн төвөгтэй тохиолдолд (жишээ нь зарим тал шулууны оронд нум байх үед) ерөнхийлж болно