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

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

Введение

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

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

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

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

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

Мой способ

Задача

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

Решение

Условные обозначения для исключения недопониманий: 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;
}

Послесловие

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

If you only need to know whether the rays intersect, you don’t have to find the point of intersection. The following may be more stable and efficient than solving the equations for the point of intersection, as it only involves subtraction and dot products, no division.

You have your first ray starting at $p_0$ and going in the direction of $p_1$ (and infinitely beyond $p_1$), and your second ray starting at $q_0$ and going in the direction of $q_1$ (and infinitely beyond $q_1$). Think about it visually. For a fixed $p_0$, $p_1$, and $q_0$, which values of $q_1$ result in an intersection? The answer is that $q_1$ must lie in a wedge-shaped region of the plane. One side of the wedge is the line between $q_0$ and $p_0$, and the other side of the wedge is parallel to the first ray. In the diagram, $q_1$ must be in the blue region for the rays to intersect.

We can express one side of the wedge by saying that $q_1$ must be on the same side of the $q_0$ to $p_0$ line as $p_1$ is. If $p_0 — q_0 = (l_x, l_y)$, then we can rotate $(l_x, l_y)$ 90 degrees to get a vector perpendicular to the line: $(-l_y, l_x)$. Then to check that $q_1$ and $p_1$ are on the same side, we check that $(q_1 — q_0) cdot (-l_y, l_x)$ has the same sign as $(p_1 — q_0) cdot (-l_y, l_x)$.

We can express the other side of the wedge by looking at the line passing through $q_0$ and $q_0 + (p_1 — p_0)$. $q_1$ and $p_1$ must be on the same side of this line. A vector parallel to the line is $p_1 — p_0 = (m_x, m_y)$ which we rotate 90 degrees to get $(-m_y, m_x)$. To check that $q_1$ and $p_1$ are on the same side of this line, we check that $(p_1 — q_0) cdot (-m_y, m_x)$ has the same sign as $(q_1 — q_0) cdot (-m_y, m_x)$.

So to sum up: the two rays intersect if and only if $(q_1 — q_0) cdot (-l_y, l_x)$ has the same sign as $(p_1 — q_0) cdot (-l_y, l_x)$, and $(p_1 — q_0) cdot (-m_y, m_x)$ has the same sign as $(q_1 — q_0) cdot (-m_y, m_x)$.

9 ответов

Лучший ответ

p = as + ad * u
p = bs + bd * v

p.x = as.x + ad.x * u
p.y = as.y + ad.y * u
p.x = bs.x + bd.x * v
p.y = bs.y + bd.y * v

as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v

v := (as.x + ad.x * u - bs.x) / bd.x

as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) 
u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)

u = ((bs.y - as.y) * bd.x - (bs.x - as.x) * bd.y) / (bd.x * ad.y - bd.y * ad.x)
v = ((bs.y - as.y) * ad.x - (bs.x - as.x) * ad.y) / (bd.x * ad.y - bd.y * ad.x)

dx = bs.x - as.x
dy = bs.y - as.y
det = bd.x * ad.y - bd.y * ad.x
u = (dy * bd.x - dx * bd.y) / det
v = (dy * ad.x - dx * ad.y) / det

bool DoRaysIntersect(Ray r1, Ray r2)
{
    // Solve the following equations for t1 and t2:
    //   r1.A.x + r1.V.x * t1 == r2.A.x + r2.V.x * t2
    //   r1.A.y + r1.V.y * t1 == r2.A.y + r2.V.y * t2
    if(no solution)  // (e.g. parallel lines)
    {
        if(r1 == r2)  // same ray?
            return true;
        else
            return false;  // parallel, non-intersecting
    }
    else  // unique solution
    {
        if(t1 >= 0 && t2 >= 0)
            return true;
        else
            return false;  // they would intersect if they are lines, but they are not lines
    }
}

