Точка пересечения двух лучей

Все исходники / Язык программирования C# / OS Windows / Математика / Аналитическая геометрия / Точка пересечения двух лучей
Оглавление:
  1. Вычисление точки пересечения лучей в программном коде
  2. Варианты пересечения двух лучей
  3. Лучи пересекаются в одной точке
  4. Лучи не имеют общих точек
  5. Вычисление точки пересечения в программный код
  6. Исходник приложения нахождения точки пересечения лучей на плоскости

Вычисление точки пересечения лучей в программном коде

К статье приложена программа демонстрации вычисления точки пересечения двух лучей. Мышью и служебными клавишами можно управлять началом и направлением, создавая различные комбинации положений лучей. В исходнике содержится класс Intersections имеющий метод вычисления точки пересечения лучей на плоскости RayRay(Point r1, Point r2, Point p1, Point p2, out Point pCross, out Info info).

Варианты пересечения двух лучей

Разные случаи пересечения двух лучей

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

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

Частные случаи пересечения двух лучей. Лучи могут иметь бесконечное количество общих точек, в таком случае говорят о полном или частичном совпадении друг с другом. Лучи имеют точки начала с равными координатами.

Лучи пересекаются в одной точке

Точка пересечения двух лучей на плоскости

Частный случай совпадения начальных точек двух лучей позволяет получить значения общих координат "сразу", при построении лучей и без вычисления.

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

Параметрические уравнения
x = x0 + vt
y = y0 + wt
где v и w координаты вектора направления луча: 
v = x1 - x0
w = y1 - y0
t - параметр определяющий расположение точек луча

точки лежат на луче при t >= 0, 
при t = 0 уравнения выведут координаты начала луча
при t < 0, точки принадлежат мнимому продолжению луча в противоположную сторону

Создадим систему уравнений для двух лучей. 4 уравнения, 4 неизвестных - система решаема.

| x = Ax + (Bx - Ax)tab
| y = Ay + (By - Ay)tab 
| x = Cx + (Dx - Cx)tcd
| y = Cy + (Dy - Cy)tcd

Если точка пересечения существует, то tab >= 0 и tcd >= 0
Для доказательства факта пересечения необходимо 
вычисление обоих параметров:  tab и  tcd.

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

| x = 1 + (10 - 1)tab    | x = 1 + 9tab
| y = 2 + (3 - 2)tab  => | y = 2 + tab
| x = 2 + (11 - 2)tcd    | x = 2 + 9tcd
| y = 3 + (2 - 3)tcd     | y = 3 - tcd

Вычислим соотношения параметров:

вычисление через неизвестную x
1 + 9tab = 2 + 9tcd => 9tab = 1 + 9tcd =>
tab = tcd + 1/9

Теперь возможно вычисление значения одного параметра для подтверждения пересечения или непересечения лучей:

используем другие уравнения - вычисление через неизвестную y
2 + tab = 3 - tcd => tab = 1 - tcd =>
tcd + 1/9 = 1 - tcd => tcd = (1 - 1/9) / 2 => tcd ≈ 0.4444
tab =0.4444 + 1/9 ≈ 0.5555

tcd > 0 и tab > 0 - лучи пересекаются

Находим координаты точки пересечения используя вычисленный параметр:

x = 2 + 9tcd => x = 2 + 9 * 0.4444 => x = 5.9996
y = 3 - tcd => y = 3 - 0.4444 => y = 2.5556

Лучи не имеют общих точек

Два луча не пересекаются

На рисунке показаны два варианта расположения лучей при которых они не пересекаются.

На одном из них мнимая точка пересечения находится за пределами обоих лучей. Другой вариант располагает мнимую точку пересечения на одном из лучей.

Для доказательства непересечения лучей также используем параметрические уравнения описанные выше. Если хотя бы один параметр имеет отрицательное значение - значит лучи не имеют общих точек.

x = x0 + vt
y = y0 + wt

Докажем для первого случая, что лучи не пересекаются. Напишем систему уравнений для двух лучей:

