2
$\begingroup$

I have 2 vectors and their start points. i.e.

$\vec p_1, \vec v_1$ and $\vec p_2, \vec v_2$

Now I want check if vectors intersect. I found this alghoritm.

$\vec c = \vec p_2 - \vec p_1$

$\vec n_1 = $ perpendicular of $\vec v_1$

$\vec n_2 = $ perpendicular of $\vec p$

$d = (\vec n_2 \cdot v_2) / (\vec n_1 \cdot \vec v_2)$

If d is between 0 and 1 then there is intersection on point

$\vec p = \vec p1 + (\vec v_1 \cdot d)$

But this seems to not work. Is there any other method?

First of all I need to know if 2 vectors intersect, and then get point of intersection.

$\endgroup$

2 Answers 2

0
$\begingroup$

Your method does not look right. Here is how I would solve

We want $$ p = p_1 + \lambda v_1 = p_2 + \mu v_2, ~~ 0\le \lambda, \mu \le 1$$ So $$ c = p_1 - p_2 = \mu v_2 - \lambda v_1$$ Let $n_1$ be perpendicular to $v_1$ and $n_2$ perpendicular to $v_2$.

Then $$ < n_1, c > = \mu <n_1, v_2>, ~~~ <n_2, c> = -\lambda <n_2,v_1>$$ So, calculate $$ \mu= \frac{<n_1,c>}{<n_1, v_2>},~~~\lambda= \frac{<n_2,-c>}{<n_2, v_1>}$$ If both $\lambda$ and $\mu$ are between 0 and 1 you have the point of intersection.

Note: If the vectors are parallel, you have to go back to the original equation and see if $c$ is parallel to $v_1$ or not. If it is not, then there is no solution. If so, you can solve for $\alpha$ and $\mu$.

EDIT: -c in lambda

$\endgroup$
4
  • $\begingroup$ Works great! Thank you very much! One thing: in lambda there c should be negative $\endgroup$
    – l00k
    Dec 29, 2013 at 6:24
  • $\begingroup$ Opps. It 1:30 AM here and I need sleep :-) $\endgroup$
    – user44197
    Dec 29, 2013 at 6:25
  • $\begingroup$ I see that you (or someone else) changed the sign of $c$. Thanks. I hate to leave mistakes uncorrected $\endgroup$
    – user44197
    Dec 29, 2013 at 6:29
  • $\begingroup$ Yes it was I ;) $\endgroup$
    – l00k
    Dec 29, 2013 at 6:36
0
$\begingroup$

HINT : Let $P_1(x_1,y_1), v_1(a,b),P_2(x_2,y_2),v_2(c,d).$ Also, let $Q_1,Q_2$ be the end point respectilvely.

Two vectors intersect at the point $P$ $$\iff \text{There exists (k,l)$\in\mathbb R$ such that $\vec{P_1P}=k\vec{P_1Q_1},\vec{P_2P}=l\vec{P_2Q_2}$}$$

From here, you can get a condition about $x_1,y_1,a,b,x_2,y_2,c,d,k,l.$

$\endgroup$
1
  • $\begingroup$ There is need to check it iteratively.. I think there is better solution. $\endgroup$
    – l00k
    Dec 29, 2013 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.