Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.
Спасибо за статью. Я не Ваш студент. Но мне она помогла написать функцию для Канторова множества на Python для черепашки: import turtle def kanter(x, y, d):     if d > 1:         turtle...
Как реализовать в данном примере границы расчёта?

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика



Координаты концов первого отрезка: A(xa, ya), B(xb, yb).
Координаты концов второго отрезка: C(xc, yc), D(xd, yd).

Для начала проверим не пересекаются ли отрезки.
Пусть для отрезка AB: x = t(xb - xa) + xa, y = t(yb - ya) + ya, тогда для CD: x = s(xd - xc) + xc, y = s(yd - yc) + yc, где 0 ≤ t,s ≤ 1.

Если отрезки пересекаются, то выполняются равенства:
t(xb - xa) - s(xd - xc) = xc - xa и t(yb - ya) - s(yd - yc) = yc - ya.

Полученную систему уравнений решим методом Крамера:
Δ = (xb - xa)(yс - yd) - (yb - ya)(xс - xd).
Δ1 = (xb - xa)(yс - ya) - (yb - ya)(xс - xa).
Δ2 = (xc - xa)(yс - yd) - (yc - ya)(xс - xd).

Тогда t = Δ1, s = Δ2/Δ. Если 0 ≤ t,s ≤ 1 и Δ ≠ 0, то отрезки пересекаются и расстояние между ними min равно 0, иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным).

Пусть k и d — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке Z, координаты Z(xz, yz) можно найти по формуле yz = kxz + d. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно 0. Тогда (x2 - x1)(x3 - xz)+(y2 - y1)(y3 - yz) = 0, соответственно xz = (x3x2 - x3x1 + y2y3 - y1y3 + y1d - y2d)/(ky2 - ky1 + x2 - x1), где (x3, y3) — координаты точки, с которой была опущена высота, (x1, y1) и (x2, y2) — координаты концов отрезка, принадлежащего прямой на которую опущена высота.

Вычислим длину dl каждой высоты, основание которой принадлежит одному из данных отрезков: dl = √((x3 - xz)2 + (y3 - kxz - d)2).

Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков: min = √((x1 - x3)2 + (y1 - y3)2), где (x1, y1) — координаты одного из концов первого отрезка, а (x3, y3) — координаты одного из концов второго отрезка.