Нахождение точки пересечения двух прямых (и отрезков)

Введение


Довольно часто при разработке игр возникает необходимость находить точку пересечения прямых, отрезков, лучей и т.д. О том, как реализовать это максимально простым способом, в этой статье.

image

Популярные способы и их критика


Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти x, и подставить его в уравнение прямой, чтобы найти y (Подробнее здесь).

Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые перпендикулярны осям, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.

В поисках более элегантного решения данной проблемы я наткнулся на весьма интересные способы, основанные на векторном умножении ( habr.com/ru/post/267037 ) и ray castinging'е ( ru.wikipedia.org/wiki/Ray_casting#Концепция ). Но на мой взгляд, они неоправданно сложные в вычислительном плане. Поэтому представляю вашему вниманию (и критике) мой способ.

Мой способ


Задача


Даны координаты двух отрезков. Нужно узнать, пересекаются ли отрезки, и если да, в какой точке. Для этой цели напишем функцию.

Решение


image

Условные обозначения для исключения недопониманий: a — вектор a, a(y) — проекция вектора a на ось Y, a{x1,y1} — вектор a, заданный координатами x1,y1.

Представим наши отрезки в виде двух векторов: a{x2-x1; y2-y1} и b{x3-x4; y3-y4}. Обратите, внимание, что вектор b имеет противоположное от ожидаемого направление. Введём вектор c{x3-x1; y3-y1}. Заметим, что a*k+b*n=c, где k,n — некоторые коэффициенты. Таким образом, получаем систему уравнений:

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

Собираем воедино


float dot[2];  // точка пересечения

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

Данная функция принимает координаты вершин и возвращает значение 1, если прямые отрезков (именно прямые) пересекаются, иначе 0. Если же вам нужны координаты вершин, вы сможете взять их из массива dot[].

Важно: при введении двух совпадающих прямых, алгоритм выводит отсутствие пересечения. Алгоритм находит точку пересечения прямых, на которых лежат отрезки, поэтому точка может оказаться за пределами отрезка (что вам придётся дополнительно проверить в уже своём коде).

Применим функцию:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

Послесловие