/**
 * Get the intersection of two rays, with origin points p0 and p1, and direction vectors n0 and n1.
 * @param p0 The origin point of the first ray
 * @param n0 The direction vector of the first ray
 * @param p1 The origin point of the second ray
 * @param n1 The direction vector of the second ray
 * @returns
 */
export function getRaysIntersection(
  p0: number[],
  n0: number[],
  p1: number[],
  n1: number[]
): number[] | undefined {
  const dx = p1[0] - p0[0];
  const dy = p1[1] - p0[1];
  const det = n1[0] * n0[1] - n1[1] * n0[0];
  const u = (dy * n1[0] - dx * n1[1]) / det;
  const v = (dy * n0[0] - dx * n0[1]) / det;
  if (u < 0 || v < 0) return undefined; // Might intersect as lines, but as rays.

  const m0 = n0[1] / n0[0];
  const m1 = n1[1] / n1[0];
  const b0 = p0[1] - m0 * p0[0];
  const b1 = p1[1] - m1 * p1[0];
  const x = (b1 - b0) / (m0 - m1);
  const y = m0 * x + b0;

  return Number.isFinite(x) ? [x, y] : undefined;
}

bool RaysIntersection(const Point& as, const Point& ad, const Point& bs, const Point& bd, Point& result)
{
    if (as == bs) {
        result = as;
        return true;
    }
    auto dx = bs.X - as.X;
    auto dy = bs.Y - as.Y;
    auto det = bd.X * ad.Y - bd.Y * ad.X;
    if (det != 0) { // near parallel line will yield noisy results
        double u = (dy * bd.X - dx * bd.Y) / (double)det;
        double v = (dy * ad.X - dx * ad.Y) / (double)det;
        if (u >= 0 && v >= 0) {
            result = as + ad * u;
            return true;
        }
    }
    return false;
}

sign1 = cross(vector1, point1 - point2)
sign2 = cross(vector2, point2 - point1)

if (sign1 * sign2 < 0) // If signs are mismatched, they will multiply to be negative
    return intersection

У меня есть два луча на 2D-плоскости, которые простираются до бесконечности, но оба имеют начальную точку. Они оба описываются начальной точкой и вектором в направлении луча, простирающегося до бесконечности. Я хочу узнать, пересекаются ли два луча, но мне не нужно знать, где они пересекаются (это часть алгоритма обнаружения столкновений).

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

7 ответов

дано: два луча a, b с начальными точками (векторами начала) as, bs и векторами направления ad, bd.

две линии пересекаются, если есть точка пересечения p:

если эта система уравнений имеет решение для u>=0 и V>=0 (положительное направление-это то, что делает их лучей) лучи пересекаются.

для координат x/y 2d векторов это означает:

решение против v:

вставка и решение против u:

вычислить u, затем вычислить v, если оба положительны, лучи пересекаются, иначе нет.

мне жаль не согласиться с ответом Питера Уолсера. Решение уравнений дает на моем столе:

Факторинг общие условия, это:

пять вычитаний, шесть умножений и два деления.

Если вам нужно только знать, пересекаются ли лучи, достаточно знаков u и v, и эти два divisons могут быть заменены num*denom

обратите внимание, что редкий случай det==0 означает, что лучи не пересекаются (одно дополнительное сравнение).

луч может быть представлен множеством точек A + Vt , где A является отправной точкой, V является вектором, указывающим направление луча, и t >= 0 — это параметр. Таким образом, чтобы определить, пересекаются ли два луча, сделайте следующее:

линии представлены точкой p и вектора v:

line = p + a*v (для всех a)

лучи (положительная) половина этой строки:

ray = p + a*v (для всех a >= 0)

чтобы определить, пересекаются ли две линии, установите их равными и решите:

перекресток, где происходит p₁ + a₁ * v₁ = p₂ + a₂ * v₂
(обратите внимание, что есть два неизвестных, а₁ и₂, и два уравнения, поскольку pи vмногомерны)

решить₁ и₂ — если они оба неотрицательные, они пересекаются. Если один отрицательный, они не пересекаются.