| x = Ax + (Bx - Ax)tab
| y = Ay + (By - Ay)tab 
| x = Cx + (Dx - Cx)tcd
| y = Cy + (Dy - Cy)tcd

если лучи не пересекаются, то 
при tab < 0 и tcd < 0 мнимая точка пересечения не лежит ни на одном луче,
при tab < 0 или tcd < 0 мнимая точка пересечения принадлежит одному из лучей,
у которого параметр t > 0.
При получении первого t < 0 вычисление второго имеет только статистический смысл,
так как отрицательный первый параметр уже доказывает что лучи не имеют общих точек.

Подставим значения известных координат точек лучей:

| x = 6 + (3 - 6)tab    | x = 6 - 3tab (у.1)
| y = 7 + (6 - 7)tab => | y = 7 - tab (у.2)
| x = 8 + (12 - 8)tcd   | x = 8 + 4tcd (у.3)
| y = 7 + (6 - 7)tcd    | y = 7 - tcd (у.4)

Через переменную x найдем соотношение параметра первого луча к параметру второго луча:

6 - 3tab = 8 + 4tcd => -3tab = 2 + 4tcd =>
tab = (-2 - 4tcd) / 3, 

Теперь мы можем получить значения параметров лучей:

искать будем через переменную y
7 - tab = 7 - tcd => 
tab = tcd => (у.5)
(-2 - 4tcd) / 3 = tcd => tcd = -2/7

из уравнения (у.5) получаем значение второго параметра
tab = tcd (т.1) => tab = -2/7

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

x = 6 - 3tab (у.1) => x = 6 - 3(-2/7) = 6 + 6/7 = 48/7 => x = 6,857
y = 7 - tab (у.2) => y = 7 - (-2/7) = 51/7 => y = 7,2857

Произведём вычисления для второго случая расположения лучей на плоскости:

| x = 2 + (9 - 2)tab    | x = 2  + 7tab
| y = 2 + (1 - 2)tab => | y = 2 - tab
| x = 6 + (13 - 6)tcd   | x = 6  + 7tcd
| y = 2 + (4 - 2)tcd    | y = 2  + 2tcd

Вычислим соотношение параметров лучей:

 2  + 7tab = 6  + 7tcd => tab = 4/7 + tcd

Получим значения параметров лучей:

2 - tab = 2  + 2tcd =>  - tab = 2tcd => -4/7 - tcd = 2tcd => -4/7 = 3tcd =>
tcd ≈ -0,1905
tab = 4/7 + tcd => tab = 0.5714 - 0,1905 =>
tab = 0.3809
один из параметров отрицательный - лучи не пересекаются,
другой параметр положительный - мнимая точка пересечения лежит 
на луче AB

Вычисление точки пересечения в программный код

На основе теоретических расчётов описанных выше создан класс Intersections с методом RayRay() вычисляющим точку пересечения двух лучей. Метод выдаёт информационные сообщения о непересечении и частных случаях расположения лучей: параллельность, совпадение, неопределенность. Практическая демонстрация работы класса прикреплена к статье в виде исходника приложения с графикой из двух лучей на плоскости.

Расположение лучей устанавливаются действиями кнопки мыши при нажатых специальных клавишах. Начальные точки - левые клавиши, вторые точки - правые клавиши. Положение лучей также можно настраивать путём ввода координат в соответствующие элементы редактирования.

