非凸多角形に対して、a番目, b番目(a<b)の頂点を結んだときに他の辺と交差するかどうかを判定する

crossed.cs

        /// <summary>
        /// 非凸多角形に対して、a番目, b番目(a<b)の頂点を結んだときに他の辺と交差するかどうかを判定する
        /// </summary>
        /// <param name="pts">多角形の点列。点の並びが反時計回りになっていることを期待している。</param>
        /// <param name="a">a番目の点</param>
        /// <param name="b">b番目の点</param>
        /// <returns>交差すれば true</returns>
        private bool Crossed(PointF[] pts, int a, int b)
        {
            float abX = pts[b].X - pts[a].X;
            float abY = pts[b].Y - pts[a].Y;

            bool positive;

            // a番目の頂点から番号が増える順にb番目までをチェックする
            int p = a + 1;
            for (int t = 0; t < b-a-1; t++)
            {
                float apX = pts[p].X - pts[a].X;
                float apY = pts[p].Y - pts[a].Y;
                float bpX = pts[p].X - pts[b].X;
                float bpY = pts[p].Y - pts[b].Y;
                p++;

                // 線分判定：ABとAP(もしくは BAとBP)のなす角度が90度より大きければ線分の外の点
                // * 内積を利用
                if (abX * apX + abY * apY < 0 || -abX * bpX - abY * bpY < 0)
                {
                    continue;
                }
                // ABからAPを見込む角度の正負を計算
                // * 外積を利用
                positive = (abX * apY - abY * apX) >= 0;
                if (!positive)
                {
                    return true;
                }
            }

            // a番目の頂点から番号が減る順にb番目までをチェックする
            p = (a - 1 + pts.Length) % pts.Length;
            for (int t = 0; t < pts.Length - b + a - 1; t++)
            {
                float apX = pts[p].X - pts[a].X;
                float apY = pts[p].Y - pts[a].Y;
                float bpX = pts[p].X - pts[b].X;
                float bpY = pts[p].Y - pts[b].Y;

                p--;
                p = (p + pts.Length) % pts.Length;

                // 線分判定：ABとAP(もしくは BAとBP)のなす角度が90度より大きければ線分の外の点
                // * 内積を利用
                if (abX * apX + abY * apY < 0 || -abX * bpX - abY * bpY < 0)
                {
                    continue;
                }
                // ABからAPを見込む角度の正負を計算(逆回りなので符号が反転)
                // * 外積を利用
                positive = (abX * apY - abY * apX) >= 0;
                if (positive)
                {
                    return true;
                }
            }
            return false;
        }