C#多邊形求角——實例說_ZenDei技術網路在線

前段時間有寫過一個計算多邊形角度的代碼，這裡給它整理整理，留給自己也送給萌新。看左下圖，這是一個多環的多邊形，一個外環（內部為多邊形內部區域），一個內環（外部為多邊形內部區域），同時多邊形中任意一個角不等於零角（等於 0° 的角）或周角（等於 360° 的角）。註意：本文下文所討論的多邊形求角度不 ...

前段時間有寫過一個計算多邊形角度的代碼，這裡給它整理整理，留給自己也送給萌新。

看左下圖，這是一個多環的多邊形，一個外環（內部為多邊形內部區域），一個內環（外部為多邊形內部區域），同時多邊形中任意一個角不等於零角（等於 0° 的角）或周角（等於 360° 的角）。註意：本文下文所討論的多邊形求角度不包含零角和周角。

現在我們要求 ∠ABC 和 ∠DEF 的大小。那咋算唻?

1. 內積計算夾角

給它加上坐標系（坐標是自己配的，計算出的角度值不一定准確，但不影響角度大小的關係），如右上圖。角度採用向量的內積來求。

以上面的 ∠ABC 為例，數學計算公式如下。

於是乎，有：

角度計算代碼如下：

public struct CxPoint
{
    public CxPoint(double x, double y)
    {
        X = x;
        Y = y;
    }

    public double X;
    public double Y;
}

/// <summary>
/// 計算三點角度，p1-p2-p3為沿環方向的三個連續頂點，其中p2為角點。計算結果範圍 0° - 180°，-1為無效值
/// </summary>
private static double CalculationAngle(CxPoint p1, CxPoint p2, CxPoint p3)
{
    //Cos(Angle) =  a•b/(|a|*|b|)
    double x1 = p1.X - p2.X, y1 = p1.Y - p2.Y;  //向量 a
    double x2 = p3.X - p2.X, y2 = p3.Y - p2.Y;  //向量 b

    //零向量，存在共點
    if (x1 == 0 && y1 == 0) return -1;
    if (x2 == 0 && y2 == 0) return -1;

    double v = x1 * x2 + y1 * y2;   //向量內積 a•b
    double val = Math.Sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2));  //a,b模長乘積 |a|*|b|
    double CosAngle = v / val;  //求出來的值可能略小於 -1 或者略大於 1，此時 Angle 等於 NaN
    double Angle = Math.Acos(CosAngle) * 180.0 / 3.14159265358979;  //兩向量夾角，0-180

    if (System.Double.IsNaN(Angle))
    {
        if (v > 0) return 0;
        else return 180;
    }
    else
    {
        if (Angle > 180) return 180;
        else if (Angle < 0) return 0;
        else return Angle;
    }
}

參考代碼

用上述代碼我們能夠計算得出 ∠ABC = 124.63°，∠DEF = 101.57°。細心的朋友會發現，∠DEF 很明顯是個優角（大於 180° 小於 360° 的角），為什麼求出來是個劣角的值（大於 0° 小於 180° 的角）呢？原來反餘弦函數的值域為 [ 0，π ]，故採用向量內積計算出來的夾角總是在 [ 0°，180° ] 之間。

2. 外積判斷互組

針對像 ∠DEF 這種優角，我們如何計算其結果呢？原來，內積計算的夾角與正確結果必定互為組角（相加等於 360° 的兩個角互為組角），如此 ∠DEF 的正確結果為 360° - 101.57° = 258.43°。故在內積計算夾角後，問題轉換為判別待求角是優角還是劣角，優角則求其組角，劣角則直接是結果。

以 ∠ABC 為例，A → B → C 為環方向，取AC中點M，再取 BM 上靠近 B 點的 B' 點（稱為面內面外判斷點），其中 BB' 的距離很小很小（若直接以 M 點作為面內面外判斷點，由於存在多環的情況，會出現問題）。若 B' 在多邊形內，則待求角為劣角，內積計算夾角即為結果，若 B' 在多邊形外，即出現 ∠DEF 這種情況（此時 B' 是 E'）,則需要求內積計算夾角的組角作為計算結果。

面內面外判斷點求取代碼如下：

/// <summary>
/// 求取面內面外判斷點，p1-p2-p3為沿環方向的三個連續頂點，其中p2為角點。
/// </summary>
private static CxPoint CalculationJudgePoint(CxPoint p1, CxPoint p2, CxPoint p3, double SmallDis = 0.01)
{
    double TempX = (p1.X + p3.X) / 2;
    double TempY = (p1.Y + p3.Y) / 2;

    double DisX = TempX - p2.X;
    double DisY = TempY - p2.Y;
    double val = Math.Sqrt(DisX * DisX + DisY * DisY);

    double Scale = SmallDis / val;

    return new CxPoint(p2.X + Scale * DisX, p2.Y + Scale * DisY);
}

參考代碼

假設，沿著環的方向，多邊形的內部總在環的右側區域，所以在上圖中，∠ABC 所在的環為順時針方向，∠DEF 所在的環為逆時針方向。有了這個假設，我們就能夠用向量外積來判斷 B' （或者是 E'）點是否在面內了。具體做法為計算 ( 待求角角點，沿環方向角點下一頂點 ) 與 ( 待求角角點，面內面外判斷點 ) 的外積（在本文圖中為和）：結果若大於 0，則面內面外判斷點在環的左側和多邊形外部，待求角為優角，求內積計算夾角的組角作為結果；結果若小於等於 0，則面內面外判斷點在環的右側和多邊形內部或邊界上，待求角為劣角或平角，內積計算夾角直接作為結果。

