Пересечение луча и прямой на плоскости

Все исходники / Язык программирования C# / OS Windows / Математика / Аналитическая геометрия / Пересечение луча и прямой на плоскости

Оглавление

  1. Пересечение луча и прямой
  2. Определение наличия пересечения
  3. Точка пересечения луча и прямой
  4. Луч и прямая не пересекаются
  5. Уравнение в программный код
  6. Деление на ноль
  7. Параллельность луча и прямой
  8. Совпадение луча и прямой
  9. Программный код
  10. Демонстрационная программа

Пересечение луча и прямой

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

Определение наличия пересечения

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

Возьмем параметрические уравнения для луча и с коэффициентами для прямой. Параметрическое уравнение луча отличается важным параметром t идентифицирующий направление луча. Только при t >=0 уравнение определяет множество точек луча. Если же к лучу добавить точки при t < 0 тогда луч превратится в прямую и это будет параметрическое уравнение прямой

Параметрические уравнения луча: 
x = x0 + vt
y = y0 + wt
где v и w координаты вектора направления луча, 
t >= 0
Система уравнений, 3 уравнения и 3 неизвестных: система решаема. 
| x = x0 + vt
| y = y0 + wt          (у.1)
Уравнение прямой
| ax + by + c = 0
Выведем подробно определение t из системы уравнений: 
a(x0 + vt) + b(y0 + wt) + c = 0    =>
ax0 + avt + by0 + bwt + c = 0    =>
t(av + bw) + ax0 + by0 + c = 0   =>
t(av + bw) = -ax0 - by0 - c          =>
t = (-ax0 - by0 - c) / (av + bw)       (у.2)
При t >= 0 луч и прямая пересекаются, если t < 0 луч и прямая не имеют общих точек.

Точка пересечения луча и прямой

Точка пересечения луча и прямой на плоскостиТеперь определим на примере точку пересечения луча и прямой. Сформируем необходимые данные для системы уравнений (у.1) и сначала определим факт пересечения уравнение (у.2), затем получим координаты точки С.

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

x0 = P1.x, y0 = P1.y
v = P2.x - P1.x = 11 - 1 = 10
w = P2.y - P1.y = 4 - 6 = -2

a = M2.y - M1.y = 8 - 2 = 6
b = M1.x - M2.x = 3 - 9 = -6
c = -M1.x * M2.y + M1.y * M2.x  = -6
Используем выражение (у.2) для параметра t и подставив данные получим значение: 
t = (-ax0 - by0 - c) / (av + bw) = 0.5
t > 0, луч и прямая имеют общую точку
Искомые координаты: 
x = 1 + 10 * 0.5 = 6
y = 6 + (-2) * 0.5 = 5

Луч и прямая не пересекаются

Луч и прямая не пересекаютсяТеперь луч и прямая не пересекаются. Но необходимо подтвердить этот факт математически, чтобы в программном коде получить значение типа Boolean. Снова обращаемся к уравнениям (у.1) и (у.2).

Необходимо заметить, что если даже t < 0, существует ложная точка пересечения находящаяся в противоположном направлении луча. На рисунке она обозначена серым цветом. Иногда в программах необходимы такие данные.

 

Итак, известные данные: 
x0 = P1.x, y0 = P1.y
v = P2.x - P1.x = 11 - 4 = 7
w = P2.y - P1.y = 6 - 5 = 1

a = M2.y - M1.y = 3 - 5 = -2
b = M1.x - M2.x = 1 - 10 = -9
c = -M1.x * M2.y + M1.y * M2.x = 47
Теперь убедимся что прямая и луч не пересекаются: 
t = (-ax0 - by0 - c) / (av + bw) = -0,24
t < 0, луч и прямая не имеют общую точку
Получаем координаты ложной точки пересечения, которая находится в противоположном направлении луча. 
x = 4 + 7 * (-0,24) = 2.32
y = 5 + 1 * (-0,24) = 4,76

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

Из теоретических утверждений создадим практический программный код, вычисляющий точку пересечения луча и прямой. Необходимо также в коде создать защиту от возможных исключений. Код будем строить, опять же, используя систему уравнений (у.1) выведенную выше.

Начинаем с определения переменных для входных и выходных данных. Рекомендуется использовать тип Double для повышенной точности расчетов. Кроме вычисления точки пересечения необходимо предусмотреть мягкий обход деления на ноль. 

// Определяющие точки луча
Point P1;
Point P2;

// Определяющие точки прямой
Point M1;
Point M2;

// Определим переменные для упрощения решения уравнений
double v = P2.X - P1.X;
double w = P2.Y - P1.Y;

