Slicker Algorithm หาพื้นที่ Polygon ใน C++ (ไม่ต้อง Triangulation)

Slicker Algorithm (หรือ Shoelace Formula) คำนวณพื้นที่ polygon โดยตรงจากพิกัดจุดโหนด ไม่ต้องแยกเป็นสามเหลี่ยม

สูตรคณิตศาสตร์

สำหรับ polygon ที่มีโหนด (x₀,y₀), (x₁,y₁), ..., (xₙ₋₁,yₙ₋₁) เรียงตามเข็มนาฬิกาหรือทวนเข็มนาฬิกา:

Area = ½ | Σ(xᵢ * yᵢ₊₁ - xᵢ₊₁ * yᵢ) |  โดย i = 0 ถึง n-1 และ (xₙ, yₙ) = (x₀, y₀)

คุณสมบัติ

• ทำงานได้กับ polygon ทุกประเภท (convex, concave, self-intersecting)
• ผลลัพธ์เป็น signed area: บวก = counter-clockwise, ลบ = clockwise
• Complexity: O(n) ใช้หน่วยความจำ O(1)

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
};

double polygonArea(const vector<Point>& poly) {
    int n = poly.size();
    if (n < 3) return 0.0;
    
    double area = 0.0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
    }
    return fabs(area) / 2.0;
}

// สigned area (เก็บเครื่องหมายเพื่อรู้ winding order)
double signedPolygonArea(const vector<Point>& poly) {
    int n = poly.size();
    if (n < 3) return 0.0;
    
    double area = 0.0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
    }
    return area / 2.0;
}

int main() {
    // ตัวอย่าง: รูปหกเหลี่ยมไม่สม่ำเสมอ
    vector<Point> polygon = {
        {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 7}
    };
    
    cout << "Polygon vertices:" << endl;
    for (int i = 0; i < polygon.size(); ++i) {
        cout << "  " << i << ": (" << polygon[i].x << ", " << polygon[i].y << ")" << endl;
    }
    
    double area = polygonArea(polygon);
    double signedArea = signedPolygonArea(polygon);
    
    cout << "\nSigned area: " << signedArea << endl;
    cout << "Area (absolute): " << area << endl;
    cout << "Winding order: " << (signedArea > 0 ? "Counter-clockwise" : "Clockwise") << endl;
    
    // รับ input จากผู้ใช้
    cout << "\n--- ป้อน polygon เอง ---" << endl;
    int n;
    cout << "จำนวนโหนด (น้อยที่สุด 3): ";
    cin >> n;
    
    if (n >= 3) {
        vector<Point> userPoly(n);
        cout << "ป้อนพิกัด x y ของแต่ละโหนด:" << endl;
        for (int i = 0; i < n; ++i) {
            cout << "  โหนด " << i << ": ";
            cin >> userPoly[i].x >> userPoly[i].y;
        }
        
        double userArea = polygonArea(userPoly);
        cout << "\nพื้นที่ Polygon " << n << " โหนด: " << userArea << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Polygon vertices:
  0: (1, 1)
  1: (2, 2)
  2: (3, 3)
  3: (4, 4)
  4: (5, 5)
  5: (6, 7)

Signed area: 2.5
Area (absolute): 2.5
Winding order: Counter-clockwise

การยืนยันสูตร (Verification)

// ทดสอบกับรูปสี่เหลี่ยมจัตุรัส (0,0) (4,0) (4,3) (0,3) -> พื้นที่ = 12
vector<Point> rect = {{0,0}, {4,0}, {4,3}, {0,3}};
cout << "Rectangle area: " << polygonArea(rect) << endl; // 12

// สามเหลี่ยม (0,0) (4,0) (0,3) -> พื้นที่ = 6
vector<Point> tri = {{0,0}, {4,0}, {0,3}};
cout << "Triangle area: " << polygonArea(tri) << endl; // 6

ข้อดีของ Slicker Algorithm

• ไม่ต้อง triangulate (ซับซ้อน O(n log n) หรือ O(n²))
• โค้ดสั้น กระชับ เข้าใจง่าย
• ทำงานได้กับ polygon ที่ self-intersecting (ได้ signed area)
• เหมาะสำหรับ real-time applications

ข้อควรระวัง

• จุดโหนดต้องเรียงลำดับ (CW หรือ CCW) ถูกต้อง
• Polygon ต้องปิด (จุดสุดท้ายเชื่อมจุดแรก) - โค้ดจัดการด้วย modulo
• Self-intersecting polygon จะได้พื้นที่ "net area" (บางส่วนอาจลบกัน)