Пересечение отрезка линии XNA?

Question

Допустим, у нас 4 Vector2 (да, это 2d), поэтому у нас есть lineOneStart, lineOneEnd, lineTwoStart и lineTwoEnd.

Как я могу определить, пересекаются ли 2 линии?Мне все равно, где они пересекаются, я просто хочу знать, пересекаются ли они.

Answer 1

Проверьте эту формулу по Бурк .

Мне недавно тоже пришлось решить эту проблему. Другой вариант - использовать (получить) уравнение линии (y = mx + c), но есть несколько крайних случаев, которые вам необходимо учитывать, а также фактически проверить, находится ли точка пересечения внутри отрезка. Формула в ссылке выше работает, хотя я не могу прокомментировать, как уравнение перестроено, все, что я скажу, это работает;)

Редактировать

Как упомянул AndiDog, другой сайт, который я использовал (пример тоже отличный), это учебник . Поскольку это XNA, вторая ссылка будет прямо на вашей улице.

Редактировать (Контент по неработающей ссылке) :

Уравнения линий: Pa = P1 + ua ( P2 - P1 ) и Pb = P3 + ub ( P4 - P3 )

Решение для точки, где Pa = Pb дает следующие два уравнения с двумя неизвестными (ua и ub) x1 + ua (x2 - x1) = x3 + ub (x4 - x3) а также y1 + ua (y2 - y1) = y3 + ub (y4 - y3) Решение дает следующие выражения для ua и ub

Подстановка любого из них в соответствующее уравнение для линии дает точку пересечения. Например, точка пересечения (x, y) x = x1 + ua (x2 - x1) y = y1 + ua (y2 - y1)

Примечания: Знаменатели для уравнений для ua и ub одинаковы. Если знаменатель для уравнений для ua и ub равен 0, то две прямые параллельны. Если знаменатель и числитель для уравнений для ua и ub равны 0, тогда эти две линии совпадают. Уравнения применимы к линиям, если требуется пересечение отрезков, то нужно только проверить, лежат ли значения ua и ub между 0 и 1. Какой из этих диапазонов находится в этом диапазоне, то соответствующий отрезок содержит точку пересечения. Если оба лежат в диапазоне от 0 до 1, то точка пересечения находится в обоих отрезках.

Answer 2

На эту тему есть учебник (пересечение отрезков).

Answer 3

Для полноты я приведу ниже алгоритм, когда линии представлены в (a,b,c) координатах, так что уравнение для линии будет a*x+b*y+c=0.

• Две линии с координатами (a1,b1,c1) и (a2,b2,c2) пересекаются в точке (x,y)

• Найти однородные координаты точки как

  u = b1*c2-b2*c1;
  v = a2*c1-a1*c2;
  w = a1*b2-a2*b1;
  

• Если линии параллельны, то w=0.

• В противном случае точка пересечения находится в

  x = u/w;
  y = v/w;
  

Приложение

• Чтобы определить линию (a,b,c) через две точки (x1,y1) и (x2,y2), используйте

  a= y1-y2;
  b= x2-x1;
  c= x1*y2-y1*x2;
  

• Чтобы определить линию (a,b,c) через точку (x,y) с полярным направлением (cos(θ),sin(θ))

  a= -sin(θ);
  b=  cos(θ);
  c= x*sin(θ)-y*cos(θ);