GeomAlgorithms.com имеет некоторые довольно сладкие алгоритмы, связанные с линиями в 3D. Вообще говоря, вероятность пересечения двух линий в 3D-пространстве действительно довольно низкая.

в 2D вы должны проверить наклон. Если наклон не равен, они пересекаются. Если наклон равен, они пересекаются, если точка на них имеет ту же X-координату или ту же Y-координату.

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

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

мы делаем это снова для второго треугольника. Опять же, отправная точка-это отправная точка второго луча. Первый вектор-это направление второго луча, а второй вектор — от начальной точки второго луча до первый луч-отправная точка. Мы снова берем перекрестное произведение векторов и отмечаем знак.

теперь мы просто берем два знака и проверяем, одинаковы ли они. Если они одинаковы, у нас нет пересечения. Если они разные, у нас есть пересечения. Вот так!

вот некоторый код psudo:

получается пять умножений, шесть вычитаний и одно сравнение.

Если линии имеют бесконечную длину, то они будут всегда пересекаются, если они параллельны. Чтобы проверить, параллельны ли они, найдите наклон каждой линии и сравните их. Наклон будет просто (y2-y1)/(x2-x1).

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

Тема: Луч. Пересечение линий.

Сформировать представление о понятиях «луч», «точка пересечения».

Учить различать прямую линию и луч.

Учить чертить лучи по линейке.

Способствовать развитию приёмов умственной деятельности: классификация, сравнение, анализ, обобщение.

Воспитывать толерантное отношение друг к другу, взаимное сотрудничество.

— умение детьми различать и чертить лучи;

— повышение активности на уроках;

— улучшение результатов обучения.

Формирование универсальных учебных действий:

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

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

Строить точку пересечения двух лучей, точку пересечения прямой и луча .

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

Представление о луче. Существенный признак луча.(точка, обозначающая его начало). Различное расположение луча на плоскости. Варианты проведения лучей из данной точки. Обозначение луча одной буквой. Пересечение лучей.

.Оборудование: мультимедийное оборудование, презентация к уроку , учебник, тетради, «веер» цифр, карточки с цифрами.

1. Психологический настрой учащихся.

Включение учащихся в деятельность.

-Посмотрите друг на друга, улыбнитесь, пожелайте успешной работы себе, соседу, всему классу.

-Что необходимо нам для успешной работы на уроке?

-Покажите своей посадкой, что вы готовы работать.

Дети вспоминают правила «рабочего» человека.

2.Постановка учебной задачи.

для выявления «Что знаем и чего ещё не знаем?»

Есть у меня, друзья,

Могу построить я

Башню, дом и самолет,

И большущий пароход!

Учитель держит в руках большой карандаш.

-Это не простой Карандаш, а волшебный. Он знает много нового и интересного и познакомит нас с жителями страны Геометрии.

-Вспомните, какие фигуры мы узнали с помощью карандаша?

-Что можете рассказать об этих фигурах?

-Какую ставим учебную задачу?

— Мы познакомились с точкой, прямой и кривой линиями.

Фигура под №1 – прямая линия;

№ 2 – кривая замкнутая;

№ 3 – ещё не знаем;

№ 4 — кривая незамкнутая;

№ 5 – две прямые линии.

-Узнать всё о новой линии.

3.Изучение нового материала

Продолжение изучения нового материала

Поиск оптимального решения учебной задачи.

Создание условий для психоэмоциональной разгрузки учащихся.

-Чтобы узнать о новой фигуре, послушайте дальше сказку о волшебном карандаше.

-Пошёл Карандаш в гости к прямой линии и поставил на ней две точки.

-Затем пришла Резинка и стёрла часть прямой.

-И получилось не прямая, а две новые фигуры.

Итак, что скажете про новую фигуру?

-Как же называется эта фигура?

-Сейчас вы догадаетесь.

Волшебный карандаш нарисовал линию. Как она называется?