class Intersections
{
    // Получение точки пересечения двух лучей.
    public static bool RayRay(Point r1, Point r2, Point p1, Point p2, out Point pCross, out Info info)
    {
        // Оповещение о событиях пересечения или не пересечения.
        info = new Info();

        // ----- Данные лучей -----
       
        // Координаты направления вектора синего луча.
        double v = r2.X - r1.X;
        double w = r2.Y - r1.Y;

        // Координаты направления вектора красного луча.
        double v2 = p2.X - p1.X;
        double w2 = p2.Y - p1.Y;
        
        // ----- /Данные лучей -----


        // ----- Частные случаи не пересечения -----

        // Лучи должны быть определены,
        // совпадают начальные и конечные точки.
        // В данном случае выдаются только сообщения.
        if (v == 0 && w == 0 && v2 == 0 && w2 == 0)
        {
            info.Id = 10;
            info.Message = "Лучи неопределённы";

            return false;
        }
        else if (v == 0 && w == 0)
        {
            info.Id = 11;
            info.Message = "Синий луч неопределён";

            return false;
        }
        else if (v2 == 0 && w2 == 0)
        {
            info.Id = 12;
            info.Message = "Красный луч неопределён";

            return false;
        }

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

        // Вычисляем длины векторов
        double lenBlue = Math.Sqrt(v * v + w * w);
        double lenRed = Math.Sqrt(v2 * v2 + w2 * w2);

        // Нормализация векторов - создание единичного вектора направления.
        // Единичные векторы дают возможность сравнить направление лучей
        // без учёта расположения их определяющих точек. 
        double x = v / lenBlue;
        double y = w / lenBlue;
        double x2 = v2 / lenRed;
        double y2 = w2 / lenRed;

        // Точность совпадения величин double.
        // Точность не может быть абсолютной,
        // можно только увеличить точность или уменьшить.
        double epsilon = 0.000001;

        // Проверка на совпадение с определенной точностью.
        // Совпадение - это одинаковые начальные точки и направления лучей.
        if (r1.X == p1.X && r1.Y == p1.Y && Math.Abs(x - x2) < epsilon && Math.Abs(y - y2) < epsilon)
        {
            info.Id = 20;
            info.Message = "Лучи совпадают";

            return false;
        }

        // Проверка на параллельность с определенной точностью.
        // Параллельность - совпадение только направления лучей.
        if (Math.Abs(x - x2) < epsilon && Math.Abs(y - y2) < epsilon)
        {
            info.Id = 21;
            info.Message = "Лучи параллельны";
            return false;
        }

        // ----- /Частные случаи не пересечения -----


        // ----- Вычисление точки пересечения -----

        // Проверка факта пересечения
        // x = p1.X + v2t2
        // y = p1.Y + w2t2

        // r1.X + vt = p1.X + v2t2 => vt = p1.X - r1.X + v2t2 =>
        // t = (p1.X - r1.X + v2t2) / v - (у.1) соотношение t-параметров
        //
        // Подробнейшее вычисление одного параметра с заменой соотношением другого
        // r1.Y + wt = p1.Y + w2t2 => wt = p1.Y - r1.Y + w2t2 => t = (p1.Y - r1.Y + w2t2) / w
        // (p1.X - r1.X + v2t2) / v = (p1.Y - r1.Y + w2t2) / w =>
        // (p1.X - r1.X + v2t2) * w = (p1.Y - r1.Y + w2t2) * v =>
        // w * p1.X - w * r1.X + w * v2t2 = v * p1.Y - v * r1.Y + v * w2t2 =>
        // w * v2t2 - v * w2t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y =>
        // (w * v2 - v * w2) * t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y =>
        // Получение значения одного параметра путём подстановки
        // вычисленного соотношения (у.1)***
        // t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2)  - (у.2)
        double t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2);

        // t = (p1.X - r1.X + v2t2) / v - (у.1)
        double t = (p1.X - r1.X + v2 * t2) / v;

        // Если один из параметров меньше 0, значит пересечения нет.
        if (t < 0 || t2 < 0)
        {
            info.Id = 20;
            info.Message = "Пересечения нет";


            return false;
        }

        // Координаты точки пересечения
        pCross.X = p1.X + v2 * t2;
        pCross.Y = p1.Y + w2 * t2;


        info.Id = 0;
        info.Message = "Пересечение есть";

        return true;

        // ----- /Вычисление точки пересечения -----
    }
}

public class Info
{
    // Для визуального сообщения.
    public string Message;

    // Для автоматических действий.
    public int Id;
}

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

Тема: «Точка пересечения двух лучей» Язык программирования C# WpfAppCrossRayRay-vs17.zip Размер:95 КбайтЗагрузки:168