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

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

Уравнения линий имеют вид

P_a = P1 + u_a ( P2 — P1 )

P_b = P3 + u_b ( P4 — P3 )

Решение относительно точки P_a = P_b дает два уравнения на координаты (u_a и u_b)

x1 + u_a (x2 — x1) = x3 + u_b (x4 — x3)
и
y1 + u_a (y2 — y1) = y3 + u_b (y4 — y3)

Решая относительно u_a и u_b имеем

Подстановка любого из этих значений в соответствующее уравнение прямой даст точку пересечения. Пусть, например, точка пересечения (x,y):

x = x1 + u_a (x2 — x1)

y = y1 + u_a (y2 — y1)

BOOL IsLinesCross(_int64 x11, _int64 y11, _int64 x12, _int64 y12, _int64 x21, _int64 y21, _int64 x22, _int64 y22) < _int64 maxx1 = max(x11, x12), maxy1 = max(y11, y12); _int64 minx1 = min(x11, x12), miny1 = min(y11, y12); _int64 maxx2 = max(x21, x22), maxy2 = max(y21, y22); _int64 minx2 = min(x21, x22), miny2 = min(y21, y22); if (minx1 >maxx2 || maxx1 < minx2 || miny1 >maxy2 || maxy1 < miny2) return FALSE; // Момент, када линии имеют одну общую вершину. _int64 dx1 = x12-x11, dy1 = y12-y11; // Длина проекций первой линии на ось x и y _int64 dx2 = x22-x21, dy2 = y22-y21; // Длина проекций второй линии на ось x и y _int64 dxx = x11-x21, dyy = y11-y21; _int64 div, mul; if ((div = (_int64)((double)dy2*dx1-(double)dx2*dy1)) == 0) return FALSE; // Линии параллельны. if (div > 0) < if ((mul = (_int64)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul >div) return FALSE; // Первый отрезок пересекается за своими границами. if ((mul = (_int64)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul >div) return FALSE; // Второй отрезок пересекается за своими границами. > if ((mul = -(_int64)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul >-div) return FALSE; // Первый отрезок пересекается за своими границами. if ((mul = -(_int64)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul >-div) return FALSE; // Второй отрезок пересекается за своими границами. return TRUE; >

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

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

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

Параметрическое уравнение отрезка

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

Параметр может иметь ограничения или не иметь их.

система из параметрических уравнений: | x = x0 + vt | y = y0 + wt где v и w координаты (x, y) вектора направления v = x1 - x0 w = y1 + y0 при 0 ≤ t ≤ 1 - уравнения описывают отрезок, при 0 ≤ t < +∞ - уравнения описывают луч, при -∞ < t < +∞ - уравнения описывают прямую

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

Система из 4-х параметрических уравнений позволяет найти точку пересечения двух отрезков. Нахождение точки пересечения отрезков аналогично описанному для двух лучей.

Дано: отрезок AB с координатами начальной и конечной точек - A(2;2) и B(7;3) , отрезок CD с координатами - C(4;1) и D(5;6) . Найти возможную точку пересечения отрезков AB и CD .

Отрезки имеют точку пересечения если оба параметра отрезков больше или равно нулю и меньше или равно единице.

| x = 2 + (7 - 2)tab | x = 2 + 5tab | y = 2 + (3 - 2)tab => | y = 2 + tab | x = 4 + (5 - 4)tcd | x = 4 + tcd | y = 1 + (6 - 1)tcd | y = 1 + 5tcd 

Чтобы узнать есть ли точка пересечения отрезков AB и CD вычислим их параметры:

найдём соотношение параметров через возможно общую координату x 2 + 5tab = 4 + tcd => 5tab = 2 + tcd => tab = (2 + tcd)/5 (у.1) вычислим параметр tcd через возможно общую координату y 2 + tab = 1 + 5tcd => 2 + (2 + tcd)/5 = 1 + 5tcd => 10 + 2 + tcd = 5 + 25cd => tcd = 7/24 ≈ 0.292 вычислим параметр tab использую полученное соотношение (у.1) tab = (2 + 0.292)/5 ≈ 0.458

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

