Java 判斷凸多邊形演算法實作：叉積法解析 HDU 2108

問題描述

給定多邊形頂點坐標（逆時針或順時針輸入），判斷是否為凸多邊形。凸多邊形定義：任意兩點連線完全在多邊形內部，等價於所有相鄰三邊叉積符號一致。

核心算法：向量叉積

對頂點 P[i]、P[i+1]、P[i+2]（索引取模 n），構造向量：

v1 = P[i+1] - P[i]
v2 = P[i+2] - P[i+1]
cross = v1.x * v2.y - v1.y * v2.x

• cross > 0：左轉（逆時針序）。
• cross < 0：右轉（順時針序）。
• cross == 0：共線（視為凸或按題意處理）。

若所有 cross 同號（或零），則為凸多邊形。

Java 完整實現 (HDU 2108)

import java.util.Scanner;

public class ConvexPolygonJudge {
    static class Point {
        int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            
            Point[] p = new Point[n];
            for (int i = 0; i < n; i++) {
                p[i] = new Point(sc.nextInt(), sc.nextInt());
            }
            
            boolean convex = true;
            for (int i = 0; i < n; i++) {
                int j = i;
                int k = (i + 1) % n;
                int t = (i + 2) % n;
                
                Point v1 = new Point(p[k].x - p[j].x, p[k].y - p[j].y);
                Point v2 = new Point(p[t].x - p[k].x, p[t].y - p[k].y);
                int cross = v1.x * v2.y - v1.y * v2.x;
                
                if (cross < 0) { // 假設輸入逆時針，若順時針則檢查 >0
                    convex = false;
                    break;
                }
            }
            
            System.out.println(convex ? "convex" : "concave");
        }
        sc.close();
    }
}

關鍵細節

1. 索引取模：(i+1)%n 處理環狀結構，避免邊界判斷。
2. 方向一致性：題目若未說明頂點順序，需先判斷首個非零叉積符號，作為基準。
3. 共線處理：cross == 0 通常視為凸（允許 180° 角），若題目要求嚴格凸則視為凹。
4. 數據範圍：坐標較大時 cross 可能溢出 int，建議用 long。

複雜度分析

• 時間：O(n)，單次遍歷。
• 空間：O(n) 存頂點，可優化為 O(1) 流式讀取（需保存前兩點）。

擴展：判斷點在凸多邊形內

同樣利用叉積：點對所有邊的叉積符號一致 → 內部；有異號 → 外部；有零 → 邊上。

總結

叉積法是計算幾何基礎技術，向量叉積符號判斷轉向方向 是判斷凸多邊形、點多邊形關係、線段相交等問題的核心工具。HDU 2108 是典型入門題。