Взаимное расположение двух отрезков

Отрезки на плоскости заданы координатами своих концевых точек, необходимо определить взаимное располо­жение двух отрезков.

Предположим, что концевые точки одного из отрезков имеют координаты (х₁,у₁) и (х₂,у₂), а концевые точки другого — (х₃;у₃) и (х₄;у₄). Пусть общее уравнение первой прямой, проходя­щей через точки (х₁,у₁) и (х₂,у₂) имеет вид А₁x + B₁y+C₁ = 0, а уравнение второй прямой, проходящей через точки (х₃;у₃) и (х₄;у₄), выглядит так: А₂x + B₂y+C₂ = 0,

Определим расположение точек (х₃;у₃) и (х₄;у₄) относительно первой прямой. Если они расположены по одну сторону от прямой, то отрезки не могут пересекать­ся. Аналогично можно определить положение точек (х₁,у₁) и (х₂,у₂) относительно другой прямой.

Таким образом,
отрезки пересекаются, если значения пары выражений Z₁=А₁x₃ + B₁y₃+C₁ и Z₂=А₁x₄ + B₁y₄+C₁ разные знаки или Z₁*Z₂=0, а также пары Z₃= А₂x₁+ B₂y₁+C₂ и Z₄= А₂x₂+ B₂y₂+C₂ имеют разные знаки или Z₃*Z₄=0.

отрезки не пересекаются, если значения пар выражений Z₁ и Z₂ или Z₃ и Z₄ имеют одинаковые знаки.

Приведенный выше алгоритм не учитывает крайней ситуации, когда два отрезка лежат на одной прямой:

(x₃-x₁)(y₂-y₁)-(y₃-y₁)(x₂-x₁)=0 и (x₄-x₁)(y₂-y₁)-(y₄-y₁)(x₂-x₁)=0

На рис.4 отрезки, лежащие на одной прямой, не пересекаются, а на рис. 5 — пересекаются.

Для того чтобы определить взаимное расположение таких отрезков, поступим следующим образом. Обозначим k₁ = min (x₁; х₂); k₂ = max(x₁; x₂); k₃ = min(x₃; x₄); k₄ = max(x₃; x₄).

Здесь k₁ является левой, a k₂ — правой точкой проекции первого отрезка (отрезка, заданного координатами (x₁;y₁), (x₂; у₂)) на ось Ох. Аналогично k₃ является левой, и k₄ — правой точкой проекции второго отрезка (отрезка, заданного координатами (x₃;y₃), (x₄; у₄)) на ось Ох. Ана­логично ищем проекции на ось Оу.

Отрезки, лежащие на одной прямой, будут пере­секаться тогда, когда их проекции на каждую ось пересекаются. Следует заметить, что если проек­ции двух произвольных отрезков пересекаются, то это не значит, что и сами отрезки пересека­ются, что видно на ри­сунке.

Для определения взаимного расположения проекций на ось Ох воспользуемся следующим фактом (см. рис. 4 и 5): координата левой точки пересечения проекций Lx равна max(k₁; k₃), т. е. максимальной из координат левых точек проекций. Рассуждая аналогично для пра­вых точек проекций, получим, что координата правой точки Rx пересечения равна min (k₂, k₄). Для того чтобы отрезки пересекались, необходимо, чтобы левая коорди­ната пересечения проекций была не больше правой координаты пересечения отрезков (такой случай имеет место на рис. 4, когда Lx = x₃, a Rx = x₂). Поэтому услови­ем пересечения проекций является выполнение нера­венства Lx<=Rx.

Аналогично можно вычислить величины Ly и Ry, взяв соответствующие проекции на ось Оу.

Следует отметить, что длина пересечения проекций в этом случае равна величине Rx — Lx (если Rx — Lx = 0, то проекции имеют только общую точку).