Хоть я и не встретил этот способ в процессе гугления своей проблемы и вывел алгоритм самостоятельно, я не претендую на его полную оригинальность (и правильность). Поэтому добро пожаловать в комментарии!
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 35

    +11
    Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые параллельны, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.

    Тем не менее, в вашем коде также приходится прописывать код на случай совпадающих и пересекающихся под прямым углом прямых. Где же преимущество?
      –1

      Все ветвления в моём способе не меняют принципиально работу алгоритма, в отличие от уравнений прямых. Они там нужны для ускорения вычислений
      Спасибо, в следующий раз буду аккуратнее в формулировках

        +1
        Спасибо, в следующий раз буду аккуратнее в формулировках
        Ничто не мешает подобрать более аккуратную формулировку и внести изменение и в эту статью
          0
          Какой результат будет на таких данных?
          x1=1, y1=2
          x2=4, y2=1
          x3=2, y3=5
          x4=8, y4=3
        +7
        Ваш способ вычислительно идентичен способу с уравнениями прямых. Там тоже получается система из двух уравнений: p1 + k*a = p4 + n*b, где p1, p2 — координаты точек.
          –6

          Но это же не уравнения прямых, по крайней мере, в том смысле, в котором я их упоминал в статье. Алгебраически они задаются как y = ax+b

            +7

            Это в школе.

              0
              В это алгебраическое определение как-то не вписываются вертикальные прямые. Так что лучше задавать прямые в виде p+kv, где p — точка на прямой, v — вектор, параллельный прямой.
                +6

                Ну нет, уравнение прямой всегда было ax + by + c = 0.

              0
              офф Может кто подскажет по стереометрии простой способ вычислить попадет ли отрезок (или прямая) в заданный цилиндр?
                0
                что значит «попадёт»? Математика вместе со своей сестрой Геометрией (а также кузиной Стереометрией) требует точных и недвусмысленных формулировок
                  0
                  Видимо имеется в виду «попадет» или «промахнётся» </шутка>
                  А если серьезно, то «расположена».
                    0
                    А если серьезно
                    нет, это не серьёзно:
                    если прямая, то расположена целиком? если отрезок, то расположен отрезок целиком в цилиндре или прямая, задаваемая отрезком, целиком расположена в цилиндре (здесь я имею в виду бесконечный цилиндр, а что имеет в виду автор вопроса, можно только гадать)
                      +1

                      А это не имеет значения. Все равно основным моментом будет нахождение точек пересечения прямой с бесконечным цилиндром и двумя плоскостями (если цилиндр не бесконечный).


                      Единственный частный случай — проверка, пересекает ли прямая бесконечный цилиндр. Тогда точки пересечения искать не надо, достаточно посчитать расстояние между прямыми и проверить их на коллинеарность.

                        0
                        Ну так ответьте автору комментария
                          0
                          Это примерно то что надо. Уточните что искать?
                      0
                      В данном случае я сказал в практическом смысле зачем мне это надо — расчет траектории летящего объекта на столкновение с объектом. Для упрощения расчетов объект — это цилиндр.
                        0
                        Только это не сняло неполноты и неоднозначности вопроса.
                        Получается, что вас интересует пересечение двух бесконечных цилиндров?
                        рассчитайте расстояние между двумя прямыми (осями цилиндров) и если сумма полугабаритов (радиусов цилиндров) обоих объектов больше этого расстояния — дело плохо (или наоборот хорошо, если столкновение — это благоприятный исход)
                          0
                          Эта публикация навела на мысли что гуглить и я нашел — Intersection of two paths given start points and bearings (Пересечение двух путей с учетом начальных точек и направлений).

                          Вопрос я сам не очень-то мог сформулировать — что-то вроде упреждения при стрельбе по цели с известными начальными координатами и направлением движения, причем зона поражения стреляющего имеет форму конуса определенных угловых размеров.
                    0
                    Задавал вопрос. Разобрался сам :)
                      0

                      Интереснее было бы рассмотреть задачу не на плоскости, а в пространстве

                        0
                        Ниже я дал книжку, в пространстве: в 7 главе.
                        +5
                        Все-таки «отрезок» это не «прямая». Как я понял, для вашего алгоритма надо предварительно выбрать подходящие отрезки, что бы пересечение гарантировано было внутри них. И весь смысл упрощений теряется.

                        Я к тому, что искать пересечение прямых (как в заголовке) это одно, а пересечение отрезков (как в статье) это другое немного.
                          +3
                          Честно говоря, всегда удивляло, почему в играх как правило используется параметрическое представление кривых, а в школе этот тип представления либо не дается, либо о нем сами учителя не знают :) Иначе очень трудно объяснить почему народ пытается решать такие задачки в функциональном стиле, ведь на самом деле все очень просто. Самому было лень писать, поэтому просто приведу код первый попавшийся в запросе гугла на псевдо С++:
                          #include <iostream>
                          #include <cmath>
                          using namespace std;
                           
                          int main() 
                          {
                              double x1, y1, x2, y2, x3, y3, x4, y4;
                              double Ua, Ub, numerator_a, numerator_b, denominator;
                              
                              cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
                          
                              denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
                          
                              if (denominator == 0) {
                                  if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)
                                      cout << "Отрезки пересекаются (совпадают)";
                                  else 
                                      cout << "Отрезки не пересекаются (параллельны)";
                              }
                              else{
                                  numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
                                  numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
                                  Ua=numerator_a/denominator;
                                  Ub=numerator_b/denominator;
                          
                                  cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");
                              }
                          
                              return 0;
                          }
                          Ua и Ub и есть параметры каждого отрезка. Если они оба лежат в пределах 0.0 < 1.0 то отрезки пересекаются. Код кажется сложным, но на самом деле это просто развертка решения системы двух линейных параметрических уравнений относительно Ua и Ub, а также можно заметить что многие суммы совпадают и на практике их можно вычислить один раз. Подставив Ua или Ub обратно в любое из уравнений можно вычислить саму точку пересечения, например в векторном виде:
                          Pc = P(x1, y1) + P(x2, y2) * Ua;
                          Pc = P(x3, y3) + P(x4, y4) * Ub;
                          +1
                          Если представить точки в виде (x,y,1) то их (двух точек) cross product даст уравнение прямой. L= P0xP1. Соответственно cross product двух линий — точка. И никаких сложных вычислений — простая алгебра. Что интересно, что нормализацию (деление ) на третий компонент, можно производить только в конце цепочки вычислений, а так линии и точки обрабатываются единообразно и без исключений особых случаев.
                          Причем можно метод расширить до плоскостей и точек в трехмерном пространстве, только плоскость будет образовываться тремя точками, а точка тремя плоскостями
                            +2
                            Да, когда-то все эти вопросы разбирались в замечательной книжке: image, читайте 3 главу
                            И, по моему, в каких-то эхоконференциях регулярно ходил Faq на эту тему, возможно Ru.Graphics, но я нашёл только demo design 3d faq там нет пересечения линий, а чисто 3D
                              0
                              Однако данный способ [...] не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай

                              В курсе аналитической геометрии, помню, было полдесятка различных уравнений прямых на плоскости, нужно выбрать более подходящий для задачи вид уравнения и проблема углового коэффициента уйдёт.


                              Я когда-то задавал эту задачку студентам-первокурсникам на лабах по C++. Ожидал увидеть какое-то такое решение:


                              — составить два общих уравнения прямой (в форме Аx + Bx + С = 0);
                              — подстановкой точек в левые части уравнений убедиться, что концы отрезков лежат по разные стороны от этих прямых;
                              — решить систему методом Крамера.


                              Ситуацию, когда на третьем этапе матрица всё равно оказывалась вырожденной, несмотря на сделанные проверки, можно было не рассматривать. К сожалению, и без этого задача оказалось слишком сложной для студентов.

                                –2
                                Метод Крамера, как и Гаусса, не являются универсальными. При некоторых значениях системы ряд расходится, если одни коэффициенты близки к другим. Более универсальное решение приводит Гейл Лакман Мак-Дуэлл в своей книге 'Карьера программиста'. У неё, правда, задача формулируется иначе, но данная проблема — частный случай того, что приводит она. Математически же более универсальное решение это квадратичные отклонения, числодробилка. Однажды застрял на похожей проблеме. 'Провисел' 2 недели, вызвали спеца, математика-практика. Решение заняло несколько строчек. К сожалению, подробности не вспомню, было очень давно.
                                  0

                                  Верно, проблема с устойчивостью — это огромная проблема при решении СЛАУ. А минимизация квадратичного отклонения — один из способов регуляризации.


                                  Вот только в данном случае это совершенно не актуально. Предыдущий комментарий был о том, что тупые студенты были даже не в состоянии составить систему. Вы же пишете о том, что систему надо решать правильно. Но в данном случае это оверинжиниринг. Метода Крамера или Гаусса для решения системы из 2 уравнений более, чем достаточно.

                                    –1
                                    Однако данный способ [...] не является универсальным:
                                    Ответ был на пост об универсальности метода. Надеюсь, минусующему ясно.
                                    +1

                                    Какой там нафиг ряд может расходиться, когда оба метода используют лишь 4 базовые арифметические операции?


                                    Вот что правда может "разойтись" — так это потеря точности на вычитании близких чисел, усугубляемая последующим делением на это число. Но это лишь означает, что искать точку пересечения почти-параллельных прямых — плохая идея.

                                      –1
                                      Для двух отрезков да. А если больше? В моём случае была система из 6 или 7 линейных уравнений. Точнее не помню. И расходилось.
                                        +2

                                        Вот когда будет поставлена задача искать точку пересечения N гиперплоскостей в M-мерном пространстве, тогда и будем придумывать решение. А вот придумывать вундервафлю для решения простейшей задачи не стоит совершенно.

                                          –1
                                          Разговор шёл о границах применимости, или
                                          способ [...] не является универсальным
                                          В моём случае
                                          вундервафля
                                          состояла в поиске проекции растра на векторное поле.
                                  0

                                  del

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое