Mif 9. Пересечение отрезков

Задача

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.

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

Координаты концов отрезка[latex]AB[/latex] и [latex]CD[/latex].

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

Пересекаются ли отрезки.

Тесты

Входные данные Выходные данные
[latex]x1[/latex] [latex]y1[/latex] [latex]x2[/latex] [latex]y2[/latex] [latex]x3[/latex] [latex]y3[/latex] [latex]x4[/latex] [latex]y4[/latex]
1 0 2 1 1 0 2 0 Отрезки пересекаются
-1 1 2 -2 0 -2 1 3 Отрезки пересекаются
1 1 2 2 2 2 1 1 Отрезки пересекаются
-1 1 -1 2 1 1 2 2 Отрезки не пересекаются
-2 -1 -2 3 0 -1 0 3 Отрезки не пересекаются
-2 0 0 2 0 -2 1 1 Отрезки не пересекаются

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

Решение

Пусть концы отрезков имеют координаты [latex](x1,y1),[/latex] [latex](x2,y2),[/latex] [latex](x3,y3),[/latex] и [latex](x4,y4),[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=ux1+(1−u)x2; \newline y=uy1+(1−u)y2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx3+(1−v)x4 \newline y=vy3+(1−v)y4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux1+(1−u)x2=vx3+(1−v)x4 \newline uy1+(1−u)y2=vy3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y4-y3)\cdot(x1-x2)-(x4-x3)\cdot(y1-y2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x4-x2)\cdot(y4-y3)-(x4-x3)\cdot(y4-y2)}{denominator} \newline Ub=\frac{(x1−x2)\cdot(y4−y2)−(x4−x2)\cdot(y1−y2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone

12 thoughts on “Mif 9. Пересечение отрезков

  1. Так, у меня нет сейчас карандаша и бумаги. Я прямо здесь поразмышляю, можно?
    Зададим первый отрезок параметрически с параметром [latex]0 \leq u \leq 1[/latex]:[latex]\left.\begin{matrix}
    x=ux_1+(1-u)x_2\\
    y=uy_1+(1-u)y_2
    \end{matrix}\right\}
    [/latex]
    Зададим второй отрезок параметрически с параметром [latex]0 \leq v \leq 1[/latex]:[latex]\left.\begin{matrix}
    x=vx_3+(1-v)x_4\\
    y=vy_3+(1-v)y_4
    \end{matrix}\right\}
    [/latex]
    В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v[/latex]:
    [latex]\left.\begin{matrix}
    ux_1+(1-u)x_2=vx_3+(1-v)x_4\\
    uy_1+(1-u)y_2=vy_3+(1-v)y_4
    \end{matrix}\right\}[/latex]
    Пока всё логично? Тогда перепишем всё в общепринятом виде:
    [latex]\left.\begin{matrix}
    (x_1-x_2)u+(x_4-x_3)v=x_4-x_2\\
    (y_1-y_2)u-v(y_4-y_3)=y_4-y_2
    \end{matrix}\right\}[/latex]
    Теперь найдем определитель: [latex]D=(x_1-x_2)(y_4-y_3)-(x_4-x_3)(y_1-y_2)[/latex]. Если он равен 0, то прямые содержащие отрезки параллельны. Этот случай нужно рассмотреть отдельно.
    Если не 0, то найдем решение по правилу Крамера:
    [latex]\left.\begin{matrix}
    u=\frac{(x_4-x_2)(y_4-y_3)-(x_4-x_3)(y_4-y_2)}{D}\\
    v=\frac{(x_1-x_2)(y_4-y_2)-(x_4-x_2)(y_1-y_2)}{D}
    \end{matrix}\right\}[/latex]
    Если оба результата не уходят меньше чем 0 или больше 1, то точка пересечения находится внутри отрезков. Иначе пересечения нет.
    Кажется так.
    Теперь просьба к Вам. Проверьте мои рассуждения и скажите, выдаёт ли Ваша программа такой же ответ.
    Вроде да. А зачем тогда swap() в коде?

  2. Вы не обратили внимание на текст «Если он равен 0, то прямые содержащие отрезки параллельны. Этот случай нужно рассмотреть отдельно.»
    Отрезки в этом случае могут иметь общие точки (пересекаться и даже совпадать) или не пересекаться. Этот случай нужно действительно рассмотреть отдельно, а не просто «не пересекаются» и все.
    Посмотрите , например, вариант
    0 0 0 2
    0 1 0 3

      • Не бросайте задачу — мы уже очень близки к финишу 🙂
        — Не нужно четыре условных оператора для случая нулевого определителя. Нужен один со сложным условием с союзом «или» — ||
        — Нельзя извлекать корень и сравнивать на равенство. Из-за ошибок округления может возникнуть «ложно отрицательное» срабатывание.
        — Как проверить проще? Вы ведь уже знаете, что все 4 точки лежат на одной прямой! Значит «между» будет выполняться для обоих координат.
        — Корректорское замечание. После текста «Пусть концы отрезков имеют координаты…» напишите буквы A. B, C, D перед каждой скобкой, чтобы ясно было где чьи координаты.
        — И еще одно. «Ссылки Ideone.» Не очень понятно. Лучше написать что-то вроде «Выполнить программу».

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