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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

Имеем 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.

Источник

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Найти точку пересечения отрезков

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

Начальные условия

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

Входными параметрами метода являются 4 точки – точки начала и конца двух отрезков.

Точка – это экземпляр класса Point. Она имеет два параметра: значение абсциссы (x) и значение ординаты (y). Класс Point:

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

Метод, который будет искать пересечение двух отрезков, назовём: checkIntersectionOfTwoLineSegments. Он возвращает true, если отрезки пересекаются и false в противном случае.

Его аргументы – это четыре точки. p1 и p2 – начало и конец первого отрезка, а p3 и p4 – соответственно начало и конец второго отрезка.

Мы подразумеваем, что начальная точка находится левее конечной относительно оси абсцисс (оси X). Также возможен вариант, когда точки имеют одинаковую абсциссу, то есть отрезок является вертикальным.

В общем случае должно выполняться условие: p1.x

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

Если конец первого отрезка находится левее начала правого отрезка (по оси X), то отрезки точно не имеют точки пересечения.

Потенциальный интервал пересечения имеется. Идём далее.

Оба отрезка вертикальные (частный случай)

Мы отдельно от общего решения будем рассматривать вертикальные отрезки, поскольку тангенс 90 градусов не определён, и, тем самым, мы в общем решении избежим деления на ноль.

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

Непересекающиеся (слева) и пересекающиеся (справа) вертикальные отрезки

Отрезок вертикальный, тогда и только тогда, когда абсциссы его обеих точек равны.

В случае проверки условия вертикальности обоих отрезков, выражение (p1.x – p2.x == 0) && (p3.x – p4.x == 0) должно быть истинным.

Два отрезка будут иметь точку пересечения в том случае, когда их абсцисса одинакова (для этого достаточно условия p1.x == p3.x) и они имеют общую часть по оси ординат (общий Y); в противном случае делаем вывод, что они не пересекаются.

Составить условие для проверки существования общего Y мысленно довольно сложно. Поэтому мы поступим проще: составим условие для проверки того, что отрезки не имеют общего Y и возьмём от него отрицание.

Напишем код на Java для всего вышесказанного:

Источник

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

Введение

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

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

Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти 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[].

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

Источник