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));
}
Математика: алгоритм определения пересечения двух отрезков
Заранее извиняюсь, если ошибся с разделом, но просто пишу на си, поэтому и алгоритм хотел бы на нём =)
Так вот, у меня всю жизнь было плохо с математикой и столкнулся с такой проблемой. Есть два отрезка с совершенно рандомными координатами от -10000 до +10000, нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм - не получилось. Видимо, задача тривиальна..
У кого есть идеи или кто сталкивался с таким вопросом, подскажите пожалуйста. От готового решения также не откажусь =) Заранее, спасибо!
Так вот, у меня всю жизнь было плохо с математикой и столкнулся с такой проблемой. Есть два отрезка с совершенно рандомными координатами от -10000 до +10000, нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм - не получилось. Видимо, задача тривиальна..
У кого есть идеи или кто сталкивался с таким вопросом, подскажите пожалуйста. От готового решения также не откажусь =) Заранее, спасибо!
Цитата: nof
нужно определить пересекаются ли данные отрезки или нет. В интернете пытался найти готовый алгоритм - не получилось. Видимо, задача тривиальна..
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно - нужно решить систему уравнений прямых.
Цитата: hardcase
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно - нужно решить систему уравнений прямых.
Найти пересечение элементарно - нужно решить систему уравнений прямых.
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.
Есть такая замечательная книга Френсиса Хилла "OpenGL. Программирование компьютерной графики". В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах...
Цитата: nof
Это при условие, что у нас есть уравнения описывающие данные отрезки. Но у нас есть только начальные и конечные точки отрезков.
уравнение прямой y= k*x + b
где k тангенс угла наклона прямой (отношение противолежащего катета к прилежащему, катеты можно легко найти, зная координаты точек отрезка)
b - некая постоянная (то значение Y где прямая пересекает ось OY)
Берем канонические уравнения:
таковые легко получить имея две точки прямой (x1, y1, z1), (x2, y2, z2)
(x-x1) (y-y1) (z-z1)
------= ----- = ------
(x2-x1) (y2-y1) (z2-z1)
где знаменатели дробей соответственно равны m, n и p
Для двух прямых имеем:
m1, n1, p1
m2, n2, p2
Если отношения m1/m2 равно n1/n2 и равно p1/p2, то прямые параллельны, в потивном случае они пересекаются.
Для двумерного случая дробь с координатой z не нужна.
Далее, если прямые не параллельны, находим точку пересечения, решая систему уравнений, как это было сказано тов. hardcase
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно - нужно решить систему уравнений прямых.
таковые легко получить имея две точки прямой (x1, y1, z1), (x2, y2, z2)
(x-x1) (y-y1) (z-z1)
------= ----- = ------
(x2-x1) (y2-y1) (z2-z1)
где знаменатели дробей соответственно равны m, n и p
Для двух прямых имеем:
m1, n1, p1
m2, n2, p2
Если отношения m1/m2 равно n1/n2 и равно p1/p2, то прямые параллельны, в потивном случае они пересекаются.
Для двумерного случая дробь с координатой z не нужна.
Далее, если прямые не параллельны, находим точку пересечения, решая систему уравнений, как это было сказано тов. hardcase
Цитата:
Находим точку пересечения двух прямых, и если она есть, проверяем, лежит ли она на обоих отрезках.
Найти пересечение элементарно - нужно решить систему уравнений прямых.
Цитата: SergPas
Есть такая замечательная книга Френсиса Хилла "OpenGL. Программирование компьютерной графики". В ней есть решение задачи определения точки пересечения 2-х отрезков прямой, заданных в параметрической (то что нужно) и/или в точечной нормальной формах...
Имея такую книгу, могу сказать, что найти её не так просто. На сайте издательства она быват далеко не всегда, не говоря о магазинах.
Я бы посоветовал книгу Дмитрия Письменного "Конспект лекций по высшей математике" ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.
Цитата: oxotnik333
уравнение прямой y= k*x + b
где k тангенс угла наклона прямой
где k тангенс угла наклона прямой
Только такое уравнение не подходит для вертикальных прямых так как у 90 градусов нет тангенса. Ето надо учитывать.
Цитата: plastictown
(x-x1) (y-y1) (z-z1)
------= ----- = ------
(x2-x1) (y2-y1) (z2-z1)
Ну и тут по сути надо учитывать то же самое. В знаменателе может и 0 получится.
ЗЫ. Также не забудьте что если прямые и паралельни, то отрезки всеровно могут иметь общую точку, а возможно и частично накладываться.
Цитата: plastictown
Имея такую книгу, могу сказать, что найти её не так просто. На сайте издательства она быват далеко не всегда, не говоря о магазинах.
Я бы посоветовал книгу Дмитрия Письменного "Конспект лекций по высшей математике" ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.
Я бы посоветовал книгу Дмитрия Письменного "Конспект лекций по высшей математике" ( 1-ю часть). Там есть аналитическая геометрия, к которой как раз и относится первоначальный вопрос. К тому же в весьма доступной форме. Да и вообще по аналитической геометрии в недрах паутины материала предостаточно.
Я не говорю о бумажной версии этой книги, я говорю об электронном варианте, который найти в рунете как расплюнуть...;) В ней как раз и рассматриваются вопросы по сабжу... Также обсуждаются вопросы и перекрывающихся прямых, и т.д. и т.п. Да и представленные в ней алгоритмы универсальны...
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.
Тоесть отрезки не на плоскости или в пространстве, а на прямой ?? Ги-ги. Ето же тривиально. Можно написать пару ифов. Типа если начало второго отрезка лежит после начала первого и конец....... и так далее. А можно просто взять 4 точки и.... Короче примерно так как я писал тут с отрезками времени
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно - ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.
Цитата: aks
Блин, автор ну перечитай еще раз что тебе уже посоветовал hardcase. И должно быть стыдно - ибо в данной задаче программирования то особо нету, а есть только школьная геометрия, не более.
Да нет там геометрии если я правильно понял. У нево только одна координата Х. Отрезки в одномерном пространстве.
Цитата: nof
Ребят, извините мою безграмотность + я ещё не начал проверять на практике то, что вы описали, но на глаз: речь ведь идёт об отрезках, а вы все пишите о прямых. Мне не нужно искать точку пересечения прямых, мне нужно знать пересекаются отрезки или нет.
Вы и не будете искать точку пересечения, если это не надо... Вы найдёте один единственный параметр и если он будет лежать вне интервала [0;1], то отрезки прямых не пересекаются. Короче, читайте, учите, ищите, разбирайтесь... Литературу Вам указали...
Пипец, все такие умные, но ничего конкретного человеку так и не предложили. Всё почитай, да поищи, да этоже элементарно. Если элементарно, так напиши.
Короче вот функция на java (с портированием на C я думаю проблем не будет :), определяющая пересекаются ли два отрезка на плоскости:
Функция возвращает true если отрезки A и B пересекаются.
ax1, ay1 - координаты первой точки отрезка A ну и т.д.
Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.
Короче вот функция на java (с портированием на C я думаю проблем не будет :), определяющая пересекаются ли два отрезка на плоскости:
Код:
Функция возвращает true если отрезки A и B пересекаются.
ax1, ay1 - координаты первой точки отрезка A ну и т.д.
Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.
Цитата: Crazy Driver
Пипец, все такие умные, но ничего конкретного человеку так и не предложили. Всё почитай, да поищи, да этоже элементарно. Если элементарно, так напиши.
Ссылка на решение задачи была дана в #6. Автор, кстати, просил хотя бы алгоритм.
Цитата: Crazy Driver
Вот ищу нечто подобное для определения пересекает ли отрезок круг.
Если известны координаты отрезка, координаты центра круга и его радиус.
Решите аналитически систему уравнений:
а) окружности
б) прямой
"Линейка", первый курс.
Если "программист" не в сосотоянии прочитать простые формулы из справочника и/или выполнить тривиальные выкладки, то ему наверняка нужно подыскивать новую специальность.
Это ссылка не на решение задачи, а на статью Википедии о прямой.
И естественно никаких алгоритмов там нет.
Цитата: hardcase
Решите аналитически систему уравнений:
а) окружности
б) прямой
"Линейка", первый курс.
Очень "полезный" совет, никогдаб не догадался.
Цитата: Crazy Driver
Это ссылка не на решение задачи, а на статью Википедии о прямой.
Переходим по ссылке, находим подраздел "Взаимное расположение нескольких прямых на плоскости" и (о чудо!) обнаруживаем там формулу, которую вы записали в своем предыдущем посте. А как найти коэффициенты канонического уравнения? - спросите вы. А очень просто: на той же самой странице есть уравнение прямой проходящей через две заданные точки. Имеющий глаза да узрит решение.
Цитата: Crazy Driver
И естественно никаких алгоритмов там нет.
С каких это пор язык математики перестал выражать суть исполняемых компьютером действий?
Для общего развития: слова алгоритм и арифметика восходят к одному корню.
Цитата: Crazy Driver
Очень "полезный" совет, никогдаб не догадался.
Ну так и вперед! Че, лень пошевелить мозгами, ага?
[quote="некто"]
Зачем тогда вообще отвечать на форуме? Можно просто на все посты давать две ссылки на википедию и на Google
[/quote]
Каков вопрос - таков ответ.
Надеюсь следующие рассуждения помогут в решении задачи:
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.
Цитата:
исходные данные: отрезок AB, радиус R.
А центр окружности разве не нужен? :D
Цитата: grag63
Надеюсь следующие рассуждения помогут в решении задачи:
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.
исходные данные: отрезок AB, радиус R.
Возможные варианты:
1) растояния до точек отрезка < R -> отрезок внутри окружности
2) одно из растояний до отрезка > R, а другое < R -> ответ очевиден
3) AR & BR > R - строим перпендикуляр от центра окружности к отрезку (точка C)
CR > R -> отрезок находится за пределами окружности.
А решить одно квадратное уравнение с одним неизвестным уже не по силам? ;)
А центр окружности разве не нужен?
а как же без него?
И точку С необходимо проверит на принадлежность отрезку, и...
А решить одно квадратное уравнение с одним неизвестным уже не по силам?
Может проще привести уравнение, чем каждый раз отвечать вопросом на вопрос???
а как же без него?
И точку С необходимо проверит на принадлежность отрезку, и...
А решить одно квадратное уравнение с одним неизвестным уже не по силам?
Может проще привести уравнение, чем каждый раз отвечать вопросом на вопрос???
Господин топик-стартер не желает не только решать уравнения уровня третьего класса,
он даже не желает набрать в гугле пересечение отрезков и выбрать из десятков готовых решений...
он даже не желает набрать в гугле пересечение отрезков и выбрать из десятков готовых решений...
Есть готовая функция на C# для нахождения точки пересечения двух отрезков, заданных точками, один из которых горизонтальный или вертикальный, может кому пригодится. http://pastie.org/1819393
Код:
// нахождение точки пересечения отрезка, заданного точками p1 p2 c вертикальным/горизонтальным отрезком, заданным точками p3 p4
public Point Crossing(Point p1, Point p2, Point p3, Point p4)
{
if (p3.X == p4.X) // вертикаль
{
double y = p1.Y + ((p2.Y - p1.Y) * (p3.X - p1.X)) / (p2.X - p1.X);
if (y > Math.Max(p3.Y, p4.Y) || y < Math.Min(p3.Y, p4.Y) || y > Math.Max(p1.Y, p2.Y) || y < Math.Min(p1.Y, p2.Y)) // если за пределами отрезков
return new Point(0, 0);
else
return new Point(p3.X, (int)y);
}
else // горизонталь
{
double x = p1.X + ((p2.X - p1.X) * (p3.Y - p1.Y)) / (p2.Y - p1.Y);
if (x > Math.Max(p3.X, p4.X) || x < Math.Min(p3.X, p4.X) || x > Math.Max(p1.X, p2.X) || x < Math.Min(p1.X, p2.X)) // если за пределами отрезков
return new Point(0, 0);
else
return new Point((int)x, p3.Y);
}
}
public Point Crossing(Point p1, Point p2, Point p3, Point p4)
{
if (p3.X == p4.X) // вертикаль
{
double y = p1.Y + ((p2.Y - p1.Y) * (p3.X - p1.X)) / (p2.X - p1.X);
if (y > Math.Max(p3.Y, p4.Y) || y < Math.Min(p3.Y, p4.Y) || y > Math.Max(p1.Y, p2.Y) || y < Math.Min(p1.Y, p2.Y)) // если за пределами отрезков
return new Point(0, 0);
else
return new Point(p3.X, (int)y);
}
else // горизонталь
{
double x = p1.X + ((p2.X - p1.X) * (p3.Y - p1.Y)) / (p2.Y - p1.Y);
if (x > Math.Max(p3.X, p4.X) || x < Math.Min(p3.X, p4.X) || x > Math.Max(p1.X, p2.X) || x < Math.Min(p1.X, p2.X)) // если за пределами отрезков
return new Point(0, 0);
else
return new Point((int)x, p3.Y);
}
}
Код выше не работает для перпендикулярных отрезков.
Вот пример получения точки пересечения для 2 перпендикулярных отрезков (может кому пригодится):
Вот пример получения точки пересечения для 2 перпендикулярных отрезков (может кому пригодится):
Код:
function getCrossPoint(p1, p2, p3, p4) {
if ( Math.min(p1.x, p2.x) > p3.x || Math.max(p1.x, p2.x) < p3.x
|| Math.min(p3.y, p4.y) > p1.y || Math.max(p3.y, p4.y) < p1.y) {
// не пересекаются
return {x: 0, y: 0};
} else
return {x: p3.x, y: p1.y};
}
if ( Math.min(p1.x, p2.x) > p3.x || Math.max(p1.x, p2.x) < p3.x
|| Math.min(p3.y, p4.y) > p1.y || Math.max(p3.y, p4.y) < p1.y) {
// не пересекаются
return {x: 0, y: 0};
} else
return {x: p3.x, y: p1.y};
}