以判斷 B' 在 BC 的哪一側為例，數學計算公式如下。

左右側判斷代碼如下：

public struct CxLine
{
    public CxLine(CxPoint fromPoint, CxPoint toPoint)
    {
        FromPoint = fromPoint;
        ToPoint = toPoint;
    }

    public CxPoint FromPoint;
    public CxPoint ToPoint;
}

/// <summary>
/// 判斷點線上的左方還是右方，在左為 true，線上上或在右為 false
/// </summary>
public static bool JudgAbout(CxLine pLine, CxPoint pPoint)
{
    double ax = pLine.ToPoint.X - pLine.FromPoint.X;
    double ay = pLine.ToPoint.Y - pLine.FromPoint.Y;
    double bx = pPoint.X - pLine.FromPoint.X;
    double by = pPoint.Y - pLine.FromPoint.Y;
    double judge = ax * by - ay * bx;

    if (judge > 0.0)
        return true;
    else
        return false;
}

參考代碼

3. 求角源碼整理

通過上述分析，將所有代碼整理成一個 cs 類。

/// <summary>
    /// 調用示例：AngleCalculation.CxPoint p1 = new AngleCalculation.CxPoint(-112, -12);
    ///           AngleCalculation.CxPoint p2 = new AngleCalculation.CxPoint(-68, -51);
    ///           AngleCalculation.CxPoint p3 = new AngleCalculation.CxPoint(0, 0);
    ///           double angle = AngleCalculation.Analysis(p1, p2, p3, true);
    /// </summary>
    public sealed class AngleCalculation
    {
        public struct CxPoint
        {
            public CxPoint(double x, double y)
            {
                X = x;
                Y = y;
            }

            public double X;
            public double Y;
        }

        public struct CxLine
        {
            public CxLine(CxPoint fromPoint, CxPoint toPoint)
            {
                FromPoint = fromPoint;
                ToPoint = toPoint;
            }

            public CxPoint FromPoint;
            public CxPoint ToPoint;
        }

        /// <summary>
        /// 角度計算主方法，p1-p2-p3為沿環方向的三個連續頂點，其中p2為角點。
        /// </summary>
        /// <param name="IsClockwise">p1-p2-p3所在環方向，順時針為 true，逆時針為 false</param>
        public static double Analysis(CxPoint p1, CxPoint p2, CxPoint p3, bool IsClockwise)
        {
            double Angle = CalculationAngle(p1, p2, p3);
            if (Angle == -1) return Angle;

            CxPoint JudgePoint = CalculationJudgePoint(p1, p2, p3);
            CxLine ReferenceLine = new CxLine(p2, p3);

            bool IsLeft = JudgAbout(ReferenceLine, JudgePoint);

            if (IsClockwise == IsLeft) Angle = 360 - Angle;

            return Angle;
        }

        /// <summary>
        /// 計算三點角度，p1-p2-p3為沿環方向的三個連續頂點，其中p2為角點。計算結果範圍 0° - 180°，-1為無效值
        /// </summary>
        private static double CalculationAngle(CxPoint p1, CxPoint p2, CxPoint p3)
        {
            //Cos(Angle) =  a•b/(|a|*|b|)
            double x1 = p1.X - p2.X, y1 = p1.Y - p2.Y;  //向量 a
            double x2 = p3.X - p2.X, y2 = p3.Y - p2.Y;  //向量 b

            //零向量，存在共點
            if (x1 == 0 && y1 == 0) return -1;
            if (x2 == 0 && y2 == 0) return -1;

            double v = x1 * x2 + y1 * y2;   //向量內積 a•b
            double val = Math.Sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2));  //a,b模長乘積 |a|*|b|
            double CosAngle = v / val;  //求出來的值可能略小於 -1 或者略大於 1，此時 Angle 等於 NaN
            double Angle = Math.Acos(CosAngle) * 180.0 / 3.14159265358979;  //兩向量夾角，0-180

            if (System.Double.IsNaN(Angle))
            {
                if (v > 0) return 0;
                else return 180;
            }
            else
            {
                if (Angle > 180) return 180;
                else if (Angle < 0) return 0;
                else return Angle;
            }
        }

        /// <summary>
        /// 求取面內面外判斷點，p1-p2-p3為沿環方向的三個連續頂點，其中p2為角點。
        /// </summary>
        private static CxPoint CalculationJudgePoint(CxPoint p1, CxPoint p2, CxPoint p3, double SmallDis = 0.01)
        {
            double TempX = (p1.X + p3.X) / 2;
            double TempY = (p1.Y + p3.Y) / 2;

            double DisX = TempX - p2.X;
            double DisY = TempY - p2.Y;
            double val = Math.Sqrt(DisX * DisX + DisY * DisY);

            double Scale = SmallDis / val;

            return new CxPoint(p2.X + Scale * DisX, p2.Y + Scale * DisY);
        }

        /// <summary>
        /// 判斷點線上的左方還是右方，在左為 true，線上上或在右為 false
        /// </summary>
        private static bool JudgAbout(CxLine pLine, CxPoint pPoint)
        {
            double ax = pLine.ToPoint.X - pLine.FromPoint.X;
            double ay = pLine.ToPoint.Y - pLine.FromPoint.Y;
            double bx = pPoint.X - pLine.FromPoint.X;
            double by = pPoint.Y - pLine.FromPoint.Y;
            double judge = ax * by - ay * bx;

            if (judge > 0.0)
                return true;
            else
                return false;
        }
    }
}