Convex Polygon ใน C++ : ตรวจสอบรูปหลายเหลี่ยมคอนเว็กซ์

ให้จุดหลายจุดที่ต่อกันเป็นรูปหลายเหลี่ยม (Simple Polygon - ไม่มีขอบตัดกัน) ตรวจสอบว่ารูปนี้เป็น **Convex Polygon (รูปหลายเหลี่ยมคอนเว็กซ์)** หรือไม่

นิยาม Convex: มุมภายในทุกมุม ≤ 180° หรือ **Cross Product ของ Vector ขอบติดกันทุกคู่ มีเครื่องหมายเดียวกัน** (ทั้งหมดบวก หรือทั้งหมดลบ)

ตัวอย่าง

Points: [[0,0], [0,1], [1,1], [1,0]]  // สี่เหลี่ยมจัตุรัส
Output: true (Convex)

อัลกอริทึม: Cross Product Sign Consistency

1. สำหรับแต่ละ Vertex i พิจารณา 3 จุดติดกัน: A = points[i], B = points[(i+1)%n], C = points[(i+2)%n]
2. คำนวณ Cross Product ของ Vector BA และ BC:

   BA = A - B
   BC = C - B
   Cross = BA.x * BC.y - BA.y * BC.x

3. Track ว่าเคยเจอ Cross > 0 (Positive) และ Cross < 0 (Negative) หรือไม่
4. ถ้าเจอ **ทั้งสองเครื่องหมาย** -> **Concave (ไม่ใช่ Convex)** -> Return false
5. จบลูปเจอเครื่องหมายเดียว -> Return true

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        bool neg = false, pos = false;
        int n = points.size();

        for (int i = 0; i < n; i++) {
            int a = i;
            int b = (i + 1) % n;
            int c = (i + 2) % n;

            int cross = calc(points[a][0], points[a][1],
                             points[b][0], points[b][1],
                             points[c][0], points[c][1]);

            if (cross < 0) neg = true;
            else if (cross > 0) pos = true;

            if (neg && pos) return false; // พบทั้งสองเครื่องหมาย -> Concave
        }
        return true;
    }

    int calc(int ax, int ay, int bx, int by, int cx, int cy) {
        int BAx = ax - bx, BAy = ay - by;
        int BCx = cx - bx, BCy = cy - by;
        return BAx * BCy - BAy * BCx; // Cross Product (2D)
    }
};

Input / Output

Input:  [[0,0],[0,1],[1,1],[1,0]]
Output: 1 (true)

ความซับซ้อน (Complexity)

• Time: O(N) — วนลูป 1 รอบ
• Space: O(1)

หมายเหตุ

• โจทย์รับประกันว่าเป็น Simple Polygon (ไม่ต้องเช็ค Self-intersection)
• Cross Product = 0 หมายถึง Collinear (มุม 180°) ยอมรับได้ใน Convex
• ใช้ long long ถ้าพิกัดใหญ่ (ป้องกัน Overflow)

วิธีนี้เป็นมาตรฐานสำหรับ Convex Polygon Check ครับ