您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

點在多邊形內部判斷：三大經典算法詳解與 C++ 實現

編輯：C++ 入門

問題背景

判斷點 P(x, y) 是否在多邊形內部，是計算幾何、遊戲開發、GIS 系統中的基礎問題。本文介紹三種主流算法並給出可直接使用的 C++ 代碼。

算法一：射線法—— 最推薦，簡單高效

原理

從測試點向右發射一條水平射線，統計射線與多邊形邊的交點數。奇數交點 → 內部；偶數交點 → 外部。

處理邊界情況

射線穿過頂點：只計算「向上」或「向下」的邊，避免重複計數。
點在邊上：算法結果不確定，需單獨判斷（距離為 0 或叉積為 0 且在線段範圍內）。

經典 C 實現（W. Randolph Franklin）

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) {
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i] > testy) != (verty[j] > testy)) &&
             (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
            c = !c;
    }
    return c;
}

C++ 物件導向版本

struct Point { double x, y; };
bool isInside(const vector& poly, const Point& p) {
    int n = poly.size(), cnt = 0;
    for (int i = 0, j = n-1; i < n; j = i++) {
        const Point& pi = poly[i], &pj = poly[j];
        if ((pi.y > p.y) != (pj.y > p.y)) {
            double x_intersect = (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x;
            if (p.x < x_intersect) cnt ^= 1;
        }
    }
    return cnt;
}

算法二：面積和判別法

將多邊形分解為以測試點為公共頂點的三角形，若所有三角形面積之和等於多邊形面積，則點在內部。缺點：需計算多邊形總面積，精度敏感，效率較低。

算法三：夾角和判別法

計算測試點到各頂點向量的夾角和，內部點和為 2π（360°），外部點為 0。缺點：需調用 acos，計算量大，浮點誤差難控制。

算法對比與選擇建議

算法	時間複雜度	實現難度	精度穩定性	適用場景
射線法	O(n)	低	高（整數坐標可完全避免浮點）	通用首選
面積和	O(n)	中	中（需面積比較）	凸多邊形、教學演示
夾角和	O(n)	中	低（三角函數誤差）	理論分析、特殊需求

邊界情況完整處理模板

// 返回：1=內部, 0=外部, -1=邊上
int pointInPolygon(const vector& poly, const Point& p) {
    int n = poly.size();
    // 先檢查是否在邊上
    for (int i = 0; i < n; ++i) {
        Point a = poly[i], b = poly[(i+1)%n];
        if (fabs(cross(b-a, p-a)) < EPS && dot(p-a, p-b) <= EPS) return -1;
    }
    // 射線法
    int cnt = 0;
    for (int i = 0, j = n-1; i < n; j = i++) {
        if ((poly[i].y > p.y) != (poly[j].y > p.y)) {
            double x = (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x;
            if (p.x < x) cnt ^= 1;
        }
    }
    return cnt;
}