Ю2.30. Расстояние между отрезками

Задача

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Найти расстояние между двумя между двумя произвольно заданными на плоскости отрезками [latex]AB[/latex] и [latex]CD[/latex].

Входные данные:

Координаты концов первого отрезка [latex]A[/latex] [latex](x_a, y_a)[/latex], [latex]B[/latex] [latex](x_b, y_b)[/latex].
Координаты концов второго отрезка [latex]C[/latex] [latex](x_c, y_c)[/latex], [latex]D[/latex] [latex](x_d, y_d)[/latex].

Выходные данные:

Расстояние между отрезками [latex]min[/latex].

Тесты

 Входные данные  Выходные данные
 № [latex]x_a[/latex] [latex]y_a[/latex] [latex]x_b[/latex] [latex]y_b[/latex] [latex]x_c[/latex] [latex]y_c[/latex] [latex]x_d[/latex] [latex]y_d[/latex] [latex]min[/latex]
 1  1  1  2  1  3  1  4  1  1
 2  0  0  5  5  1  1  2  2  0
 3  0  1  3  3  5  3  6  4  2
 4  0  0  7  0  0  8  5  3  3
 5  5  5  10  10  5  9  6  12  2.8284
 6  2  1  3  5  0  0  0  5  2
 7  -3  0  3  0  0  -3  0  3  0

Код программы

Решение

Для начала проверим не пересекаются ли отрезки. Пусть для отрезка [latex]AB[/latex] [latex]x=t(x_b-x_a)+x_a[/latex], [latex]y=t(y_b-y_a)+y_a[/latex], а для [latex]CD[/latex] [latex]x=s(x_d-x_c)+x_c[/latex], [latex]y=s(y_d-y_c)+y_c[/latex] (где [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex] ). Если отрезки пересекаются, то выполняются равенства: [latex]t(x_b-x_a)-s(x_d-x_c)=x_c-x_a[/latex] и [latex]t(y_b-y_a)-s(y_d-y_c)=y_c-y_a[/latex]. Полученную систему уравнений решим методом Крамера: 
[latex]\Delta =\begin{pmatrix} x_b-x_a & \quad x_c-x_d \\ y_b-y_a & \quad y_c-y_d \end{pmatrix}=(x_b-x_a)(y_c-y_d)-(y_b-y_a)(x_c-x_d)[/latex] [latex]\Delta _1=\begin{pmatrix} x_{ b }-x_{ a } & \quad x_{ c }-x_{ a } \\ y_{ b }-y_{ a } & \quad y_{ c }-y_{ a } \end{pmatrix}=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a)[/latex] [latex]\Delta _2=\begin{pmatrix} x_{ c }-x_{ a } & \quad x_{ c }-x_{ d } \\ y_{ c }-y_{ a } & \quad y_{ c }-y_{ d } \end{pmatrix}=(y_c-y_d)(x_c-x_a)-(x_c-x_d)(y_c-y_a)[/latex].
Тогда [latex]t=\frac { \Delta_1 }{ \Delta } [/latex], а [latex]s=\frac { \Delta_2 }{ \Delta } [/latex]. Если [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex], а [latex]\Delta \neq 0[/latex], то отрезки пересекаются и расстояние между ними [latex]min[/latex] равно [latex]0[/latex], иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным). Пусть [latex]k[/latex] и [latex]d[/latex] — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке  [latex]Z[/latex], координаты [latex]Z[/latex] [latex](x_z, y_z)[/latex] можно найти по формуле [latex]y_z=kx_z+d[/latex]. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно [latex]0[/latex]. Тогда [latex](x_2-x_1)(x_3-x_z)+(y_2-y_1)(y_3-y_z)=0[/latex], соответственно [latex]x_z=\frac { x_3x_2-x_3x_1+y_2y_3-y_1y_3+y_1d-y_2d }{ ky_2-ky_1+x_2-x_1 } [/latex] (где [latex](x_3, y_3)[/latex] — координаты точки, с которой была опущена высота, [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] — координаты концов отрезка, принадлежащего прямой на которую опущена высота). Вычислим длину [latex]dl[/latex] каждой высоты, основание которой принадлежит одному из данных отрезков: [latex]dl=\sqrt { {(x_3-x_z)}^{2}+{(y_3-x_zk-d)}^{2} }[/latex](где [latex] (x_3, y_3)[/latex] — координаты точки, с которой была опущена высота). Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков [latex]min=\sqrt { {( x_1-x_3) }^{ 2 }+{ (y_1-y_3) }^{ 2 } }[/latex] (где [latex](x_1, y_1)[/latex] — координаты одного из концов первого отрезка, а [latex](x_3, y_3)[/latex] — координаты одного из концов второго отрезка) .

Ссылки

Related Images:

3 thoughts on “Ю2.30. Расстояние между отрезками

  1. — Вы пишите «найдём неизвестные уравнений», лучше «найдём коэффициенты уравнений». А вообще переход к такой форме записи идея не самая удачная. Сразу появляется куча кода для обработки нулей в знаменателях для вертикальных прямых. Лучше использовать параметрическую форму записи отрезков. Тогда и легче определить принадлежность точки пересечения отрезкам.
    — Не очень удачные обозначения. Лучше обозначить отрезки [latex]\left[AB\right][/latex] и [latex]\left[CD\right][/latex]. Тогда координаты точек естественно будет обозначить [latex]A\left(x_a,y_a\right),[/latex] [latex]B\left(x_b,y_b\right),[/latex] [latex]C\left(x_c,y_c\right)[/latex] и [latex]D\left(x_d,y_d\right).[/latex]

    • Спасибо. Постарался всё исправить. Избежал случаи с нулём в знаменателе.

    • Зачёл.
      Длинный код с логическими повторами, который сложно анализировать. Лечится использованием вспомогательных функций. Точно нужна функция для вычисления кратчайшего расстояния от точки до отрезка и просто расстояние между двумя точками.
      Если будет свободное время попробуйте сделать еще один вариант кода. Если разместить здесь оба варианта кода, то станет очевидна разница в размере и читаемости.

Добавить комментарий