it-swarm-ru.tech

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

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

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

11
user420878

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

x (t) = u + t v

x1 (t) = u1 + t v1

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

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

p = x (t) = u + t v

и такой, что

p = x1 (s) = u1 + s v1

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

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

ты + t v = ты1 + s v1

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

ты - ты1 = s v1 - t v

ты = (х00, у00)

ты1 = (х10, у10)

v = (х01, у01)

v1 = (х11, у11)

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

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

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

94
templatetypedef

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

0
gor