double a = M2.Y - M1.Y;
double b = M1.X - M2.X;
double c = -M1.X  * M2.Y + M1.Y * M2.X;
Теперь выражение для получения параметра t. Если t >= 0 точка луч и прямая пересекаются. Если t < 0 луч и прямая не пересекаются, не имеют общей точки. Определим параметр t из уравнения (у.2): 
double t = (-a * P1.X - b * P1.Y - c) / (a * v + b * w);

Деление на ноль

Как видно из выражения вывода параметра t нам не удалось избавится от деления. В случае если знаменатель будет равен нулю, то результат будет бесконечность. В каких случаях знаменатель может быть равен нулю?

  1. Направление луча неопределенно: 
    тогда v = 0 и w = 0
  2. Направление прямой неопределенно: 
     тогда a = 0 и b = 0
  3. Когда луч и прямая параллельны друг другу, а их векторы коллинеарны. В нашем случае когда соблюдается условие: 
     -b       a
----  = ---- => av + bw = 0 (наш знаменатель)
  v       w

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

Параллельность луча и прямой

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

Проверка на параллельность: 
вектор прямой
a = M2.Y - M1.Y
b = M1.X - M2.X => -b = M2.X - M1.X

вектор луча
v = P2.X - P1.X
w = P2.Y - P1.Y
Если направление векторов совпадает, то должно выполняться условие: 
 vector1.X      vector1.Y
----------- = -------------
 vector2.X      vector2.Y

в нашем случае
 -b      a
 --- = ---- 
  v      w
Без операции деления: 
-bw = av =>  av + bw = 0

Совпадение луча и прямой

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

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

если a * P1.X + b * P1.Y + c = 0
 и   a * P2.X + b * P2.Y + c = 0

Координаты луча являются решениями для уравнения прямой, значит две точки луча принадлежат прямой. Отсюда вывод: луч и прямая совпадают.

Программный код

Теперь непосредственно исходный код, созданный на основе теоретических раскладок, описанных выше. В коде учтена защита вычислений от деления на ноль. имеется разбор параллельности и совпадения луча и прямой. Предусмотрен вывод дополнительной информации в виде идентификатора и текстового сообщения. Исходник представляет собой класс class Intersections имеющий метод вычисления public bool RayLine(...) . В комплект входит программа, демонстрирующая работу класса вычисления точки пересечения луча и прямой.

Листинг исходника 
class Intersections
{
    public bool RayLine(Point p1, Point p2, Point m1, 
                  Point m2, out Point pCross, out Info info)
    {
        info = new Info();

        //Данные прямой
        double a = m2.Y - m1.Y;
        double b = m1.X - m2.X;
        double c = -m1.X * m2.Y + m1.Y * m2.X;

        // Данные луча
        double v = p2.X - p1.X;
        double w = p2.Y - p1.Y;


        // **** Явное непересечение до вычисления параметра t ****

        //Луч и прямая должны быть определены
        if (v == 0 && w == 0 && a == 0 && b == 0)
        {
            info.Id = 10;
            info.Message = "Луч и прямая не определённы";
            return false;
        }
        else if (v == 0 && w == 0)
        {
             info.Id = 11;
             info.Message = "Луч не определён";
             return false;
        }
        else if (a == 0 && b == 0)
        {
                info.Id = 12;
                info.Message = "Прямая не определённа";
                return false;
        }


        //Подставим координаты луча в уравнение прямой.
        //Если уравнение верно, то две точки луча лежат на прямой.

        double result1 = a * p1.X + b * p1.Y + c;
        double result2 = a * p2.X + b * p2.Y + c;

        if (result1 == 0 && result2 == 0)
        {
            info.Id = 20;
            info.Message = "Прямая и луч совпадают";
            return false;
        }


        //Для вычисления параллельности луча и прямой 
        //необходимо сравнить их векторы.
        //Если направление их совпадает, 
        //то значит луч и прямая параллельны
        if ((a * v + b * w) == 0)
        {
            info.Id = 21;
            info.Message = "Луч и прямая параллельны";
            return false;
        }


        // **** Вычисляем точку пересечения ****

        // Проверка факта пересечения
        double t = (-a * p1.X - b * p1.Y - c) / (a * v + b * w);

        if (t < 0)
        {
            info.Id = 20;
            info.Message = "Пересечения нет";
            return false;
        }

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

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

         return true;
    }
}

public class Info
{
    public string Message;
    public int Id;
}

Демонстрационная программа

В комплект исходника входит программа визуальной демонстрации работы метода вычисления точки пересечения луча и прямой. Для работы демонстрационной программы необходима установка платформы. .NET Core 3.1.