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

Question

Можно создать дубликат:
How do you detect where two line segments intersect?

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

Answer 1

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

Answer 2

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

х (т) = у + т v

x (t) = u + T v

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

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

р = х (Т) = у + T v

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

р = х (ы) = у + з v

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

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

˙U + т v = ˙U + s v

Или, что то же самое,

у - у = S v - т v

у = (x , у)

у = (х , у)

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 | 

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

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

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

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