Введение

Уже не раз на habr затрагивалась данная тема: раз, два.

Я лишь хочу поделиться своей реализацией. Думаю, это кому-то пригодится.

Предупреждаю, данный метод не учитывает некоторые пограничные случаи и вхождение отрезков друг в друга.

Подготовка

Весь последующий код будет приведён на языке Java

Для начала создадим вспомогательный класс Dot. В нём всего две переменные x и y:

static class Dot {
        float x,y;
        Dot(float x, float y){
            this.x =x;
            this.y = y;
        }
  			
  			@Override
        public String toString() {
            return "x:"+x+" y:"+y;
        }
    }

И класс Vector2. В нём всего две функции: crs (cross) - векторное произведение, scl (scale) - масштабирование вектора.

public static class Vector2 {
        float x,y;

        public Vector2(Dot d1, Dot d2) {
            this.x = d2.x-d1.x;
            this.y = d2.y-d1.y;
        }

        /** Calculates the 2D cross product between this and the given vector.
         * @param v2 the other vector
         * @return the cross product (Z vector) */
        public static float crs(Vector2 v1, Vector2 v2) {
            return v1.x * v2.y - v1.y * v2.x;
        }

        /** Multiplies this vector by a scalar */
        public Vector2 scl (float scalar) {
            x *= scalar;
            y *= scalar;
            return this;
        }
}

Задача 1: определить, касаются ли отрезки.

Решение:
Из векторного произведения мы можем узнать, обхо́дим мы вектор по часовой или против часовой. Это поможет понять где находятся точки. Соединим точки A и D, A и C.

Перемножим вектора main и v2, main и v1. Если полученные произведения имеют разные знаки, значит точки C и D находятся по разные стороны относительно отрезка AB. Назовём такой метод fromDifferentSides:

public static boolean fromDifferentSides(Vector2 main, Vector2 v1, Vector2 v2){
    float product1 =crs(main ,v1), product2 = crs(main ,v2);
    return (product1>=0&&product2<=0 || product1<=0&&product2>=0);
}

Таким же образом необходимо проверить точки A и B относительно отрезка CD. Соединим это в один метод и получится следующее:

public static boolean linesIntersect(Dot a, Dot b, Dot c, Dot d) {
    Vector2 main = new Vector2(a,b);
    Vector2 v1 = new Vector2(a,c);
    Vector2 v2 = new Vector2(a,d);

    if (fromDifferentSides(main,v1,v2)) {
      main = new Vector2(c,d);
      v1 =new Vector2(c,a);
      v2 =new Vector2(c,b);
      return fromDifferentSides(main,v1,v2);
    }
    return false;
}

Задача 2: определить точку касания.

Решение:
Как и в предыдущей задаче определяем, касаются ли отрезки. Если касаются, начинаем определять эту точку. Через подобие найдём длину DO. Коэффициент подобия (k) равен отношению уже известных нам векторных произведений:

//коэффициент подобия
double k = Math.abs(product2 / product1);
if (Float.isInfinite((float) k)) return c;

В третей строчке проверяем пограничный случай. Теперь узнаем чему равно DO. Для этого решим систему уравнений:



DO = CO*k
Подставляем во второе уравнение:
CO*k+CO = CD
CO(k+1)= CD
CO = CD/(k+1)
В итоге:
DO = (CD/(k+1))*k

Теперь создаём вектор CD и уменьшаем его до длинны DO. Но поскольку мы будем его умножать, нужно взять обратное от (k+1)*k:

//вектор DC
Vector2 dc = new Vector2(d, c);

//уменьшаем вектор
dc.scl((float) (1 / (k + 1)*k));

Теперь осталось добавить вектор к точке D:

//добавляем вектор к точке
return new Dot(d.x + dc.x, d.y + dc.y);

Вот и всё! Мы получили заветную точку.

Предупреждаю, данный метод не учитывает некоторые пограничные случаи и вхождение отрезков друг в друга.

Функцию нахождения точки я назвал pointOfIntersection. Привожу полный код на Java:

public class Main {
    public static void main(String[] args) {
        System.out.println(pointOfIntersection(new Dot(0, 0),new Dot(5, 0), new Dot(2, 3),new Dot(2, 0) ));
    }

    public static Dot pointOfIntersection(Dot a, Dot b, Dot c, Dot d) {

        Vector2 main = new Vector2(c,d);
        Vector2 v1= new Vector2(c,a);
        Vector2 v2 = new Vector2(c,b);
        if (fromDifferentSides(main,v1,v2)) {
            main = new Vector2(a,b);
            v1 = new Vector2(a,c);
            v2 = new Vector2(a,d);

            double product1 = crs(main ,v1), product2 = crs(main ,v2);
            if (product1>=0&&product2<=0 || product1<=0&&product2>=0) {
                //коэффициент подобия
                double k = Math.abs(product2 / product1);
                if (Float.isInfinite((float) k)) return c;

                //вектор DC
                Vector2 dc = new Vector2(d, c);

                //уменьшаем вектор
                dc.scl((float) (1 / (k + 1)*k));

                //добавляем вектор к точке
                return new Dot(d.x + dc.x, d.y + dc.y);
            }

        }

        return null;
    }

    public static boolean linesIntersect(Dot a, Dot b, Dot c, Dot d) {
        Vector2 main = new Vector2(a,b);
        Vector2 v1 = new Vector2(a,c);
        Vector2 v2 = new Vector2(a,d);

        if (fromDifferentSides(main,v1,v2)) {
            main = new Vector2(c,d);
            v1 =new Vector2(c,a);
            v2 =new Vector2(c,b);
            return fromDifferentSides(main,v1,v2);
        }
        return false;
    }

    static class Dot {
        float x,y;
        Dot(float x, float y){
            this.x =x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "x:"+x+" y:"+y;
        }
    }


    public static class Vector2 {
        float x,y;

        public Vector2(Dot d1, Dot d2) {
            this.x = d2.x-d1.x;
            this.y = d2.y-d1.y;
        }

        /** Calculates the 2D cross product between this and the given vector.
         * @param v2 the other vector
         * @return the cross product (Z vector) */
        public static float crs(Vector2 v1, Vector2 v2) {
            return v1.x * v2.y - v1.y * v2.x;
        }

        /** Multiplies this vector by a scalar */
        public Vector2 scl (float scalar) {
            x *= scalar;
            y *= scalar;
            return this;
        }

        public static boolean fromDifferentSides(Vector2 main, Vector2 v1, Vector2 v2){
            float product1 =crs(main ,v1), product2 = crs(main ,v2);
            return (product1>=0&&product2<=0 || product1<=0&&product2>=0);
        }
				
      //функция округления
        public static double round(double value, int places) {
            if (places < 0) throw new IllegalArgumentException();
            BigDecimal bd = new BigDecimal(Double.toString(value));
            bd = bd.setScale(places, RoundingMode.HALF_UP);
            return bd.doubleValue();
        }
    }
}

Надеюсь, вам понравилось. Удачи!