Вопрос № 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
Все.
* Код программы, выдержки из закона и т.п. дополнение к вопросу.
Эта информация будет отображена в аналогичном окне как есть.
Обратите внимание!
Вопрос будет отправлен всем экспертам данной рассылки!
Для того, чтобы отправить вопрос выбранным экспертам этой рассылки или
экспертам другой рассылки портала RusFAQ.ru, зайдите непосредственно на RusFAQ.ru.
Форма НЕ работает в почтовых программах The BAT! и MS Outlook (кроме версии 2003+)!
Чтобы отправить вопрос, откройте это письмо в браузере или зайдите на сайт RusFAQ.ru.
