Оглавление
Пересечение луча и прямой
Пересечения луча и прямой на плоскости могут иметь общие и частные варианты: луч и прямая пересекаются, луч и прямая параллельны и не пересекаются, луч и прямая параллельны и совпадают, луч и прямая расположены под углом друг к другу и не пересекаются. Выведем уравнения и вычисления теоретически и затем воплотим их в практический программный код на 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 нам не удалось избавится от деления. В случае если знаменатель будет равен нулю, то результат будет бесконечность. В каких случаях знаменатель может быть равен нулю?
- Направление луча неопределенно:
тогда v = 0 и w = 0
- Направление прямой неопределенно:
тогда a = 0 и b = 0
- Когда луч и прямая параллельны друг другу, а их векторы коллинеарны. В нашем случае когда соблюдается условие:
-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.
Скачать исходник
IntersectionsRayLine.zip
- Размер: 83 Кбайт
- Загрузки: 347