|
Пусть (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. Это уж сами придумайте как сделать, там ничего принципиально сложного.
|
