C# 射線法判斷點是否在多邊形內部：完整演算法與邊界處理

演算法原理

從測試點向固定方向 (通常 +X 或 -Y) 發射射線，統計與多邊形邊的交點數：

• 奇數 → 點在內部
• 偶數 (含 0) → 點在外部

關鍵邊界情況處理

1. 點在邊上：直接視為內部 (或依業務定義)
2. 射線經過頂點：避免重複計數，採用「只計算上端點、不計下端點」或「Y 嚴格大於」規則
3. 水平邊：平行射線不產生交點，直接跳過
4. 浮點精度：引入 EPS = 1e-10 進行模糊比較

健壯實作

public struct PointD { public double X, Y; }

public static class PolygonHelper
{
    private const double EPS = 1e-10;

    /// 

    /// 判斷點是否在多邊形內部 (含邊界)
    /// 
    public static bool Contains(PointD pt, IReadOnlyList polygon)
    {
        if (polygon.Count < 3) return false;
        bool inside = false;

        for (int i = 0, j = polygon.Count - 1; i < polygon.Count; j = i++)
        {
            var pi = polygon[i];
            var pj = polygon[j];

            // 1. 點在邊上直接回傳 true
            if (PointOnSegment(pt, pi, pj)) return true;

            // 2. 射線與邊相交判斷 (向 +X 方向)
            // 條件：邊跨越射線的 Y 座標，且交點在點的右側
            bool intersect = ((pi.Y > pt.Y) != (pj.Y > pt.Y)) &&
                             (pt.X < (pj.X - pi.X) * (pt.Y - pi.Y) / (pj.Y - pi.Y) + pi.X);

            if (intersect) inside = !inside;
        }
        return inside;
    }

    private static bool PointOnSegment(PointD p, PointD a, PointD b)
    {
        // 向量叉積為 0 (共線) 且點在矩形包圍盒內
        double cross = (p.X - a.X) * (b.Y - a.Y) - (p.Y - a.Y) * (b.X - a.X);
        if (Math.Abs(cross) > EPS) return false;

        double dot = (p.X - a.X) * (p.X - b.X) + (p.Y - a.Y) * (p.Y - b.Y);
        return dot <= EPS; // 允許微小誤差
    }
}

測試案例

var square = new List
{
    new PointD { X = 0, Y = 0 },
    new PointD { X = 10, Y = 0 },
    new PointD { X = 10, Y = 10 },
    new PointD { X = 0, Y = 10 }
};

Console.WriteLine(PolygonHelper.Contains(new PointD { X = 5, Y = 5 }, square));   // True (內部)
Console.WriteLine(PolygonHelper.Contains(new PointD { X = 0, Y = 5 }, square));   // True (邊界)
Console.WriteLine(PolygonHelper.Contains(new PointD { X = 15, Y = 5 }, square));  // False (外部)
Console.WriteLine(PolygonHelper.Contains(new PointD { X = 5, Y = 10 }, square));  // True (頂點)

效能與擴充

常見錯誤與修正

• 整數除法截斷：座標運算務必用 double，避免 int 導致交點判斷錯誤。
• 忽略水平邊：水平邊 pi.Y == pj.Y 時 (pi.Y > pt.Y) != (pj.Y > pt.Y) 為 false，自然跳過，無需特判。
• 頂點重複計數：採用 (pi.Y > pt.Y) != (pj.Y > pt.Y) 寫法，天然只計算上端點，避免射線穿過頂點時雙計數。

總結

射線法 (Ray Casting) 是點在多邊形判斷的標準演算法，核心在於正確處理邊界與頂點情況。上述實作以 double 精度、EPS 模糊比較、標準交點判斷邏輯，能可靠處理凸/凹多邊形、含洞多邊形 (需依規則調整) 等一般幾何應用場景。