2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 алгоритм пересечения двух произвольных отрезков прямых
Сообщение03.02.2006, 16:05 
заданных координатами...
помогите найти сабж? :roll:

 
 
 
 
Сообщение03.02.2006, 16:12 
Аватара пользователя
а в чем вопрос?

 
 
 
 
Сообщение03.02.2006, 16:23 
найти точку пересечения если таковая есть, но чтобы работало и с параллельными и во всех случаях... все встреченные примеры были не универсальны

 
 
 
 
Сообщение03.02.2006, 16:27 
Аватара пользователя
на плоскости?

 
 
 
 
Сообщение03.02.2006, 16:36 
ага... :roll:
ато как программер совсем математику забыл

 
 
 
 
Сообщение03.02.2006, 16:40 
Аватара пользователя
Пусть (ax,ay), (bx,by) - концы одного отрезка, (cx,cy) и (dx,dy) - концы другого.

1. Проверяем, что отрезки не коллинеарны. Для этого нужно, чтобы определитель матрицы, строки которой имеют вид (bx-ax, by-ay) и (dx-cx, dy-cy), был бы ненулевой.

2. Представляем первую прямую в параметрическом виде: x(t) = ax + t*(bx-ax), y(t) = ay + t*(by-ay). Заметим, что отрезок между точками соответствует диапазону изменения t от 0 до 1.

3. Находим число t, для которого точка (x(t),y(t)) попадает на вторую прямую. Для этого нужно приравнять к нулю определитель матрицы, составленной из строк (x(t)-cx , y(t)-cy) и (dx-cx, dy-cy). Получим линейное уравнение на t, откуда находим решение t0.

4. Проверяем, что t0 лежит в диапазоне от 0 до 1. Если нет, то точка пересечения не лежит между A и B.

5. Еще нужно проверить, что точка пересечения лежит на второй прямой между C и D. Это уж сами придумайте как сделать, там ничего принципиально сложного.

 
 
 
 
Сообщение03.02.2006, 16:46 
ой... спасиба, буду разбираться

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group