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

Question

Мне нужен алгоритм, который может найти пересечение двух двумерных линий. Каждая строка будет представлена ​​в виде точкой на линии и dx/dy параллельного вектора. Я попытался параметризовать каждую строку и решить систему уравнений для решения параметризованной переменной, которую я мог бы подключить к параметрическому уравнению линий и получить свой x/y, но моя попытка не удалась. Есть идеи? Я программирую на Python, но язык не имеет большого значения.

Answer 1

Вы в основном должны решить следующее уравнение:

х = _{0, а} + дх × т
у = у _{0, а} + ду × т
х = х _{0, б} + дх _б × ¯u
у = у _{0, б} + д _б × у

Или:

х _{0, а} + де _в × т = х _{0, б} + де _б × у
x _{0, a} + dx _a × t = x _{0, b} + де _б × у

Теперь, если вы делаете некоторые алгебраические манипуляции, вы увидите, что:

т = д _б × (х _{0, б} -x _{0, а}) -dx _б × (у _{0, б} -y _{0, а})/д
и = ду × (х _{0, б} -x _{0, а}) -dx × (у _{0, б} -y _{0, а})/д; где
d = дх × ду _б -dx _б × ду

Теперь, таким образом, только вопрос, чтобы определить, как tu или (вам не нужно вычислить оба) , и затем вставьте в формулу выше.Так

def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb): 
    t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya) 
    return (x0a+dxa*t,y0a+dya*t) 

Если d в уравнении (знаменатель) равен нулю, это означает, что нет пересечения (две линии параллельны). Вы можете изменить функцию и, например, вернуть None или вызвать исключение в таком случае.

Если вы протестируете его, например, с смещением вектора (1,0) и направлением (0,1); и вектор со смещением (0,2) и направлением (1,1); вы получаете не очень удивительный результат:

$ python3 
Python 3.5.2 (default, Nov 17 2016, 17:05:23) 
[GCC 5.4.0 20160609] on linux 
Type "help", "copyright", "credits" or "license" for more information. 
>>> def intersect(x0a,y0a,dxa,dya,x0b,y0b,dxb,dyb): 
...  t = (dyb*(x0b-x0a)-dxb*(y0b-y0a))/(dxa*dyb-dxb*dya) 
...  return (x0a+dxa*t,y0a+dya*t) 
... 
>>> intersect(1,0,0,1,0,2,1,1) 
(1.0, 3.0)