Что такое пересечение отрезков

Урок 32. Пересекаются ли два отрезка?

Урок из серии «Геометрические алгоритмы»

Здравствуйте, дорогой читатель. Напишем еще три новые функции.

Функция LinesCross() будет определять, пересекаются ли два отрезка. В ней взаимное расположение отрезков определяется с помощью векторных произведений. Для вычисления векторных произведений напишем функцию — VektorMulti().

Функция RealLess() будет использоваться для реализации операции сравнения «

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

Решение
Пусть даны два отрезка. Первый задан точками . Второй задан точками .

Взаимное расположение отрезков можно проверить с помощью векторных произведений:

Рассмотрим отрезок и точки и .

Точка лежит слева от прямой , для нее векторное произведение > 0, так как векторы положительно ориентированы.

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

Аналогичные рассуждения можно провести для отрезка и точек и .

Итак, если , то отрезки пересекаются.

Для проверки этого условия используется функцию LinesCross(), а для вычисления векторных произведений – функция VektorMulti().

Векторное произведение двух векторов вычисляется по формуле:

ax, ay — координаты первого вектора,

bx, by — координаты второго вектора.

Результаты выполнения программы:

Мы написали программу, определяющую, пересекаются ли отрезки, заданные своими координатами.

На следующем уроке мы составим алгоритм, с помощью которого можно будет определить, лежит ли точка внутри треугольника.

Уважаемый читатель. Вы уже познакомились с несколькими уроками из серии «Геометрические алгоритмы». Все ли доступно написано? Я буду Вам очень признательна, если Вы оставите отзыв об этих уроках. Возможно, что-то нужно еще доработать.

Источник

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

Введение

Уже не раз на habr затрагивалась данная тема: раз, два.

Я лишь хочу поделиться своей реализацией. Думаю, это кому-то пригодится.

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

Подготовка

Весь последующий код будет приведён на языке Java

Для начала создадим вспомогательный класс Dot. В нём всего две переменные x и y:

Задача 1: определить, касаются ли отрезки.

Решение:
Из векторного произведения мы можем узнать, обхо́дим мы вектор по часовой или против часовой. Это поможет понять где находятся точки. Соединим точки A и D, A и C.

Перемножим вектора main и v2, main и v1. Если полученные произведения имеют разные знаки, значит точки C и D находятся по разные стороны относительно отрезка AB. Назовём такой метод fromDifferentSides:

Таким же образом необходимо проверить точки A и B относительно отрезка CD. Соединим это в один метод и получится следующее:

Задача 2: определить точку касания.

Решение:
Как и в предыдущей задаче определяем, касаются ли отрезки. Если касаются, начинаем определять эту точку. Через подобие найдём длину DO. Коэффициент подобия (k) равен отношению уже известных нам векторных произведений:

В третей строчке проверяем пограничный случай. Теперь узнаем чему равно DO. Для этого решим систему уравнений:

DO = CO*k
Подставляем во второе уравнение:
CO*k+CO = CD
CO(k+1)= CD
CO = CD/(k+1)
В итоге:
DO = (CD/(k+1))*k

Теперь создаём вектор CD и уменьшаем его до длинны DO. Но поскольку мы будем его умножать, нужно взять обратное от (k+1)*k:

Теперь осталось добавить вектор к точке D:

Вот и всё! Мы получили заветную точку.

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

Функцию нахождения точки я назвал pointOfIntersection. Привожу полный код на Java:

Источник

Пересечение отрезков и поворот: определение, свойства, вычисление

Содержание

Аффинное пространство [ править ]

Ориентация [ править ]

Ориентация векторов [ править ]

Из курса линейной алгебры известно, что любые две такие формы отличаются друг от друга только на некоторый множитель. Зафиксируем одну из таких форм (например, считая, что форма равна 1 на наборе из векторов выделенного базиса). Назовем ориентацией набора из N N-мерных векторов знак значения этой формы на этом наборе векторов.

Отметим свойства ориентации:

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

Заметим, что определитель является в точности кососимметричной линейной формой от N N-мерных векторов, а значит, подходит для вычисления ориентации набора векторов.

Ориентация точек [ править ]

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

Предикат левый поворот [ править ]

О точном вычислении ориентации см. раздел Ссылки.

Пересечение отрезков [ править ]

В случае, если обе ориентации в одной из строк равны нулю, отрезки лежат на одной прямой, и в этом случае пересечение можно проверить способом, аналогичным пересечению отрезков на действительной прямой (считаем, что точки сравниваются лексикографически):

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

Источник

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

Введение

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

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

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

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

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

Мой способ

Задача

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

Решение

Условные обозначения для исключения недопониманий: a — вектор a, a(y) — проекция вектора a на ось Y, a — вектор a, заданный координатами x1,y1.

Представим наши отрезки в виде двух векторов: a и b. Обратите, внимание, что вектор b имеет противоположное от ожидаемого направление. Введём вектор c. Заметим, что a*k+b*n=c, где k,n — некоторые коэффициенты. Таким образом, получаем систему уравнений:

a(x)*k+b(x)*n=c(x)
a(y)*k+b(y)*n=c(y)
Наша задача сводится к нахождению этих коэффициентов (правда сказать, достаточно найти лишь один из них).

Внимательный читатель заметит, что при a(y)=0, мы получим ошибку. Пропишем ветвление на этапе нахождения a(y). Этот случай ещё проще, ведь мы сразу получаем уравнение с одной неизвестной.

Рекомендую попробовать вывести n самостоятельно, так будет понятнее, что откуда берётся в коде ниже.

Зная n, можно найти точку пересечения, для этого мы отнимем от координаты точки (x3,y3) вектор b*n

Собираем воедино

Данная функция принимает координаты вершин и возвращает значение 1, если прямые отрезков (именно прямые) пересекаются, иначе 0. Если же вам нужны координаты вершин, вы сможете взять их из массива dot[].

Важно: при введении двух совпадающих прямых, алгоритм выводит отсутствие пересечения. Алгоритм находит точку пересечения прямых, на которых лежат отрезки, поэтому точка может оказаться за пределами отрезка (что вам придётся дополнительно проверить в уже своём коде).

Источник

Еще один алгоритм определения пересечения двух отрезков

Недавно была публикация «Простой алгоритм определения пересечения двух отрезков». Я решил попробовать решить задачу пересечения двух отрезков немного по-другому, более геометрически.

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

Имеем 2 отрезка и , где P0,P1,P2,P3 точки на плоскости. Будем обозначать x y координаты точки P как P.x и P.y
Имеем координаты 4 точек в массиве P(0..3) структуры point(x float, y float):

Шаг 1 — Перенос начала координат.

Запомним координаты точек P в дополнительном массиве P_copy. Перенесем начало системы координат в точку P0 и пересчитаем координаты точек:

Шаг 2 — Поворот начала координат
Повернем систему координат так, чтобы отрезок принял вертикальное положение (лег на ось Y). Вычислим длину отрезка как:
L1 = SQRT ( (P(1).x)^2 + (P(1).y)^2 )

Синус и косинус угла alfa поворота осей координат:

Cнова пересчитываем координаты точек P1,P2,P3:

Шаг 3 — Поиск точки пересечения отрезков.

Запишем уравнение отрезка и найдем точку его пересечения CR с осью Y:

Если P(2).x = P(3).x, то это означает, что отрезок вертикален и параллелен отрезку . Пересечение отрезков возможно только если второй отрезок тоже лежит на оси Y, и один из его концов лежит в первом отрезке (или касается) или отрезок накрывает . Будем считать что для результата нам достаточно одной точки. Это будет одна из точек P0..P3.

Источник