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

by

16

Задача

Пересекаются ли отрезки. Для двух отрезков [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 Отрезки не пересекаются

Код программы на C++

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

Решение

Пусть концы отрезков имеют координаты [latex]A(x_1,y_1)[/latex], [latex]B(x_2,y_2)[/latex], [latex]C(x_3,y_3)[/latex] и [latex]D(x_4,y_4)[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=u x_1+(1−u)x_2; \newline y=uy_1+(1−u)y_2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx_3+(1−v)x_4 \newline y=vy_3+(1−v)y_4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux_1+(1−u)x_2=vx_3+(1−v)x_4 \newline uy_1+(1−u)y_2=vy_3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y_4-y_3)\cdot(x_1-x_2)-(x_4-x_3)\cdot(y_1-y_2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x_4-x_2)\cdot(y_4-y_3)-(x_4-x_3)\cdot(y_4-y_2)}{denominator} \newline Ub=\frac{(x_1−x_2)\cdot(y_4−y_2)−(x_4−x_2)\cdot(y_1−y_2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone C++
Ideone Java

Related Images:

16 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() в коде?

    • Здравствуйте, Игорь Евгеньевич. Спасибо что не теряете веру в меня и за Ваше внимание. Функция swap () нужна по причине описанной в решении «Поскольку данная формула работает только для горизонтальных отрезков, в случае когда отрезок вертикален мы его перевернем.»

    • Игорь Евгеньевич, подскажите, пожалуйста, что мне делать с этой задачей, а именно: что мне конкретно в ней исправлять?

    • Исправил, Игорь Евгеньевич. Программа не работала из-за ошибки в формуле.

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

    • Исправил, Игорь Евгеньевич. Сделал проверку при denominator = 0.

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

  7. Как я понял, программа должна проверять, пересекаются ли отрезки. Уточняю, отрезки, а не прямые. Тогда почему при использовании данной программы (которая под с++) если отрезки лежать на одной прямой, но не пересекаются (для примера я взял первый отрезок с координатами x1 = 10, y1 = 10, x2 = 20, y2 = 10 и второй отрезок с координатами x3 = 30, y3 = 10, x4 = 40, y4= 10) то программа выдаёт, что они пересекаются, хотя по факту они не пересекаются.

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