Как найти общие точки двух прямых

Оглавление

1. Пересечение прямых
2. Прямые пересекаются
3. Точка пересечения прямых
4. Прямые параллельны
5. Уравнение в программный код
6. Вывод результата
7. Проверка параллельности и совпадения
8. Проверка на перпендикулярность
9. Класс Intersections
10. Применение класса Intersections
11. Прикрепленный файл

Пересечение прямых

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

Прямые это бесконечные линии, поэтому на плоскости они всегда пересекаются. Если прямые не пересекаются значит они параллельны. Частные случаи поведения прямых на плоскости: прямые неопределенны, прямые параллельны, прямые совпадают, одна из прямых параллельна оси X или Y. Общие случаи “нормального” пересечения прямых и частные случаи учитываются в программном коде класса Intersections прикрепленного исходника.

Прямые пересекаются

Даны две прямые AB и CD расположенные на одной плоскости. Они пересекаются и необходимо найти точку пересечения. За основу берем классическое уравнение прямой и подставляя данные получаем систему уравнений для двух прямых.

Точку пересечения можно найти, решая совместно уравнения прямых. Два уравнения – две неизвестных величины. Если количество уравнений больше или равно количеству неизвестных, то система решаема. Точка пересечения двух прямых это такая точка, которая принадлежит обеим прямым.

Классическое уравнение прямой:

 x - x1        y - y1
--------  =  ---------    (у.1)
 x2 - x1       y2 - y1

Запишем уравнение в одну строчку:

x(y2 - y1) + y(x1 - x2) - x1y2 + y1x2 = 0 (у.2)

Вычислим коэффициенты и свободные члены:

a = (y2 - y1)
b = (x1 - x2)
c = (-x1y2 + y1x2)

В итоге получаем уравнение прямой с коэффициентами:

ax + by + c = 0 (у.3)

Уравнение с линейными коэффициентами отличается от уравнения с угловым коэффициентом отсутствием операции деления. Минимум операций деления упрощает создание устойчивого программного кода.

Точка пересечения прямых

Координаты точки пересечения это числа которые являются решением для каждого из уравнений прямых. Решая систему из двух уравнений находим в какой точке пересекаются прямые AB и CD.

Подставляем известные данные:

AB  x(5 - 2) + y(2 - 11) - 2*5 + 2*11 = 0
CD  x(2 - 7) + y(2 - 12) - 2*2 + 7*12 = 0

Получаем два уравнения:

AB  x - 3y + 4 = 0        
CD  x + 2y - 16 = 0

Решаем систему уравнений:

|                     
| x = 3y - 4  =>  x = 3(-0.5x + 8) - 4
| y = -0.5x + 8 =>  y = -0.5(3y - 4) + 8          
|

Найдено, прямые пересекаются в точке с координатами:

x = 8
y = 4

Прямые параллельны

Если прямые параллельны и лежат друг от друга на расстоянии, то у них нет общих точек. Совместная система уравнений не имеет решений. Эти уравнения существуют как бы сами по себе. В точности как их параллельные прямые.

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

Применяя формулу у.2 выведем уравнения прямых:

AB  x(7 - 3) + y(2 - 6) - 2*7 + 3*6 = 0
CD  x(4 - 1) + y(8 - 11) - 8*4 + 1*11 = 0

Получаем систему уравнений:

|                                    
|  x - y - 25 = 0  =>    x - y = 25
|  x - y - 7 = 0   =>    x - y  = 7
|                                   

25 ≠ 7

Итог: система уравнений параллельных прямых не имеет решений.

Уравнение в программный код

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

Преобразуем в программный код уравнение с коэффициентами (у.3) описанное выше. Для каждой прямой своё уравнение и переменные.

AB a1x + b1y + c1 = 0
CD a2x + b2y + c2 = 0

Точки определяющие прямые запишем в структуры Point. У каждой прямой две точки и они являются входными данными:

Point pABDot1;
Point pABDot2;

Point pCDDot1;
Point pCDDot2;

Определяем коэффициенты и свободные члены уравнений. Записываем их в соответствующие переменные:

double a1 = pABDot2.Y - pABDot1.Y;
double b1 = pABDot1.X - pABDot2.X;
double c1 = -pABDot1.X * pABDot2.Y + pABDot1.Y * pABDot2.X;

double a2 = pCDDot2.Y - pCDDot1.Y;
double b2 = pCDDot1.X - pCDDot2.X;
double c2 = -pCDDot1.X * pCDDot2.Y + pCDDot1.Y * pCDDot2.X;

Точка пересечения также будет храниться в структуре Point:

Point pCross;

Вывод результата

Упростим уравнение (у.3) для получения значений искомых координат. Чтобы освежить память сделаем это максимально подробно. Из одного уравнения выведем X, из другого Y:

a1x = -b1y - c1 => x = (-b1y - c1) / a1 =>
b2y = -a2x - c2 => y = (-a2x - c2) / b2 =>

x = ( -b1( (-a2x - c2) / b2) - c1 ) / a1 =>
y = ( -a2( (-b1y - c1) / a1) - c2) / b2 =>

x = ( (b1a2x + b1c2) / b2 - c1 ) / a1 =>
y = ( (a2b1y + a2c1) / a1 - c2) / b2  =>

x = ( (b1a2x + b1c2 - b2c1) / b2 ) / a1 =>
y = ( (a2b1y + a2c1 - a1c2)  / a1) / b2 =>

x = ( b1a2x + b1c2 - b2c1)  /  b2 a1 =>
y = ( a2b1y + a2c1 - a1c2)  / a1 b2 =>

xb2a1 - b1a2x = b1c2 - b2c1 =>
ya1b2 - a2b1y = a2c1 - a1c2  =>

