C 語言判斷點在多邊形內部：射線法核心算法與三種實現變體

點在多邊形內判斷是圖形學、GIS、遊戲碰撞的基礎運算。射線法（Ray Casting）以 O(n) 時間、O(1) 空間成為通用標準：從點向任意方向發射射線，統計與多邊形邊相交次數，奇數在內、偶數在外。

一、 幾何原理

若射線與多邊形邊相交奇數次，點在內部；偶數次在外部。需處理邊界情況：點在頂點、點在邊上、射線穿過頂點。

二、 經典 C 實現（整數座標）

// 返回 1 內部，0 外部，-1 邊界
int pointInPolygon(int n, const Point* poly, Point p) {
    int inside = 0;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        const Point *pi = &poly[i], *pj = &poly[j];
        // 檢查點是否在邊上
        if (onSegment(*pi, *pj, p)) return -1;
        // 射線相交判斷：(yi > y) != (yj > y) 且 x < 交點x
        if ((pi->y > p.y) != (pj->y > p.y)) {
            double x_intersect = (double)(pj->x - pi->x) * (p.y - pi->y) / (pj->y - pi->y) + pi->x;
            if (p.x < x_intersect) inside = !inside;
        }
    }
    return inside;
}

// 輔助：點在線段上（含端點）
int onSegment(Point a, Point b, Point p) {
    return cross(b - a, p - a) == 0 && dot(p - a, p - b) <= 0;
}

三、 三種優化變體

四、 邊界情況處理清單

• 點在頂點：返回 -1（邊界）。
• 點在水平邊上：返回 -1。
• 射線穿過頂點：(yi > y) != (yj > y) 條件天然去重，避免雙計數。
• 多邊形非簡單（自相交）：射線法仍有效，結果為繞數奇偶性。

五、 總結

射線法是點在多邊形判斷的「瑞士軍刀」：原理簡單、實現靈活、擴展性強。工程中首選成熟庫（CGAL、Clipper、JTS），自行實現時務必建立完整邊界測試用例集。