Кто-то, пожалуйста, объясните эту функцию проверки пересечения

Question

Я просматриваю несколько функций, предоставляемых в классе геометрии, и я нашел эту очень плохо прокомментированную функцию, которая, по-видимому, проверяет, есть ли пересечение между двумя строками. Может кто-нибудь объяснить мне, как это работает?

inline bool LineIntersection2D(Vector2D A, 
           Vector2D B, 
           Vector2D C, 
           Vector2D D) 
{ 
    double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y); 
    double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y); 

    double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x); 

    if (Bot == 0)//parallel 
    { 
     return false; 
    } 

    double invBot = 1.0/Bot; 
    double r = rTop * invBot; 
    double s = sTop * invBot; 

    if((r > 0) && (r < 1) && (s > 0) && (s < 1)) 
    { 
     //lines intersect 
     return true; 
    } 

//lines do not intersect 
return false; 
} 

Из того, что я собрал, А и В являются две точки первой линии и С и D являются две точки второго. После этого я полностью потерялся. Заранее спасибо!

Answer 1

Сначала можно определить некоторые векторы. Пусть u = B - A, v = D - C и w = A - C. Первые строки

double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y); 
double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y); 
double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x); 

переводит

rtop = v X w 
stop = u X w 
bot = u X v 

Здесь u X v является 2D версия кросс-продукт, который дает подписанную площадь параллелограмма с ребрами u, v.

Давайте предположим, что существует некоторая точка Р пересечения, и мы можем написать

P = r u + A. 

Параметр г будет находиться в диапазоне от 0 до 1, чтобы дать отрезок. Мы можем также написать

P = s v + C 

мы можем установить эти равны друг другу

r u + A = s v + C 

и вычитать C

r u + A - C = s v 

или

r u + w = s v 

это векторное уравнение 2D в двух переменных r и s. Мы можем исключить либо r, либо s, взяв перекрестное произведение с u или v как u X u = 0.

r u X u + w X u = s v X u 

так

w X u = s v X u 

и

s = (w X u)/(v X u) 

аналогично с перекрестной продукт с v устраняет с.

r u X v + w X v = s v X v 
r u X v + w X v = 0 
r = - (w X v)/(u X v) 
r = (v X w)/ (u X v) 

В любом месте есть знак, но я надеюсь, что это даст суть.

Оба значения r и s должны находиться в пределах от 0 до 1, чтобы точка пересечения лежала на сегментах.

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

Теперь u X v дает площадь прямоугольника и w X v дает площадь параллелограмма. Мы видим, что отношение двух областей совпадает с отношением длин AB к AP.

Вот еще один вид более общего положения.

sTop = v X w есть площадь параллелограмма AcdE и Bot = u X v является область большего parallogram ABFE. Отношение двух говорит вам, насколько далеко по линии АВ точка пересечения.