Определение точки пересечения двух отрезков
Пусть даны два отрезка. Первый задан точками P1(x1;y1) и P2(x2;y2). Второй задан точками P3(x3;y3) и P4(x4;y4).
Взаимное расположение отрезков можно проверить с помощью векторных произведений:
Рассмотрим отрезок P3P4 и точки P1 и P2.
Точка P1 лежит слева от прямой P3P4, для нее векторное произведение v1 > 0, так как векторы положительно ориентированы.
Точка P2 расположена справа от прямой, для нее векторное произведение v2 < 0, так как векторы отрицательно ориентированы.
Для того чтобы точки P1 и P2 лежали по разные стороны от прямой P3P4, достаточно, чтобы выполнялось условие v1v2 < 0(векторные произведения имели противоположные знаки).
Аналогичные рассуждения можно провести для отрезка P1P2 и точек P3 и P4.
Векторное произведение двух векторов вычисляется по формуле:
где:
ax, ay — координаты первого вектора,
bx, by — координаты второго вектора.
Уравнение прямой, проходящей через две различные точки, заданные своими координатами.
Пусть на прямой заданы две не совпадающие точки:P1 с координатами (x1;y1) и P2 с координатами (x2; y2). Соответственно вектор с началом в точке P1 и концом в точке P2 имеет координаты (x2-x1, y2-y1). Если P(x, y) – произвольная точка на прямой, то координаты вектора P1P равны (x — x1, y – y1).
Итак, прямую можно задать уравнением вида (1).
Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:
Здесь D – определитель системы, а Dx,Dy — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0, то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x1=Dx/D, y1=Dy/D, которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
Отрезки
Чтобы понять, лежат ли отрезки на одной прямой, достаточно проверить, что концы одного из них лежат на прямой, задаваемой другим отрезком:
struct segment arraypt, 2> ends; >; // здесь прямую мы задаём 2 точками bool pt::BelongsTo(line& L) pt A = L.pts[0]; pt B = L.pts[1]; pt AB = pt(A, B); pt AP = pt(A, *this); // у вас должен быть написан конструктор pt (pt&, pt&) // векторное произведение return AB % AP == 0; > bool IsSegmentsOnSameLine(segment& s1, segment& s2) line s1_line = line(s1.ends[0], s1.end[1]); for (int i = 0; i 2; ++i) pt s2_end = s2.ends[i]; if (!s2_end.BelongsTo(s1_line)) return false; > > return true; >
Если отрезки лежат на одной прямой, то ответ либо пустой, либо это отрезок, концы которого являются подножеством концов исходных отрезков (убедиться в этом можно, нарисовав все возможные варианты пересечения отрезков на одной прямой).
Получаем такой код пересечения отрезков на одной прямой:
static segment::NoSegment() return segment(pt::NoPt(), pt::NoPt()) >; bool pt::BelongsTo(segment& s) pt A = s.pts[0]; pt B = s.pts[1]; pt AB = pt(A, B); pt BA = pt(B, A) pt AP = pt(A, *this); pt BP = pt(B, *this); // векторное произведение return AB % AP == 0 && BA % BP == 0; > pairbool, segment> IntersectSegmentsOnSameLine(segment& s1, segment& s2) vectorpt> intersection; for (int segment_i = 1; segment_i 2; ++segment_i) segment& cur_s = (segment_i == 1 ? s1 : s2); segment& other_s = (segment_i == 1 ? s2 : s1); for (int i = 0; i 2; ++i) pt& p = cur_s.ends[i]; if (p.BelongsTo(other_s)) intersection.push_back(p); > > > if (intersection.size() == 0) return false, segment::NoSegment()>; // в принципе неважно, что вы тут вернёте вторым аргументом > return true, segment(intersection[0], intersection[1])>; >
Если же отрезки не лежат на одной прямой, то точек пересечения либо 0, либо 1. Первый способ пересечения отрезков который тогда приходит в голову: найти точку пересечения прямых, на которых лежат отрезки и проверить лежит ли эта точка на каждом из отрезков. Однако коль скоро мы работаем с компьютерами, надо держать в голове проблему с точностью, которая наверняка всплывёт как только мы начнём пересекать прямые $\implies$ точка пересечения будет иметь нецелые координаты и проверить её принадлежность каждому из отрезков с абсолютной точностью мы не сможем.
Однако, в случае, когда координаты концов отрезков целочисленные, мы можем наверняка сказать, пересекаются ли отрезки или нет. Для этого должно быть верно следующее: концы каждого из отрезков лежат по разные стороны от прямой, содержащей другой отрезок, либо один из концов отрезков должен лежать на другом отрезке.
Проверку принадлежности точки отрезку мы уже умеем делать, проверять, лежат ли точки по разную сторону от прямой мы тоже умеем.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex
Математика: алгоритм определения пересечения двух отрезков
Так вот, у меня всю жизнь было плохо с математикой и столкнулся с такой проблемой. Есть два отрезка с совершенно рандомными координатами от -10000 до +10000, нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм — не получилось. Видимо, задача тривиальна..
У кого есть идеи или кто сталкивался с таким вопросом, подскажите пожалуйста. От готового решения также не откажусь =) Заранее, спасибо!
24 ответа
17 марта 2009 года
4.5K / / 09.08.2005
нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм — не получилось. Видимо, задача тривиальна..
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно — нужно решить систему уравнений прямых.
17 марта 2009 года
193 / / 03.04.2006
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно — нужно решить систему уравнений прямых.
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.
17 марта 2009 года
527 / / 03.02.2007
Есть такая замечательная книга Френсиса Хилла «OpenGL. Программирование компьютерной графики». В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах.
17 марта 2009 года
2.9K / / 03.08.2007
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.
уравнение прямой y= k*x + b
где k тангенс угла наклона прямой (отношение противолежащего катета к прилежащему, катеты можно легко найти, зная координаты точек отрезка)
b — некая постоянная (то значение Y где прямая пересекает ось OY)
17 марта 2009 года
4.5K / / 09.08.2005
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.
Внимаетельно смотрим на формулы. Там есть ответы на все ваши вопросы.
17 марта 2009 года
309 / / 08.01.2006
Берем канонические уравнения:
таковые легко получить имея две точки прямой (x1, y1, z1), (x2, y2, z2)
где знаменатели дробей соответственно равны m, n и p
Для двух прямых имеем:
m1, n1, p1
m2, n2, p2
Если отношения m1/m2 равно n1/n2 и равно p1/p2, то прямые параллельны, в потивном случае они пересекаются.
Для двумерного случая дробь с координатой z не нужна.
Далее, если прямые не параллельны, находим точку пересечения, решая систему уравнений, как это было сказано тов. hardcase
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно — нужно решить систему уравнений прямых.
17 марта 2009 года
309 / / 08.01.2006
Есть такая замечательная книга Френсиса Хилла «OpenGL. Программирование компьютерной графики». В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах.
Имея такую книгу, могу сказать, что найти её не так просто. На сайте издательства она быват далеко не всегда, не говоря о магазинах.
Я бы посоветовал книгу Дмитрия Письменного «Конспект лекций по высшей математике» ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.
17 марта 2009 года
1.1K / / 01.08.2005
уравнение прямой y= k*x + b
где k тангенс угла наклона прямой
Только такое уравнение не подходит для вертикальных прямых так как у 90 градусов нет тангенса. Ето надо учитывать.
(x-x1) (y-y1) (z-z1)
——= —— = ——
(x2-x1) (y2-y1) (z2-z1)
Ну и тут по сути надо учитывать то же самое. В знаменателе может и 0 получится.
ЗЫ. Также не забудьте что если прямые и паралельни, то отрезки всеровно могут иметь общую точку, а возможно и частично накладываться.
17 марта 2009 года
527 / / 03.02.2007
Имея такую книгу, могу сказать, что найти её не так просто. На сайте издательства она быват далеко не всегда, не говоря о магазинах.
Я бы посоветовал книгу Дмитрия Письменного «Конспект лекций по высшей математике» ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.
Я не говорю о бумажной версии этой книги, я говорю об электронном варианте, который найти в рунете как расплюнуть. 😉 В ней как раз и рассматриваются вопросы по сабжу. Также обсуждаются вопросы и перекрывающихся прямых, и т.д. и т.п. Да и представленные в ней алгоритмы универсальны.
17 марта 2009 года
193 / / 03.04.2006
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.
17 марта 2009 года
1.1K / / 01.08.2005
Тоесть отрезки не на плоскости или в пространстве, а на прямой ?? Ги-ги. Ето же тривиально. Можно написать пару ифов. Типа если начало второго отрезка лежит после начала первого и конец. и так далее. А можно просто взять 4 точки и. Короче примерно так как я писал тут с отрезками времени
17 марта 2009 года
2.5K / / 14.07.2006
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно — ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.
17 марта 2009 года
1.1K / / 01.08.2005
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно — ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.
Да нет там геометрии если я правильно понял. У нево только одна координата Х. Отрезки в одномерном пространстве.
17 марта 2009 года
527 / / 03.02.2007
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.
Вы и не будете искать точку пересечения, если это не надо. Вы найдёте один единственный параметр и если он будет лежать вне интервала [0;1], то отрезки прямых не пересекаются. Короче, читайте, учите, ищите, разбирайтесь. Литературу Вам указали.
21 декабря 2009 года
2 / / 21.12.2009
Пипец, все такие умные, но ничего конкретного человеку так и не предложили. Всё почитай, да поищи, да этоже элементарно. Если элементарно, так напиши.
Короче вот функция на java (с портированием на C я думаю проблем не будет :), определяющая пересекаются ли два отрезка на плоскости:
boolean transection (double ax1, double ay1, double ax2, double ay2, double bx1, double by1, double bx2, double by2)
double v1=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
double v2=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
double v3=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
double v4=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
return ((v1*v2 <=0) && (v3*v4<=0));
>
Функция возвращает true если отрезки A и B пересекаются.
ax1, ay1 — координаты первой точки отрезка A ну и т.д.
Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.
Условия проверки пересечения двух отрезков
Достаточно ли этих трех условий, чтобы утверждать, что точка E является точкой пересечения этих отрезков?
Если недостаточно, напишите, пожалуйста, какие еще необходимо проверить условия, либо другой более правильный метод.
Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 14 апр 2018 в 6:38
Simple User Simple User
141 1 1 золотой знак 3 3 серебряных знака 15 15 бронзовых знаков
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Если при решении системы уравнений учитывается случай параллельных прямых (в таком случае решений нет или их бесконечное количество при совпадении прямых), то этих условий достаточно.
Есть методы проверки факта пересечения, не требующие нахождения самой точки пересечения. Например, алгоритм, который проверяет, что концы одного отрезка лежат по разные стороны от прямой, включающей второй отрезок, и концы второго отрезка лежат по разные стороны от прямой, включающей первый отрезок. При этом сравниваются знаки векторных произведений AB x AC и AB x AD, CD x CA и CD x CB
Отслеживать
ответ дан 14 апр 2018 в 11:28
52.3k 3 3 золотых знака 19 19 серебряных знаков 43 43 бронзовых знака
-
Важное на Мете
Связанные
Похожие
Подписаться на ленту
Лента вопроса
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.1.3.2953
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.