Определение пересечения двух сегментов линии?

Ответ 1

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

x ₀ (t) = u ₀ + t v _{0суб >}

x ₁ (t) = u ₁ + t v _{1суб >}

Здесь x, u и v - векторы (далее выделены жирным шрифтом) в & real; ² и t & in; [0, 1].

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

p= x ₀ (t) = u ₀ + t v <суб > 0суб >

и a s такие, что

p= x ₁ (s) = u ₁ + s v <суб > 1суб >

И, кроме того, оба s, t & in; [0, 1], то две линии пересекаются. В противном случае они этого не делают.

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

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

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

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

u ₀= (x ₀₀, y ₀₀)

u ₁= (x ₁₀, y ₁₀)

v ₀= (x ₀₁, y ₀₁)

v ₁= (x ₁₁, y ₁₁)

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

| 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 не должно быть слишком плохим; вам просто нужно быть осторожным, чтобы не делиться на ноль.

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

Ответ 2

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