Нахождение точки пересечения двух прямых (и отрезков)
Довольно часто при разработке игр возникает необходимость находить точку пересечения прямых, отрезков, лучей и т.д. О том, как реализовать это максимально простым способом, в этой статье.
Популярные способы и их критика
Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти x, и подставить его в уравнение прямой, чтобы найти y (Подробнее здесь).
Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые перпендикулярны осям, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.
В поисках более элегантного решения данной проблемы я наткнулся на весьма интересные способы, основанные на векторном умножении ( habr.com/ru/post/267037 ) и ray castinging’е ( ru.wikipedia.org/wiki/Ray_casting#Концепция ). Но на мой взгляд, они неоправданно сложные в вычислительном плане. Поэтому представляю вашему вниманию (и критике) мой способ.
Мой способ
Задача
Даны координаты двух отрезков. Нужно узнать, пересекаются ли отрезки, и если да, в какой точке. Для этой цели напишем функцию.
Решение
Условные обозначения для исключения недопониманий: a — вектор a, a(y) — проекция вектора a на ось Y, a
Представим наши отрезки в виде двух векторов: a
a(x)*k+b(x)*n=c(x)
a(y)*k+b(y)*n=c(y)
Наша задача сводится к нахождению этих коэффициентов (правда сказать, достаточно найти лишь один из них).
Предлагаю домножить обе части нижнего уравнения на q= -a(x)/a(y). Так после сложения двух уравнений, мы сразу избавимся от k. Нахождение n сведётся к решению обыкновенного линейного уравнения. Важно обратить внимание, что у n может не быть решения.
Внимательный читатель заметит, что при a(y)=0, мы получим ошибку. Пропишем ветвление на этапе нахождения a(y). Этот случай ещё проще, ведь мы сразу получаем уравнение с одной неизвестной.
Рекомендую попробовать вывести n самостоятельно, так будет понятнее, что откуда берётся в коде ниже.
Зная n, можно найти точку пересечения, для этого мы отнимем от координаты точки (x3,y3) вектор b*n
Собираем воедино
Данная функция принимает координаты вершин и возвращает значение 1, если прямые отрезков (именно прямые) пересекаются, иначе 0. Если же вам нужны координаты вершин, вы сможете взять их из массива dot[].
Важно: при введении двух совпадающих прямых, алгоритм выводит отсутствие пересечения. Алгоритм находит точку пересечения прямых, на которых лежат отрезки, поэтому точка может оказаться за пределами отрезка (что вам придётся дополнительно проверить в уже своём коде).
Определение точки пересечения двух отрезков
Пусть даны два отрезка. Первый задан точками P1(x1;y1) и P2(x2;y2). Второй задан точками P3(x3;y3) и P4(x4;y4). 
Взаимное расположение отрезков можно проверить с помощью векторных произведений: 
Рассмотрим отрезок P3P4 и точки P1 и P2. 
Точка P1 лежит слева от прямой P3P4, для нее векторное произведение v1 > 0, так как векторы положительно ориентированы.
Точка P2 расположена справа от прямой, для нее векторное произведение v2 < 0, так как векторы отрицательно ориентированы.
Для того чтобы точки P1 и P2 лежали по разные стороны от прямой P3P4, достаточно, чтобы выполнялось условие v1v2 < 0 (векторные произведения имели противоположные знаки).
Аналогичные рассуждения можно провести для отрезка P1P2 и точек P3 и P4.
Векторное произведение двух векторов вычисляется по формуле: 
где:
ax, ay — координаты первого вектора,
bx, by — координаты второго вектора.
Уравнение прямой, проходящей через две различные точки, заданные своими координатами.
Пусть на прямой заданы две не совпадающие точки:P1 с координатами (x1;y1) и P2 с координатами (x2; y2). Соответственно вектор с началом в точке P1 и концом в точке P2 имеет координаты (x2-x1, y2-y1). Если P(x, y) – произвольная точка на прямой, то координаты вектора P1P равны (x — x1, y – y1).
Итак, прямую можно задать уравнением вида (1).
Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:
Здесь D – определитель системы, а Dx,Dy — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0, то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x1=Dx/D, y1=Dy/D, которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Найти точку пересечения отрезков
В статье покажем, как найти точку пересечения отрезков. Это совсем не тривиальная задача, хотя на первый взгляд она кажется именно такой. Поиск пересечения двух отрезков имеет множество полезных приложений. Например, с помощью него можно определить пересекаются ли фигуры на плоскости или нет.
Начальные условия
На протяжении всей статьи мы будем писать метод, который ищет пересечение двух отрезков на плоскости и даёт ответ: пересекаются они или нет.
Входными параметрами метода являются 4 точки — точки начала и конца двух отрезков.
Точка — это экземпляр класса Point. Она имеет два параметра: значение абсциссы (x) и значение ординаты (y). Класс Point:
Поиск пересечения двух отрезков
Метод, который будет искать пересечение двух отрезков, назовём: checkIntersectionOfTwoLineSegments. Он возвращает true, если отрезки пересекаются и false в противном случае.
Его аргументы — это четыре точки. p1 и p2 — начало и конец первого отрезка, а p3 и p4 — соответственно начало и конец второго отрезка.
Мы подразумеваем, что начальная точка находится левее конечной относительно оси абсцисс (оси X). Также возможен вариант, когда точки имеют одинаковую абсциссу, то есть отрезок является вертикальным.
В общем случае должно выполняться условие: p1.x <= p2.x и p3.x <= p4.x.
Но если вдруг программист задал точки отрезка не по порядку, мы расставим их, как следует:
После того, как точки отрезков расставлены по порядку, мы можем сразу проверить наличие потенциального интервала, на котором отрезки могут пересекаться.
Если конец первого отрезка находится левее начала правого отрезка (по оси X), то отрезки точно не имеют точки пересечения.
Потенциальный интервал пересечения имеется. Идём далее.
Оба отрезка вертикальные (частный случай)
Мы отдельно от общего решения будем рассматривать вертикальные отрезки, поскольку тангенс 90 градусов не определён, и, тем самым, мы в общем решении избежим деления на ноль.
Сначала обсудим такой частный случай, когда оба отрезка являются вертикальными.
Непересекающиеся (слева) и пересекающиеся (справа) вертикальные отрезки
Отрезок вертикальный, тогда и только тогда, когда абсциссы его обеих точек равны.
В случае проверки условия вертикальности обоих отрезков, выражение (p1.x — p2.x == 0) && (p3.x — p4.x == 0) должно быть истинным.
Два отрезка будут иметь точку пересечения в том случае, когда их абсцисса одинакова (для этого достаточно условия p1.x == p3.x) и они имеют общую часть по оси ординат (общий Y); в противном случае делаем вывод, что они не пересекаются.
Составить условие для проверки существования общего Y мысленно довольно сложно. Поэтому мы поступим проще: составим условие для проверки того, что отрезки не имеют общего Y и возьмём от него отрицание.
Напишем код на Java для всего вышесказанного:
Решаем систему уравнений и находим точку пересечения отрезков
Каждый отрезок — это часть прямой. Уравнение прямой в общем случае имеет всем нам знакомый вид:
A * x + b = y (1)
Для случая с двумя прямыми получаем систему уравнений (2):
A1 * x + b1 = y
A2 * x + b2 = y
Решив её, мы получим координаты точки (x, y) пересечения двух прямых. Но у нас нет значений параметров A1, A2, b1 и b2. Найдём их.
Параметр A — это тангенс угла между прямой и осью X. Вычислим его по определению: тангенс — это отношение противолежащего катета к прилежащему.
A1 = (p1.y — p2.y) / (p1.x — p2.x) (3)
A2 = (p3.y — p4.y) / (p3.x — p4.x) (4)
Параметр b найдём для каждой прямой, выразив его из уравнений (2):
b1 = p1.y — A1 * p1.x = p2.y — A1 * p2.x (5)
b2 = p3.y — A2 * p3.x = p4.y — A2 * p4.x (6)
Теперь, зная все параметры, решим систему уравнений (2). Найдём абсциссу точки пересечения прямых (обозначим её Xa):
Xa = (b2 — b1) / (A1 — A2) (7)
Как практически в любом решении и, к сожалению, здесь тоже есть частные случаи, о которых следует поговорить отдельно.
При нахождении параметров A1 и A2 (уравнения 3, 4) может возникнуть исключительная ситуация деления на ноль. Такое возможно, когда один из отрезков вертикальный.
Один из отрезков вертикальный (частный случай)
Сначала рассмотрим ситуацию, когда первый отрезок вертикальный.
Предположим, что x вертикального отрезка является абсциссой точки пересечения отрезков: Xa = p1.x. Параметры A2 и b2 найдём, как это было описано выше. Также вычислим ординату предполагаемой точки пересечения (используя формулу 1):
Найденная точка (Xa, Ya) будет являться точкой пересечения двух отрезков только в том случае, если p3.x <= Xa <= p4.x и Ya входит в интервал вертикального отрезка по Y. В противном случае — отрезки не пересекаются.