Вопрос № 71413: Здравствуйте, как решить такую задачу:
Проверить или пересекаются два отрезка заданных координатами своих концов?
..
Вопрос № 71.413
Здравствуйте, как решить такую задачу:
Проверить или пересекаются два отрезка заданных координатами своих концов?
Отправлен: 17.01.2007, 20:22
Вопрос задал: ataman (статус: 2-ой класс)
Всего ответов: 3 Мини-форум вопроса >>> (сообщений: 3)
Отвечает: Troyan
Здравствуйте, ataman!
Прямую линию по координатам ее концов (допустим w b u) можно определить следующим уравнением: A*x+B*y+C=0, где A=u.y-w.y, B=w.x-u.x, C=-(u.x*(u.y-w.y)+u.y*(w.x-u.x))
Все остальное в приложении. Если возникнут проблемы, то попробуйте сделать процедуру сравнения для вещественных числе (в паскале она не всегда правильно работает)
Приложение:
--------- Кто к нам с чем за чем от того и того!
Ответ отправил: Troyan (статус: 5-ый класс)
Ответ отправлен: 17.01.2007, 20:45
Отвечает: fsl
Здравствуйте, ataman!
Ур-ние прямой, проходящей через точки (х1,у1) и (х2,у2) находим по формуле
у= ах + b,
где
а = (у2 - у1)/(х2 - х1)
b = у1 - (у2 - у1)/(х2 - х1)*х1
Если х1=х2, то уравнение прямой х = х1.
Вычисляете это все для каждой пары точек (с проверкой)
И так имеем два ур-ния
у= а1х + b1
и
у= а2х + b2
Далее если а1=а2, то прямые параллельны, если нет, то прямые пересекаются.
Если обе прямые представлены ввиде х = k и х=m, то прямые также параллельны,
если ли же только одна, то прямые пересекаются.
Если будут сложности с кодом, пишите в личку, помогу.
Удачи!
--------- Ну, Вы спросили!
Ответ отправил: fsl (статус: Студент)
Ответ отправлен: 18.01.2007, 09:22
Отвечает: Сухомлин Кирилл Владимирович
Здравствуйте, ataman!
Удобней всего записать уравнения прямых, содержащих эти отрезки в параметрической форме:
1-ая прямая проходит из (x1; y1) в (x2; y2)
2-ая прямая проходит из (x3; y3) в (x4; y4)
Уравнения прямых:
{ x = x1 + (x2-x1)*t
{ y = y1 + (y2-y1)*t
и, соответственно,
{ x = x3 + (x4-x3)*s
{ y = y3 + (y4-y3)*s
{ (x2-x1)*t + (x3-x4)*s = -(x3 + x1)
{ (y2-y1)*t + (y3-y4)*s = -(y3 + y1)
Решается такая система уравнений тривиально.
Например, через детерминанты.
Далее, если решения не существует, значит, даже прямые, содержащие исхлодные отрезки, не пересекаются — они параллельны.
Если решение есть, то отрезки пересекаются тогда и только тогда, когда
0 <= t, s <= 1
Все.