x = 2 + 5tab => x = 2 + 5 * 0.458 = 4.29 y = 2 + tab => y = 2 + 0.458 = 2.458

Точка пересечения отрезков AB и CD имеет координаты (4.29; 2.458).

Отрезки не пересекаются

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

Дано: отрезок AB с координатами начальной и конечной точек - A(5;4) и B(10;5) , отрезок CD с координатами - C(3;3) и D(7;6) . Определить: отрезки пересекаются или не пересекаются. Если отрезки не пересекаются, найти мнимую точку пересечения.

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

| x = 5 + (10 - 5)tab | x = 5 + 5tab | y = 4 + (5 - 4)tab => | y = 4 + tab | x = 3 + (7 - 3)tcd | x = 3 + 4tcd | y = 3 + (6 - 3)tcd | y = 3 + 3tcd 

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

3 + 4tcd = 5 + 5tab => 4tcd = 2 + 5tab => tcd = (2 + 5tab)/4 3 + 3tcd = 4 + tab => 3 + 3(2 + 5tab)/4 = 4 + tab => 3 + (6 + 15tab)/4 = 4 + tab => 2 + 11tab = 0 => tab = -2/11 ≈ -0.182 параметр tab меньше нуля, значит отрезки не пересекаются tcd = (2 + 5tab)/4 => tcd = (2 + 5*-0.182)/4 ≈ 0.273 параметр tcd положительный и меньше единицы, значит мнимая точка лежит на отрезке CD

Найдем мнимую точку, расположенную на отрезке CD :

x = 5 + 5 * -0.182 = 4.09 y = 4 - 0.182 = 3.818

Метод SegmentSegment(. )

Метод вычисления точки пересечения отрезков инкапсулирован в классе Intersections. Метод статический, для вычисления точки пересечения не требуется создание экземпляра класса. Методы вычисляющие точки пересечения прямых и лучей описаны на страницах точка пересечения двух прямых на плоскости, пересечение луча и прямой, пересечение двух лучей.

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

class Intersections < // Вычисление точки пересечения отрезков. public static bool SegmentSegment(Point r1, Point r2, Point p1, Point p2, out Point pCross, out Info info) < // Параметрическое уравнение отрезка // x = x0 + vt // y = y0 + wt // где v = x1 - x0 // w = y1 - y0 // при 0 else if (v == 0 && w == 0) < info.Id = 11; info.Message = "Синий отрезка неопределён"; return false; >else if (v2 == 0 && w2 == 0) < info.Id = 12; info.Message = "Красный отрезка неопределён"; return false; >// Для вычисления параллельности отрезка // необходимо сравнить направления их векторов. // Вычисляем длины векторов double lenBlue = Math.Sqrt(v * v + w * w); double lenRed = Math.Sqrt(v2 * v2 + w2 * w2); // Нормализация векторов - создание единичного вектора направления double x = v / lenBlue; double y = w / lenBlue; double x2 = v2 / lenRed; double y2 = w2 / lenRed; // Точность совпадения величин double double epsilon = 0.000001; // Проверка на совпадение if (r1.X == p1.X && r1.Y == p1.Y && r2.X == p2.X && r2.Y == p2.Y) < info.Id = 20; info.Message = "Отрезки совпадают"; return false; >// Проверка на параллельность с определенной точностью. if (Math.Abs(x - x2) < epsilon && Math.Abs(y - y2) < epsilon) < info.Id = 21; info.Message = "Отрезки параллельны"; return false; >// ===== /Частные случаи не пересечения ===== // ===== Вычисление точки пересечения ===== // Проверка факта пересечения // x = p1.X + v2t2 // y = p1.Y + w2t2 // r1.X + vt = p1.X + v2t2 => vt = p1.X - r1.X + v2t2 => // t = (p1.X - r1.X + v2t2) / v - (у.1) соотношение t-параметров // // Вычисление одного параметра с заменой соотношением другого // r1.Y + wt = p1.Y + w2t2 => wt = p1.Y - r1.Y + w2t2 => t = (p1.Y - r1.Y + w2t2) / w // (p1.X - r1.X + v2t2) / v = (p1.Y - r1.Y + w2t2) / w => // (p1.X - r1.X + v2t2) * w = (p1.Y - r1.Y + w2t2) * v => // w * p1.X - w * r1.X + w * v2t2 = v * p1.Y - v * r1.Y + v * w2t2 => // w * v2t2 - v * w2t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y => // (w * v2 - v * w2) * t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y => // t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2) - (у.2) double t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2); // t = (p1.X - r1.X + v2t2) / v - (у.1) double t = (p1.X - r1.X + v2 * t2) / v; // Если один из параметров меньше 0 и больше 1, значит пересечения нет. if (t < 0 || t >1 || t2 < 0 || t2 >1) < info.Id = 20; info.Message = "Пересечения нет"; return false; >// Координаты точки пересечения pCross.X = p1.X + v2 * t2; pCross.Y = p1.Y + w2 * t2; info.Id = 0; info.Message = "Пересечение есть"; return true; // ===== /Вычисление точки пересечения ===== > > public class Info < // Для визуального сообщения. public string Message; // Для автоматических действий. public int Id; >