-Пошёл Карандаш по этой линии и начал ставить точки.

Говорит Карандаш Резинке: «Поиграй со мной!» И начал выбегать из каждой точки.

— А сейчас догадались?

-Правильно. А кто из вас может сказать тему нашего урока.

-Молодцы! Действительно о луче, о том, как его начертить, и пойдёт речь у нас на уроке.

1.Быстро поморгать, закрыть глаза и посидеть спокойно, медленно считая до 5. Повторить 4-5 раз.

2.Крепко зажмурить глаза

(считать до 3), открыть, посмотреть вдаль (считать до 5).

Повторить 4-5 раз.

Учитель проговаривает стихотворение:

Мы — веселые мартышки,

Мы играем громко слишком.

Все ногами топаем,

Все руками хлопаем,

Скачем на носочках.

Дружно прыгнем к потолку,

Пальчик поднесем к виску

И друг другу даже

Шире рот откроем ,

Гримасы все состроим.

Как скажу я слово три,

Все с гримасами замри.

-Рассмотрите внимательно луч. Чем он отличается от прямой линии?

-Действительно, прямую линию можно продлить как влево, так и вправо.

-Луч – это часть прямой, ограниченная с одной стороны. Лучу дают название, написав рядом с точкой букву. Например, любая буква латинского алфавита: А или В, или С, и т.д.

-Конечно, такую работу уже умеем выполнять.

Предположения детей: тема нашего урока — различные линии и точки.

-Новая фигура – это часть прямой линии.

-Плавная кривая замкнутая линия

-Это солнышко, а линии похожи на лучи солнышка.

-Тема нашего урока – луч.

Дети проговаривают стихотворение и имитируют действия мартышек.

-У луча есть начало, но нет конца.

-Луч можно продлить, только в ту сторону, в какую он направлен.

-Мы учились обозначать точки.

-Давайте попробуем начертить лучи. Как вы думаете, что для этого мы будем делать?

-Попробуйте начертить 3 луча в разных направлениях. (Для проверки детей показать

— C какой фигурой мы сегодня познакомились?

-Что вы узнали об этой фигуре?

-Думаем, что луч можно начертить с помощью линейки, так как это часть прямой линии.

-Сначала необходимо поставить точку.

-Линию из точки можно вести в любом направлении.

— Мы познакомились с лучом.

— У луча есть начало, но нет конца. Лучу можно дать название.

— Что можно сказать об этих линиях?

— Начертите в тетради две пересекающиеся линии.

-Поставьте точку в том месте, где линии пересеклись, назовите её.

-Какие новые фигуры получились? Сколько?

-Поработаем в тетрадях на печатной основе, с.

— Это прямые линии, они встретились (Кто-нибудь из детей скажет: они пересеклись)

-Получились лучи, их 4.

6.Итог урока. Рефлексия.

Развитие умений соотносить цель и результат.

Осознание учащимися своей учебной деятельности и всего класса.

— С чем познакомились?

-Чему учились на уроке?

-Что узнали нового?

-У меня получилось…

-На следующем уроке мы…

На какой ступеньке лесенки вы бы хотели сейчас стоять?

Ничего не понятно на уроке. -1

Все понятно на уроке, затруднений нет.- 2

Хочу знать больше. -3

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

• Шаповалова Елена ВикторовнаНаписать 1466 20.10.2015

Номер материала: ДВ-082410

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

20.10.2015 475

20.10.2015 1942

20.10.2015 665

20.10.2015 2108

20.10.2015 2808

20.10.2015 1077

20.10.2015 744

Не нашли то что искали?

Вам будут интересны эти курсы:

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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

Ответы на вопрос

ответ: мама больше купила овощей на 1 килограмм

1)1 км коля проходит за t = 1/6 = 0,1(6) часа

2) при переводе в минуты получается 0,1(6) получаем 10 мин.

3) 25 — 10 = 15 мин.

коля успевает дойти до школы за 10 мин с запасом времени 15 мин.