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
    Commented Dec 29, 2013 at 6:24
  • $\begingroup$ Opps. It 1:30 AM here and I need sleep :-) $\endgroup$
    – user44197
    Commented 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
    Commented Dec 29, 2013 at 6:29
  • $\begingroup$ Yes it was I ;) $\endgroup$
    – l00k
    Commented 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
    Commented Dec 29, 2013 at 6:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .