Как найти точку пересечения отрезков
Перейти к содержимому

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

  • автор:

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

В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.
Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются — найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.

Задача

Даны два отрезка, каждый из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.

Решение

Для начала необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно быть соблюдено для обоих отрезков следующее: конечные точки одного из отрезков должны лежать в разных полуплоскостях, если разделить плоскость линией, на которой лежит второй из отрезков. Продемонстрируем это рисунком.
image
На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка — нетривиальная задача, но у страха глаза велики, и всё не так сложно. Мы знаем, что векторное умножение двух векторов даёт нам третий вектор, направление которого зависит от того, положительный или отрицательный угол между первым и вторым вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только компоненту Z, соответственно и отличие произведений векторов будет только в этой компоненте. Причем при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор разделяющего отрезка на векторы направленные от начала разделяющего отрезка к обеим точкам проверяемого отрезка.
image
Если компоненты Z обоих произведений будет иметь различный знак, значит один из углов меньше 0 но больше -180, а второй больше 0 и меньше 180, соответственно точки лежат по разные стороны от прямой. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой.
Если один из компонент Z является нулём, значит мы имеем пограничный случай, когда точка лежит аккурат на проверяемой прямой. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо и оба отрезка удовлетворяют условию, значит пересечение существует. Давайте найдём его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль (длина вектора) будет численно равен именно этой компоненте. Давайте посмотрим, как найти точку пересечения.
image
Длина векторного произведения векторов a и b (как мы выяснили, численно равная его компоненте Z) равна произведению модулей этих векторов на синус угла между ними (|a| |b| sin(ab)). Соответственно, для конфигурации на рисунке мы имеем следующее: |AB x AC| = |AB||AC|sin(α), и |AB x AD| = |AB||AD| sin(β). |AC|sin(α) является перпендикуляром, опущенным из точки C на отрезок AB, а |AD|sin(β) является перпендикуляром, опущенным из точки D на отрезок AB (катетом ADD’). Так как углы γ и δ — вертикальные углы, то они равны, а значит треугольники PCC’ и PDD’ подобны, а соответственно и длины всех их сторон пропорциональны в равном отношении.
Имея Z1 (AB x AC, а значит |AB||AC|sin(α) ) и Z2 (AB x AD, а значит |AB||AD|sin(β) ), мы можем рассчитать CC’/DD’ (которая будет равна Z1/Z2), а также зная что CC’/DD’ = CP/DP легко можно высчитать местоположение точки P. Лично я делаю это следующим образом:

Px = Cx + (Dx-Cx)*|Z1|/|Z2-Z1|;
Py = Cy + (Dy-Cy)*|Z1|/|Z2-Z1|;

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

 1 template 2 bool are_crossing(vector const &v11, vector const &v12, vector const &v21, vector const &v22, vector *crossing) 3 < 4 vectorcut1(v12-v11), cut2(v22-v21); 5 vector prod1, prod2; 6 7 prod1 = cross(cut1 * (v21-v11)); 8 prod2 = cross(cut1 * (v22-v11)); 9 10 if(sign(prod1[Z]) == sign(prod2[Z]) || (prod1[Z] == 0) || (prod2[Z] == 0)) // Отсекаем также и пограничные случаи 11 return false; 12 13 prod1 = cross(cut2 * (v11-v21)); 14 prod2 = cross(cut2 * (v12-v21)); 15 16 if(sign(prod1[Z]) == sign(prod2[Z]) || (prod1[Z] == 0) || (prod2[Z] == 0)) // Отсекаем также и пограничные случаи 17 return false; 18 19 if(crossing) < // Проверяем, надо ли определять место пересечения 20 (*crossing)[X] = v11[X] + cut1[X]*fabs(prod1[Z])/fabs(prod2[Z]-prod1[Z]); 21 (*crossing)[Y] = v11[Y] + cut1[Y]*fabs(prod1[Z])/fabs(prod2[Z]-prod1[Z]); 22 >23 24 return true; 25 > 

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

Варианты пересечения отрезков

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

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

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

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

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

система из параметрических уравнений: | 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#. Приложение демонстрирует вычисление точки пересечения двух отрезков. Графика приложения создает различные положения отрезков на плоскости окна. Управление начальными и конечными точками мышью и служебными клавишами.

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

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

Как найти координаты пересечения двух отрезков зная их концы и угол при пересечении?

У меня есть координаты двух точек. А(1,7) и Б(8, 2). В коде, угол пересечения прямых, из этих точек, будет динамическим от 90 до -90 градусов (на картинке я показал угол). и для примера взял угол в 45 градусов. От того какой угол я задам, мне надо будет отрисовать точку С по найденным координатам, но как их найти? Какая последовательность действий мне нужна? Снизу я добавил картинки того, как должны выглядеть прямые, если я задам угол в 90 и -90 градусов Точка С лежит на диагонали пример задачи как будут выглядеть прямые, если я задам угол 90 или -90 градусов

  • javascript
  • геометрия
  • вычислительная-геометрия

Отслеживать
81.6k 9 9 золотых знаков 78 78 серебряных знаков 136 136 бронзовых знаков
задан 29 апр 2020 в 14:24
31 6 6 бронзовых знаков
ну задача хорошая - а вы сами то пытались что то сделать ?
29 апр 2020 в 14:29
@MaximLensky вопрос не всегда предполагает, что автор что-то должен был пытаться.
29 апр 2020 в 14:31

@MaximLensky всё, в некотором приближении - задание. В данном случае, ТС сформулировал свою проблему своими словами. Формулировка достаточно ясна и в будущем пригодится тем, у кого будет аналогичный вопрос. Какие именно попытки решения вы хотите увидеть? )

29 апр 2020 в 14:35

@MaximLensky поэтому я и хочу улучшить его, чтобы этот вопрос остался в базе знаний Stack Overflow 😉

29 апр 2020 в 14:40
@StrangerintheQ почему никто не может подсказать как делать, если все пишут что это легко?)
29 апр 2020 в 16:51

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

Аналитическое решение для этой задачи есть, но у меня получилось очень громоздкое. Поэтому предлагаю численно подобрать решение бинарным поиском. Код на Python. dx, dy - ширина и высота, an - угол в радианах. Ответ - два смещения от вершины.

from math import sqrt, cos, pi def calcpos(dx, dy, an): l = 0 r = 0.5 cosa = cos(an) dx2 = dx * dx dy2 = dy * dy dxdy = dx2 + dy2 while (r - l > 0.0001): t = (l + r) / 2 tt = 1 - t ca = dxdy * t * tt / sqrt((dx2 * t * t + dy2 * tt * tt)*(dy2 * t * t + dx2 * tt * tt)) if ca > cosa: r = t else: l = t return [(dx * l, dy * (1 - l)), (dx * (1 - l), dy * l)] print(calcpos(2, 3, pi/4)) >> [(0.5621337890625, 2.15679931640625), (1.4378662109375, 0.84320068359375)] 

Проверочка (углы показаны дополнительные до 180):

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

Пусть дано множество из [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.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *