|
Математика: Вычислительная геометрия:
Пересекаются ?... А если да, то где ?
© Кантор И.
Два отрезка.
(1) Отрезок AB: A(X1, Y1) и B(X2, Y2)
(2) Отрезок CD: C(X3, Y3) и D(X4, Y4)
В этом случае уравнение прямой AB будет F(X, Y) = (X-X1)(Y2-Y1)-(Y-Y1)(X2-X1) = 0.
Если подставить в левую часть вместо X и Y координаты точек С и D, то
левая часть имеет разный знак при подстановке C и D - пересечение есть,
При подстановке одной из точек левая часть равна 0 - эта точка лежит на AB.
Обе точки дают 0 - отрезки лежат на одной прямой - требуется дополнительное исследование ( бывает крайне редко ), 0 только 1 - есть пересечение.
Знаки одинаковы - пересечения нет.
Потом AB и CD меняются местами. Результат выбирается наихудший из двух проверок (пересечения нет - плохо).
![](../../../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации.
| |