Исходник приложения с классом Intersections

К странице приложен исходник приложения на языке C#. Приложение демонстрирует вычисление точки пересечения двух отрезков. Графика приложения создает различные положения отрезков на плоскости окна. Управление начальными и конечными точками мышью и служебными клавишами.

Скачать исходник

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

Пересечение множества отрезков

Пусть дано множество из [math]n[/math] отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за [math]O(n^2)[/math] ; ясно также, что любой алгоритм будет в худшем случае работать за [math]\Theta(n^2)[/math] (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя [math]O((n+I)\log)[/math] времени и [math]O(n)[/math] памяти, где [math]I[/math] — количество пересечений.

Формальная постановка задачи

Дано: [math]S[/math] — множество замкнутых отрезков на плоскости. Найти все точки их взаимного пересечения, охарактеризовав каждую точку пересечения множеством отрезков, которые участвуют в этом пересечении.

Описание алгоритма

Заметающая прямая и события

Воспользуемся методом заметающей прямой (sweep line), расположенной горизонтально и двигающейся вниз (в сторону уменьшения y-координаты). Нас будут интересовать события (events, event points) трёх типов:

• верхний конец отрезка,
• нижний конец отрезка,
• точка пересечения пары отрезков;

причем о событиях первых двух типов мы знаем заранее, а события, являющиеся пересечением отрезков, будут обнаружены и добавлены в множество необработанных событий динамически. Будем считать, что если у двух точек равные ординаты, то выше та, что лежит левее. Таким образом верхним концом горизонтального отрезка, в силу введенного порядка, является его левый конец. Это даст нам корректную обработку вырожденного случая, когда отрезок горизонтален.

Приоритет событий

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

Нам потребуется две структуры данных.

Во-первых, мы будем хранить очередь событий [math]Q[/math] в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за [math]O(\log)[/math] , где [math]m[/math] — количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.

Во вторых, будем хранить статус [math]T[/math] заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.

Статус заметающей прямой

Соседние отрезки в статусе

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

Далее приведен псевдокод алгоритма, а ниже подробно расписана обработка события определенного типа.

findIntersections(S) Инициализировать Q и T for s in S вставить концы s в Q (вместе с верхним концом вставить сам s) while not Q.empty() p = Q.pop() handleEventPoint(p)

Рассмотрим обработку событий.

• Верхний конец отрезка. В этом случае мы вставим отрезок в статус и проверим, не пересекает ли он соседние отрезки в статусе. Нас будут интересовать только пересечения ниже заметающей прямой. Естественно, если пересечения будут обнаружены, то они должны быть вставлены в [math]Q[/math] .

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

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

Обработка верхних концов и пересечений

Обработка нижних концов

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

handleEventPoint(p) U(p) = множество отрезков, верхний конец которых есть p // Напомним, что мы храним такие отрезки в Q вместе c p // Далее найдём в T все отрезки, которые содержат p (они будут соседними в дереве) L(p) = множество отрезков, нижний конец которых есть p C(p) = множество отрезков, содержащих внутри себя p if [math] \vert L(p) \cup C(p) \cup U(p) \vert \gt 1[/math] report(p, [math]L(p) \cup C(p) \cup U(p)[/math]) // сообщить о p как о точки пересечения отрезков [math]L(p) \cup C(p) \cup U(p)[/math] T.remove([math]L(p) \cup C(p)[/math]) T.insert([math]C(p) \cup U(p)[/math]) // отрезки должны быть вставлены в порядке, // в котором они пересекают горизонтальную линию, // лежащую немного ниже заметающей прямой // (при удалении-вставке отрезков из C(p) - те поменяют порядок на обратный if [math]C(p) \cup U(p) = \emptyset[/math] s_l = левый сосед p в T s_r = правый сосед p в T findIntersection(s_l, s_r, p) else s1 = самый левый отрезок из [math]C(p) \cup U(p)[/math] в T s_l = левый сосед s1 в T findIntersection(s_l, s1, p) s2 = самый правый отрезок из [math]C(p) \cup U(p)[/math] в T s_r = правый сосед s2 в T findIntersection(s2, s_r, p)

findIntersection(s_l, s_r, p) if not intersects(s_l, s_r) return x = точка пересечения s_l и s_r if x лежит ниже заметающей прямой или на ней справа от p Q.insert(x) // должно работать корректно, если x уже есть в Q

Поддержание статуса при обработке события

Доказательство корректности

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

Пусть [math]p[/math] — точка пересечения нескольких отрезков, причем [math]p[/math] не совпадает ни с одним из концов отрезков, участвующих в пересечении. Отсортируем отезки по углу вокруг [math]p[/math] и пусть отрезки [math]s_i[/math] и [math]s_j[/math] окажутся соседними в сортировке. Тогда существует событие [math]q[/math] с приоритетом выше, чем у [math]p[/math] , такое что при обработке этого события [math]s_i[/math] и [math]s_j[/math] будут соседними в статусе.

Алгоритм сообщает о всех точках пересечения

Воспользуемся индукцией по событиям, отсортированным в порядке, введённом выше ( [math]p \lt q \Leftrightarrow p_y \lt q_y \lor p_y = q_y \land p_x \lt q_x[/math] ). Пусть [math]p[/math] — точка пересечения. Предположим что все события [math]q, q \lt p[/math] были обработаны корректно. Тогда [math]p[/math] будет обнаружена.

Действительно, если [math]p[/math] — конец некоторого отрезка, то [math]p[/math] добавлена в очередь событий в начале работы. Все содержащие её отрезки из статуса, который будет текущим при обработке [math]p[/math] будут найдены. Для остальных отрезков, содержащих [math]p[/math] , верно, что [math]p[/math] — их верхний конец, и они будут найдены, т.к. мы храним их вместе с [math]p[/math] в очереди.

Оценка времени работы

Время работы алгоритма — [math]O((n+I)\log)[/math] , где [math]I[/math] — количество пересечений.

Инициализация [math]Q[/math] может быть выполнена за [math]O(n\log)[/math] , инициализация [math]T[/math] — за [math]O(1)[/math] .

Далее, по ходу алгоритма мы обрабатываем каждое событие. Обработка включает в себя удаление события ( [math]O(\log)[/math] ), вызов функции findIntersection до двух раз, что может вызвать вставку новых событий [math]O(\log)[/math] . Также при обработке события [math]p[/math] мы [math]m(p) = \vert L(p) \cup C(p) \cup U(p) \vert[/math] раз выполняем операции вставки, удаления, поиска над [math]T[/math] . Каждая из этих операций требует [math]O(\log)[/math] времени. Пусть [math]m = \sum_

[/math] . Тогда время работы алгоритма — [math]O(m\log)[/math]

Покажем, что [math]m = O(n + I)[/math] , где [math]I[/math] — количество пересечений. Для этого рассмотрим планарный граф, вершинами которого являются концы отрезков, а также их точки пересечения, а ребрами — части отрезков, их соединяющие. Рассмотрим событие [math]p[/math] . Ему соответствует вершина графа со степенью [math]O(m(p))[/math] , следовательно [math]m = O(\sum_

) = O(E) = O(V) = O(2n + I)[/math] , где [math]deg(p)[/math] — степень [math]p[/math] , [math]E[/math] — число ребер в графе, [math]V[/math] — число вершин. (Предпоследний переход следует из формулы Эйлера.)

Объём памяти

Очевидно, что статус в худшем случае занимает [math]O(n)[/math] памяти, однако очередь событий может занимать [math]O(n + I)[/math] памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до [math]O(n)[/math] . Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.

Источники

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 2: Line Segment Intersection: pp.20–29.

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

Пересечение отрезков

Обозначения:
Отрезок 1 обозначим как AB и пусть он имеет координаты A(x₁;y₁) B(x₂; y₂)
Отрезок 2 обозначим как CD и пусть он имеет координаты C(x₃;y₃) B(x₄; y₄)

Чтобы вычислить правильные угловые коэффициенты, должно выполняться условие x₁ ≤ x₂; x₃ ≤ x₄;
Если нет - то меняем местами пары координат отрезков.

Шаг 2. Если x₁ ≥ x₂ то меняем между собой значения x₁ и x₂ и y₁ и y₂
Шаг 3. Если x₃ ≥ x₄ то меняем между собой значения x₃ и x₄ и y₃ и y₄ ;

Шаг 4. Проверяем, равны ли между собой у₂ и у₁,
если у₂ = у₁ да, то принимаем k₁ = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k₁ = ( у₂ - у₁ ) / ( x₂ - x₁ )

Шаг 5. Проверяем, равны ли между собой у₃ и у₄,
если у₃ = у₄ да, то принимаем k₂ = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k₂ = ( у₄ - у₃ ) / ( x₄ - x₃ )

Шаг 6. Проверим отрезки на параллельность.
Если k₁ = k₂ , то прямые параллельны и отрезки пересекаться не могут. Решение задачи прекращаем.

Шаг 7. Вычисляем значения свободных переменных
Определяем свободные члены в уравнении прямой:
b₁ = у₁ - k₁ * x₁
b₂ = у₃ - k₂ * x₃

Шаг 8. Решаем систему уравнений:
y = k₁ x + b₁
y = k₂ x + b₂

Если прямые имеют точку пересечения, то
k₁ x + b₁ = k₂ x + b₂

Откуда и вычисляем точку пересечения прямых
x = ( b₂ - b₁ ) / ( k₁ - k₂ )
y = k₁ x + b₁.

Шаг 9.Учтем, что точка пересечения прямых может лежать вне отрезков, принадлежащих этим прямым. Таким образом, если отрезки пересекаются, то, поскольку
x₁ ≤ x₂; x₃ ≤ x₄;
должны выполняться условия:
x₁ ≤ x₄ и x₄ ≤ x₂
или
x₁ ≤ x₃ и x₃ ≤ x₂

Если одно из двух условий верно, то отрезки имеют точку пересечения, иначе - отрезки не пересекаются.