Определение, пересекаются ли два отрезка?

Question

Возможный дубликат:
Как определить, где пересекаются два отрезка?

Может ли кто-нибудь предоставить алгоритм или код C для определения, пересекаются ли два отрезка?

Answer 1

Это действительно зависит от того, как линии представлены. Я собираюсь предположить, что они представлены в параметрической форме.

x₀(t) = u₀ + t v₀

x₁(t) = u₁ + t v₁

Здесь x's, u' s и v's являются векторами (далее обозначены жирным шрифтом) в ℜ² и t ∈ [0, 1].

Эти две точки пересекаются, если есть некоторая точка, которая находится на обоих этих отрезках. Таким образом, если есть некоторая точка р, так что там, где

p = x₀(t) = u₀ + t v₀

и такой, что

p = x₁(s) = u₁ + s v₁

Причем оба s, t ∈ [0, 1], тогда две прямые пересекаются. Иначе они этого не делают.

Если мы объединим два равенства, мы получим

u₀ + t v₀ = u₁ + s v₁

Или, что эквивалентно,

u₀ - u₁ = s v₁ - t v₀

и₀ = (х₀₀, у₀₀)

u₁ = (х₁₀, у₁₀)

v₀ = (х₀₁, у₀₁)

v₁ = (х₁₁, у₁₁)

Если мы переписываем вышеприведенное выражение в матричной форме, то теперь имеем

| x00 - x10 |   | x11 |      | x01 |
| y00 - y10 | = | y11 | s -  | y01 | t

Это в свою очередь эквивалентно матричному выражению

| x00 - x10 |   | x11  x01 | | s|
| y00 - y10 | = | y11  y01 | |-t|

Теперь у нас есть два случая для рассмотрения. Во-первых, если эта левая часть является нулевым вектором, то существует тривиальное решение - просто установите s = t = 0 и точки пересекаются. В противном случае, есть единственное решение, только если правая матрица обратима. Если мы позволим

        | x11  x01 |
d = det(| y11  y01 |) = x11 y01 - x01 y11

Тогда обратная матрица

| x11  x01 |
| y11  y01 |

дан кем-то

      |  y01   -x01 |
(1/d) | -y11    x11 |

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

Если матрица обратима, то мы можем решить вышеуказанную линейную систему, умножив влево на эту матрицу:

 | s|         |  y01   -x01 | | x00 - x10 |
 |-t| = (1/d) | -y11    x11 | | y00 - y10 |

              |  (x00 - x10) y01 - (y00 - y10) x01 |
      = (1/d) | -(x00 - x10) y11 + (y00 - y10) x11 |

Так что это означает, что

s = (1/d)  ((x00 - x10) y01 - (y00 - y10) x01)
t = (1/d) -(-(x00 - x10) y11 + (y00 - y10) x11)

Если оба эти значения находятся в диапазоне [0, 1], тогда два отрезка пересекаются, и вы можете вычислить точку пересечения. В противном случае они не пересекаются. Кроме того, если d равно нулю, тогда эти две линии параллельны, что может представлять интерес для вас. Кодирование этого в C не должно быть слишком плохим; вам просто нужно быть осторожным, чтобы не делить на ноль.

Надеюсь это поможет! Если кто-нибудь может перепроверить математику, это было бы здорово.

Answer 2

Вы можете построить уравнение для двух прямых, найти точку пересечения и затем проверить, принадлежит ли оно этим отрезкам.