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

Вход на сайт

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

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

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

Не получается, емаё
огромное спасибо за подробное объяснение про 3д графику на питоне, в интернете очень мало подобной информации
dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(
У Вас число превысит максимальное число int. Можно использовать в Вашем случае uint, но лучше все переписать на double.

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

Рейтинг@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) — координаты одного из концов второго отрезка.