Простой алгоритм определения пересечения двух отрезков
В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.
Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются — найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.
Задача
Даны два отрезка, каждый из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.
Решение
Для начала необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно быть соблюдено для обоих отрезков следующее: конечные точки одного из отрезков должны лежать в разных полуплоскостях, если разделить плоскость линией, на которой лежит второй из отрезков. Продемонстрируем это рисунком. 
На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка — нетривиальная задача, но у страха глаза велики, и всё не так сложно. Мы знаем, что векторное умножение двух векторов даёт нам третий вектор, направление которого зависит от того, положительный или отрицательный угол между первым и вторым вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только компоненту Z, соответственно и отличие произведений векторов будет только в этой компоненте. Причем при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор разделяющего отрезка на векторы направленные от начала разделяющего отрезка к обеим точкам проверяемого отрезка. 
Если компоненты Z обоих произведений будет иметь различный знак, значит один из углов меньше 0 но больше -180, а второй больше 0 и меньше 180, соответственно точки лежат по разные стороны от прямой. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой.
Если один из компонент Z является нулём, значит мы имеем пограничный случай, когда точка лежит аккурат на проверяемой прямой. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо и оба отрезка удовлетворяют условию, значит пересечение существует. Давайте найдём его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль (длина вектора) будет численно равен именно этой компоненте. Давайте посмотрим, как найти точку пересечения. 
Длина векторного произведения векторов 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 >
Как определить пересекаются ли отрезки
Уравнения линий имеют вид
Pa = P1 + ua ( P2 — P1 )
Pb = P3 + ub ( P4 — P3 )
Решение относительно точки Pa = Pb дает два уравнения на координаты (ua и ub)
x1 + ua (x2 — x1) = x3 + ub (x4 — x3)
и
y1 + ua (y2 — y1) = y3 + ub (y4 — y3)
Решая относительно ua и ub имеем
Подстановка любого из этих значений в соответствующее уравнение прямой даст точку пересечения. Пусть, например, точка пересечения (x,y):
x = x1 + ua (x2 — x1)
y = y1 + ua (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#. Приложение демонстрирует вычисление точки пересечения двух отрезков. Графика приложения создает различные положения отрезков на плоскости окна. Управление начальными и конечными точками мышью и служебными клавишами.
Скачать исходник
Тема: «Точка пересечения двух отрезков»
Как определить пересекаются ли отрезки
Здравствуйте, <Аноним>, Вы писали:
А> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
Первая задача — решение линейного уравнения.
Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
Re[2]: Есть два отрезка, как определить, пересекаются ли они
| От: | Аноним |
| Дата: | 12.07.07 10:13 |
| Оценка: |
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, , Вы писали:
А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
А можно кодом? Я как-то сталкивался, но уже забыл. Решение там пару строк, что-то вроде (x1-x2)*(y1-y2).
Re[2]: Есть два отрезка, как определить, пересекаются ли они
| От: | tinytjan |
| Дата: | 12.07.07 10:16 |
| Оценка: |
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, , Вы писали:
А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
Глянь в поиске, было и не раз.
Re: Есть два отрезка, как определить, пересекаются ли они?
| От: | Cruser |
| Дата: | 12.07.07 11:30 |
| Оценка: |
Здравствуйте, Аноним, Вы писали:
А> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
Автор: Cruser
Дата: 01.02.07
Re[2]: Есть два отрезка, как определить, пересекаются ли они
| От: | twisted_mind | |
| Дата: | 12.07.07 11:39 | |
| Оценка: | +1 | |
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, , Вы писали:
А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
На самом деле точку пересечения не нужно находить. Достаточно проверить, что каждый отрезок пересекает прямую, проходящую через второй. А для этого нужно проверить, что концы отрезка лежат в разных полуплоскостях относительно прямой, т.е. подставить концы отрезка в уравнение прямой и проверить, чтобы знаки были различные.
Re[3]: Есть два отрезка, как определить, пересекаются ли они
| От: | Аноним |
| Дата: | 12.07.07 11:53 |
| Оценка: |
Здравствуйте, twisted_mind, Вы писали:
_>Здравствуйте, Lloyd, Вы писали:
L>>Здравствуйте, , Вы писали:
А>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>Первая задача — решение линейного уравнения.
L>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
_>На самом деле точку пересечения не нужно находить. Достаточно проверить, что каждый отрезок пересекает прямую, проходящую через второй. А для этого нужно проверить, что концы отрезка лежат в разных полуплоскостях относительно прямой, т.е. подставить концы отрезка в уравнение прямой и проверить, чтобы знаки были различные.
А концы отрезка нужно подставлять в уравнение какой прямой? Можно кодом, плиз.
Re[3]: Есть два отрезка, как определить, пересекаются ли они
| От: | Аноним |
| Дата: | 12.07.07 12:06 |
| Оценка: |
Здравствуйте, tinytjan, Вы писали:
T>Здравствуйте, Lloyd, Вы писали:
L>>Здравствуйте, , Вы писали:
А>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>Первая задача — решение линейного уравнения.
L>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
T>Глянь в поиске, было и не раз.
уже два часа копаюсь. Вариантов много, но по делу ничего нет . Либо не работает вообще, либо работает так медленно, что лучше бы вообще не работало. Помню, как-то сталкивался с хорошим способом в пару строк, но его уже не помню.
Re[4]: Есть два отрезка, как определить, пересекаются ли они
| От: | _pk_sly |
| Дата: | 12.07.07 12:13 |
| Оценка: |
А> уже два часа копаюсь. Вариантов много, но по делу ничего нет . Либо не работает вообще, либо работает так медленно, что лучше бы вообще не работало. Помню, как-то сталкивался с хорошим способом в пару строк, но его уже не помню.
(hint: скалярное произведение)
Re[4]: Есть два отрезка, как определить, пересекаются ли они
| От: | twisted_mind |
| Дата: | 12.07.07 12:14 |
| Оценка: |
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, twisted_mind, Вы писали:
_>>Здравствуйте, Lloyd, Вы писали:
L>>>Здравствуйте, , Вы писали:
А>>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?
L>>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>>Первая задача — решение линейного уравнения.
L>>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.
_>>На самом деле точку пересечения не нужно находить. Достаточно проверить, что каждый отрезок пересекает прямую, проходящую через второй. А для этого нужно проверить, что концы отрезка лежат в разных полуплоскостях относительно прямой, т.е. подставить концы отрезка в уравнение прямой и проверить, чтобы знаки были различные.
А> А концы отрезка нужно подставлять в уравнение какой прямой? Можно кодом, плиз.
Первый отрезок в уравнение прямой для второго, а второй — для первого.
double x1, y1, x2, y2; // первый отрезок double x3, y3, x4, y4; // второй отрезок double A1 = y2 - y1; double B1 = x1 - x2; double C1 = - A1 * x1 - B1 * y1; double A2 = y4 - y3; double B2 = x3 - x4; double C2 = -A2 * x3 - B2 * y3; double f1 = A1 * x3 + B1 * y3 + C1; double f2 = A1 * x4 + B1 * y4 + C1; double f3 = A2 * x1 + B2 * y1 + C2; double f4 = A2 * x2 + B2 * y2 + C2; bool intersect = (f1 * f2 < 0 && f3 * f4 < 0); // строгое пересечение или bool intersect = (f1 * f2 // с учетом касания (так на самом деле нельзя, нужно сравнивать с учетом погрешности, но я так написал для ясности)Re[5]: Есть два отрезка, как определить, пересекаются ли они
| От: | Аноним |
| Дата: | 12.07.07 14:04 |
| Оценка: |
Здравствуйте, twisted_mind, Вы писали:
_>Здравствуйте, Аноним, Вы писали:
_>Первый отрезок в уравнение прямой для второго, а второй — для первого.
_>
_>double x1, y1, x2, y2; // первый отрезок _>double x3, y3, x4, y4; // второй отрезок _>double A1 = y2 - y1; _>double B1 = x1 - x2; _>double C1 = - A1 * x1 - B1 * y1; _>double A2 = y4 - y3; _>double B2 = x3 - x4; _>double C2 = -A2 * x3 - B2 * y3; _>double f1 = A1 * x3 + B1 * y3 + C1; _>double f2 = A1 * x4 + B1 * y4 + C1; _>double f3 = A2 * x1 + B2 * y1 + C2; _>double f4 = A2 * x2 + B2 * y2 + C2; _>bool intersect = (f1 * f2 < 0 && f3 * f4 < 0); // строгое пересечение _>или _>bool intersect = (f1 * f2 // с учетом касания (так на самом деле нельзя, нужно сравнивать с учетом погрешности, но я так написал для ясности) _>Алгоритм неверный . Мне нужен вариант с учетом касания, так как у большинства отрезков длинна равна 2 пикселям. А набор отрезков (84,63), (85,63) и (94,63),(95,63) выдает true, хотя это не так.
Re[6]: Есть два отрезка, как определить, пересекаются ли они
| От: | twisted_mind |
| Дата: | 12.07.07 14:50 |
| Оценка: |
А> Алгоритм неверный . Мне нужен вариант с учетом касания, так как у большинства отрезков длинна равна 2 пикселям. А набор отрезков (84,63), (85,63) и (94,63),(95,63) выдает true, хотя это не так.
Тогда, конечно, не работает, когда все 4 точки лежат на одной прямой.
А случай, когда пересекаются не в одной точке, а по отрезку, что должен давать? Если тоже true, могу предложить такой вариант:
double sqr(double x) < return x * x; > . if (f1 == 0 && f2 == 0 && f3 == 0 && f4 == 0) < double l1 = sqrt(sqr(x1 - x2) + sqr(y1 - y2)); double l2 = sqrt(sqr(x3 - x4) + sqr(y3 - y4)); return sqr((x1 + x2) - (x3 + x4)) + sqr((y1 + y2) - (y3 + y4))
Т.е. сравниваем расстояние между серединами отрезков с суммой половин их длин (только двойки сократились).
Re[7]: Поправка
| От: | twisted_mind |
| Дата: | 12.07.07 15:16 |
| Оценка: |