using System;
using System.Collections.Generic;
using System.Windows;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace lineTest
{
    class Program
    {
        public struct Point
        {
            public double X;
            public double Y;

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

        static void Main(string[] args)
        {
            Point a = new Point(0, 0);
            Point b = new Point(100, 100);
            Point c = new Point(100,0);
            Point d = new Point(50,49);
            var result = IsIntersect(a, b, c, d);
        }

        public static Point? GetIntersection(Point lineAStart, Point lineAEnd, Point lineBStart, Point lineBEnd)
        {
            double x1 = lineAStart.X, y1 = lineAStart.Y;
            double x2 = lineAEnd.X, y2 = lineAEnd.Y;

            double x3 = lineBStart.X, y3 = lineBStart.Y;
            double x4 = lineBEnd.X, y4 = lineBEnd.Y;

            //equations of the form x=c (two vertical lines)
            if (x1 == x2 && x3 == x4 && x1 == x3)
            {
                return null;
            }

            //equations of the form y=c (two horizontal lines)
            if (y1 == y2 && y3 == y4 && y1 == y3)
            {
                return null;
            }

            //equations of the form x=c (two vertical lines)
            if (x1 == x2 && x3 == x4)
            {
                return null;
            }

            //equations of the form y=c (two horizontal lines)
            if (y1 == y2 && y3 == y4)
            {
                return null;
            }
            double x, y;

            if (x1 == x2)
            {
                double m2 = (y4 - y3) / (x4 - x3);
                double c2 = -m2 * x3 + y3;

                x = x1;
                y = c2 + m2 * x1;
            }
            else if (x3 == x4)
            {
                double m1 = (y2 - y1) / (x2 - x1);
                double c1 = -m1 * x1 + y1;

                x = x3;
                y = c1 + m1 * x3;
            }
            else
            {
                //compute slope of line 1 (m1) and c2
                double m1 = (y2 - y1) / (x2 - x1);
                double c1 = -m1 * x1 + y1;

                //compute slope of line 2 (m2) and c2
                double m2 = (y4 - y3) / (x4 - x3);
                double c2 = -m2 * x3 + y3;

                x = (c1 - c2) / (m2 - m1);
                y = c2 + m2 * x;
            }

            if (IsInsideLine(lineAStart, lineAEnd, x, y) &&
                IsInsideLine(lineBStart, lineBEnd, x, y))
            {
                return new Point(x, y);
            }

            //return default null (no intersection)
            return null;
        }
        private static bool IsInsideLine(Point start, Point end, double x, double y)
        {
            return ((x >= start.X && x <= end.X)
                || (x >= end.Y && x <= start.Y))
                && ((y >= start.Y && y <= end.Y)
                    || (y >= end.Y && y <= start.Y));
        }

        public static bool IsIntersect(Point p1, Point p2, Point q1, Point q2)
        {
            //排斥試驗，判斷p1p2在q1q2為對角線的矩形區之外
            if (Math.Max(p1.X, p2.X) < Math.Min(q1.X, q2.X))
            {//P1P2中最大的X比Q1Q2中的最小X還要小，說明P1P2在Q1Q2的最左點的左側，不可能相交。
                return false;
            }

            if (Math.Min(p1.X, p2.X) > Math.Max(q1.X, q2.X))
            {//P1P2中最小的X比Q1Q2中的最大X還要大，說明P1P2在Q1Q2的最右點的右側，不可能相交。
                return false;
            }

            if (Math.Max(p1.Y, p2.Y) < Math.Min(q1.Y, q2.Y))
            {//P1P2中最大的Y比Q1Q2中的最小Y還要小，說明P1P2在Q1Q2的最低點的下方，不可能相交。
                return false;
            }

            if (Math.Min(p1.Y, p2.Y) > Math.Max(q1.Y, q2.Y))
            {//P1P2中最小的Y比Q1Q2中的最大Y還要大，說明P1P2在Q1Q2的最高點的上方，不可能相交。
                return false;
            }

            //跨立試驗
            var crossP1P2Q1 = VectorCross(p1, p2, q1);
            var crossP1Q2P2 = VectorCross(p1, q2, p2);
            var crossQ1Q2P1 = VectorCross(q1, q2, p1);
            var crossQ1P2Q2 = VectorCross(q1, p2, q2);

            bool isIntersect = (crossP1P2Q1 * crossP1Q2P2 >= 0) && (crossQ1Q2P1 * crossQ1P2Q2 >= 0);
            return isIntersect;
        }

        private static double VectorCross(Point p1, Point p2, Point p3)
        {
            Vector vectorP1 = new Vector(p1.X, p1.Y);
            Vector vectorP2 = new Vector(p2.X, p2.Y);
            Vector vectorP3 = new Vector(p3.X, p3.Y);
            Vector vectorP1P2 = Vector.Subtract(vectorP2, vectorP1);
            Vector vectorP1P3 = Vector.Subtract(vectorP3, vectorP1);
            return Vector.CrossProduct(vectorP1P2, vectorP1P3);
        }
    }
}