CGL_3_C: Polygon-Point Containment

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q067 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("0 0");
            WillReturn.Add("3 1");
            WillReturn.Add("2 3");
            WillReturn.Add("0 3");
            WillReturn.Add("3");
            WillReturn.Add("2 1");
            WillReturn.Add("0 2");
            WillReturn.Add("3 2");
            //2
            //1
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal double X;
        internal double Y;
    }

    static List<PointDef> mXYInfoList = new List<PointDef>();
    static List<PointDef> mQueryInfoList = new List<PointDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        int N = int.Parse(InputList[0]);

        double[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => double.Parse(X)).ToArray();

        foreach (string EachStr in InputList.Skip(1).Take(N)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mXYInfoList.Add(WillAdd);
        }

        foreach (string EachStr in InputList.Skip(1 + N + 1)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mQueryInfoList.Add(WillAdd);
        }

        foreach (PointDef EachQueryInfo in mQueryInfoList) {
            if (OnSegment(EachQueryInfo)) {
                Console.WriteLine(1);
            }
            else if (IsNaihou(EachQueryInfo)) {
                Console.WriteLine(2);
            }
            else {
                Console.WriteLine(0);
            }
        }
    }

    // 座標を引数として、多角形の辺上の座標かを返す
    static bool OnSegment(PointDef pPoint)
    {
        for (int I = 0; I <= mXYInfoList.Count - 1; I++) {
            PointDef FromPos = mXYInfoList[I];
            int ToInd = I + 1;
            if (mXYInfoList.Count - 1 < ToInd) {
                ToInd = 0;
            }
            PointDef ToPos = mXYInfoList[ToInd];

            if (CCW(FromPos, ToPos, pPoint) == 0) {
                return true;
            }
        }
        return false;
    }

    static int CCW(PointDef pPointA, PointDef pPointB, PointDef pPointC)
    {
        const int COUNTER_CLOCKWISE = 1;
        const int CLOCKWISE = -1;
        const int ONLINE_BACK = 2;
        const int ONLINE_FRONT = -2;
        const int ON_SEGMENT = 0;

        PointDef VectorA = SetVector(pPointA, pPointB);
        PointDef VectorB = SetVector(pPointA, pPointC);

        // 外積 A*Bを求める
        double Cross = DeriveCross(VectorA, VectorB);

        // Aの半時計回りの方向にBが存在する
        if (Cross > 0) {
            return COUNTER_CLOCKWISE;
        }

        // Aの時計回りの方向にBが存在する
        if (Cross < 0) {
            return CLOCKWISE;
        }

        // 3点が1直線にある場合

        // 内積がマイナスなら、ベクトルの向きは反対
        double Dot = DeriveDot(VectorA, VectorB);
        if (Dot < 0) {
            return ONLINE_BACK;
        }

        double NormA = DeriveNorm(VectorA);
        double NormB = DeriveNorm(VectorB);
        if (NormA < NormB) {
            return ONLINE_FRONT;
        }
        return ON_SEGMENT;
    }

    // 座標を引数として、多角形に内包してるかを返す
    static bool IsNaihou(PointDef pPoint)
    {
        double RadSum = 0D;
        for (int I = 0; I <= mXYInfoList.Count - 1; I++) {
            PointDef FromPos = mXYInfoList[I];
            int ToInd = I + 1;
            if (mXYInfoList.Count - 1 < ToInd) {
                ToInd = 0;
            }
            PointDef ToPos = mXYInfoList[ToInd];

            PointDef Vector1 = SetVector(pPoint, FromPos);
            PointDef Vector2 = SetVector(pPoint, ToPos);

            double Dot = DeriveDot(Vector1, Vector2);
            double CosVal = Dot / DeriveABS(Vector1) / DeriveABS(Vector2);
            if (CosVal >= 1D) CosVal = 1D;
            double Theta = Math.Acos(CosVal);
            double Cross = DeriveCross(Vector1, Vector2);
            if (Cross < 0) Theta *= -1D;
            RadSum += Theta;
        }
        return RadSum >= 3.14D;
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    static PointDef SetVector(PointDef pStaPoint, PointDef pEndPoint)
    {
        PointDef WillReturn;
        WillReturn.X = pEndPoint.X - pStaPoint.X;
        WillReturn.Y = pEndPoint.Y - pStaPoint.Y;
        return WillReturn;
    }

    // 内積を求める
    static double DeriveDot(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.X + pVector1.Y * pVector2.Y;
    }

    // 外積を求める
    static double DeriveCross(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.Y - pVector1.Y * pVector2.X;
    }

    // ベクトルの大きさを求める
    static double DeriveABS(PointDef pVector)
    {
        double wkNorm = DeriveNorm(pVector);
        double wkSqrt = Math.Sqrt(wkNorm);
        return wkSqrt;
    }

    // ベクトルのNormを求める
    static double DeriveNorm(PointDef pVector)
    {
        return pVector.X * pVector.X + pVector.Y * pVector.Y;
    }
}

解説

チェック対象の座標から、
多角形の辺の両端に引いたベクトルの角度(符号付き)の合計が360度なら、
多角形の内部だと判定してます。