x = (b1c2 - b2c1) / (b2a1 - b1a2)
y = (a1c1 - a1c2) / (a1b2 - a1b1)

После упрощения и прихорашивания уравнений записываем искомые координаты X Y в объект pCross:

Point pCross;

pCross.X = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
pCross.Y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);

В выражениях присутствует деление. Но знаменатель только тогда и только тогда будет равен нулю, когда обе прямые будут параллельны или оси X или оси Y. В этом случае они не пересекаются или совпадают. Это отслеживаемые состояния в классе Intersections, и вывод информации заканчивается до выбрасывания исключения при делении на ноль.

Проверка параллельности и совпадения

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

a1 / a2 = b1 / b2

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

if ((a1 * b2 - a2 * b1) == 0)
{
    // Прямые параллельны другу друг и не имеют точек пересечения
    ...
}

Если пропорциональны не только коэффициенты, но и свободные члены, то исследуемые прямые совпадают. У таких прямых идентичные уравнения. Прямые совпадают если:

a1 / a2 = b1 / b2 = c1 / c2

Данную ситуацию дополнительно отслеживаем в программном коде, исключая операцию деления:

if ((a1 * b2 - a2 * b1) == 0)
{
    // Прямые параллельны другу друг и не имеют точек пересечения
    ...

    if (a1 * b2 == b1 * a2 && a1 * c2 == a2 * c1 && b1 * c2 == c1 * b2)
    {
        // Прямые совпадают и имеют бесконечное количество решений
        ...
    }
}

Проверка на перпендикулярность

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

a1a2 = -b1b2 или a1a2 + b1b2 = 0

В программном коде отследим эту ситуацию выражением:

if ((a1 * a2 + b1 * b2) == 0)
{
    // Прямые перпендикулярны
    ...
}

Класс Intersections

Исходник представляет собой два класса: класс вычисления точки пересечения прямых и информационный класс выдающий множество дополнительных сведений о свойствах исследуемых прямых.

Краткий листинг исходника дающий представление о структуре классов:

// Вычисление точки пересечения прямых
class Intersections
{
    // Метод вычисления точки пересечения.
    private Point Cross(double a1, double b1, double c1, double a2, double b2, double c2)
    {
        Point pCross;
        pCross.X = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
        pCross.Y = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);

        return pCross;
    }


    // Метод дающий полную информацию об исследуемых прямых и их пересечениях
    public bool LineLine(Point pABDot1, Point pABDot2, 
         Point pCDDot1, Point pCDDot2, out Point pCross, out Info info)
    {
        // 
        info = new Info();

        double a1 = pABDot2.Y - pABDot1.Y;
        double b1 = pABDot1.X - pABDot2.X;
        double c1 = -pABDot1.X * pABDot2.Y + pABDot1.Y * pABDot2.X;

        double a2 = pCDDot2.Y - pCDDot1.Y;
        double b2 = pCDDot1.X - pCDDot2.X;
        double c2 = -pCDDot1.X * pCDDot2.Y + pCDDot1.Y * pCDDot2.X;

        ...

        // Прямые параллельны
        if ((a1 * b2 - a2 * b1) == 0)
        {
            info.Id = 40;
            info.Message = "Прямые параллельны";

                ...

            if (a1 * b2 == b1 * a2 && a1 * c2 == a2 * c1 && b1 * c2 == c1 * b2)
            {
                    info.Id = 43;
                    info.Message = "Прямые совпадают";
            }

            return false;
        }

        //  --------------  Прямые пересекаются ----------------------

        // Точка пересечения прямых
        pCross = Cross(a1, b1, c1, a2, b2, c2);

        // Прямые перпендикулярны
        if ((a1 * a2 + b1 * b2) == 0)
        {
            info.Id = 50;
            info.Message = "Прямые перпендикулярны";

            return true;
        }

            ...

        return true;

    } // public bool LineLine(Point pABDot1...
}// class Intersections

// Идентификатор результата пересечения прямых
// и пояснительное сообщение
public class Info
{
     public string Message;
     public int Id;
}

Применение класса Intersections

Класс class Intersections легко встраивается в любой исходный код. Точки определяющие прямые являются входными данными. На выходе получаем результат пересечения, координаты точки пересечения. Для дальнейшей обработки результатов можно использовать идентификатор свойства пересечения и дополнительную текстовую информацию.

// Определяющие точки первой прямой
Point pABDot1 = new Point(X1, Y1);
Point pABDot2 = new Point(X2, Y2);

// Определяющие точки второй прямой
Point pCDDot1 = new Point(X1, Y1);
Point pCDDot2 = new Point(X2, Y2);

// Вычисляем точку пересечения прямых
Intersections intersections = new Intersections();

Point pCross;
Info info;
bool res = intersections.LineLine(pABDot1, pABDot2, 
                      pCDDot1, pCDDot2, out pCross, out info);

// Вывод информации о свойстве пересечения или непересечения
crossInfo.Content = info.Message;

if (res == true)
{
    // Прямые пересекаются,
    // получены координаты точки пересечения.
    // Объект перемещается в точку пересечения.

    Obj.MoveTo(pCross.X, pCross.Y);
    ...
}
else
{
    // Пересечения прямых нет  
    ...
}

Прикрепленный файл

Прикрепленный файл архива содержит исходник классов Intersections, Info и программу демонстрирующую работу класса Intersections в режиме вычисления точки пересечения прямых на плоскости. Исходный код написан на языке C#, но его легко можно преобразовать в код на другом языке программирования. Для работы демонстрационной программы необходима установка платформы .NET Core 3.1.

Скачать исходник

• IntersectionsLineLine.zip
• Размер: 84 Кбайт
• Загрузки: 825