2
$\begingroup$

Assume these vectors start at the origin. Given I know the (x,y) components of vectors v1 and v2, what's the most computationally efficient way of finding v3, which points to the location of the intersection of the lines that are perpendicular to vectors v1 and v2, intersecting v1 and v2 at their endpoint?

Note that v1 and v2 are the same length.

enter image description here

$\endgroup$
1
$\begingroup$

Since $v_1$ and $v_2$ have the same length, $v_3$ is exactly in the middle between them: $$v_3=\frac{v_1+v_2}{2} \cdot s$$ $$v_3=(v_1+v_2)\cdot t$$

The vector between the endpoints of $v_3$ and $v_2$ is $w=v_2-v_3$. $w$ must be perpendicular to $v_2$. $$w \cdot v_2 = 0$$ $$(v_2-tv_1-tv_2) \cdot v_2 = 0$$ $$|v_2|^2-tv_1v_2-t|v_2|^2 = 0$$ $$t = \frac{|v_2|^2}{v_1v_2+|v_2|^2}$$

$\endgroup$
1
  • $\begingroup$ I have checked this and believe it is correct and optimal. $\endgroup$
    – David K
    Oct 14 '17 at 2:47
1
$\begingroup$

The equation for the first perpendicular is

$a_x(x - a_x) + a_y(y - a_y) = 0$

And the second

$b_x(x - b_x) + b_y(y - b_y) = 0$

Put those together

$ \left(\begin{matrix} a_x & a_y \\ b_x & b_y \end{matrix}\right) \left(\begin{matrix} x \\ y \end{matrix}\right) = \left(\begin{matrix} a_x^2 + a_y^2 \\ b_x^2 + b_y^2 \end{matrix}\right) $

Since the vectors have equal magnitude.

$ \left(\begin{matrix} a_x & a_y \\ b_x & b_y \end{matrix}\right) \left(\begin{matrix} x \\ y \end{matrix}\right) = \left(\begin{matrix} a_x^2 + a_y^2 \\ a_x^2 + a_y^2 \end{matrix}\right) $

$ \left(\begin{matrix} x \\ y \end{matrix}\right)= \frac{1}{a_xb_y-a_yb_x}\left(\begin{matrix} b_y & -a_y \\ -b_x & a_x \end{matrix}\right) \left(\begin{matrix} a_x^2 + a_y^2 \\ a_x^2 + a_y^2 \end{matrix}\right) $

$ \left(\begin{matrix} x \\ y \end{matrix}\right)= \left(\begin{matrix} \frac{(b_y-a_y)(a_x^2 + a_y^2)}{a_xb_y-a_yb_x} \\ \frac{(a_x-b_x)(a_x^2 + a_y^2)}{a_xb_y-a_yb_x} \end{matrix}\right) $

To do this efficently, make sure to save redundant calculations.

$u = \frac{a_x^2 + a_y^2}{a_xb_y-a_yb_x}$

$x = u(b_y - a_y)$

$y = u(a_x - b_x)$

$\endgroup$
1
  • $\begingroup$ I have checked this and believe it is correct and optimal. $\endgroup$
    – David K
    Oct 14 '17 at 2:47
1
$\begingroup$

I'll try a geometric/trigonometric approach.

Let $\theta$ be the angle between $\newcommand{v}{\mathbf v}\v_1$ and $\v_3.$ (This is also the angle between $\v_2$ and $\v_3.$)

Then the parallelogram with edges $\v_1$ and $\v_2$ is given by $\lVert \v_1\rVert \lVert \v_2\rVert \sin(2\theta),$ but is also given by the cross product $a_x b_y - b_x a_y,$ where the $(x,y)$ coordinates of $\v_1$ are $(a_x,a_y)$ and the $(x,y)$ coordinates of $\v_2$ are $(b_x,b_y).$ That is, $$ \lvert a_x b_y - b_x a_y \rvert = \lVert \v_1\rVert \lVert \v_2\rVert \sin(2\theta) = \lVert \v_1\rVert^2 \sin(2\theta) = \lVert \v_2\rVert^2 \sin(2\theta). $$

Also, the isoceles triangle with sides $\v_1,$ $\v_2,$ and $\v_2 - \v_1$ can be divided into two right triangles with angle $\theta$ and hypotenuse $\lVert \v_1\rVert = \lVert \v_2\rVert,$ and sides $\left\lVert \frac12(\v_2 - \v_1)\right\rVert$ and $\left\lVert \frac12(\v_1 + \v_2)\right\rVert,$ from which we find that $$\left\lVert \tfrac12(\v_2 - \v_1)\right\rVert = \lVert \v_1\rVert \sin\theta = \lVert \v_2\rVert \sin\theta$$ and $$\left\lVert \tfrac12(\v_1 + \v_2)\right\rVert = \lVert \v_1\rVert \cos\theta = \lVert \v_2\rVert \cos\theta.$$

We also have right triangles with hypotenuse $\lVert \v_3\rVert,$ angle $\theta,$ and adjacent leg $\lVert \v_1\rVert$ or $\lVert \v_1\rVert,$ so $$ \lVert \v_1\rVert = \lVert \v_2\rVert = \lVert \v_3\rVert \cos\theta. $$

So \begin{align} \left\lVert\frac{\lVert \v_1\rVert^2} {\lvert a_x b_y - b_x a_y\rvert} (\v_1 - \v_2)\right\rVert &= \frac{\lVert\v_2 - \v_1\rVert}{\sin(2\theta)} \\ &= \frac{\lVert\v_2 - \v_1\rVert}{2\sin\theta \cos\theta} \\ &= \frac{2\lVert\v_1\rVert\sin\theta}{2\sin\theta \cos\theta} \\ &= \frac{\lVert\v_1\rVert}{\cos\theta} \\ &= \lVert\v_3\rVert. \end{align}

This shows that $\v_4 = \frac{\lVert \v_1\rVert^2} {\lvert a_x b_y - b_x a_y\rvert} (\v_1 - \v_2)$ is a vector of the desired length, $\lVert\v_3\rVert.$ But $\v_4$ is in the direction of $\v_1 - \v_2,$ which is perpendicular to the direction of $\v_3.$ We therefore have to rotate $\v_4$ through a right angle.

To do this rotation, we can start by finding the $x$ and $y$ coordinates of $\v_1 - \v_2,$ which are $a_x - b_x$ and $a_y - b_y,$ respectively, then replace the $x$ coordinate with the negation of the $y$ coordinate and the $y$ coordinate with the $x$ coordinate. So we now have a vector with coordinates $(b_y - a_y, a_x - b_x).$ If we then multiply each of these coordinates by $\frac{\lVert \v_1\rVert^2}{a_x b_y - b_x a_y} = \frac{a_x^2 + a_y^2}{a_x b_y - b_x a_y},$ we end up with either $\v_3$ or $-\v_3,$ depending on the sign of $a_x b_y - b_x a_y$ and on whether we rotated in the correct direction. But this gives us exactly the same result as an earlier answer, confirming that that answer is correct up to a possible sign change. We have only to check the answer with suitable test values such as $a_x = b_y = 1,$ $a_y = b_x = 0$ to find that the sign is correct and therefore the answer is correct.


On the other hand, $\v_3$ is in the same direction as $\v_1 + \v_2.$ Since we found earlier that $\left\lVert \tfrac12(\v_1 + \v_2)\right\rVert = \lVert \v_2\rVert \cos\theta$ and that $\lVert \v_2\rVert = \lVert \v_3\rVert \cos\theta,$ we have $$ \v_3 = \frac{1}{2\cos^2\theta} (\v_1 + \v_2), $$ but also $$ \cos\theta = \frac{\lVert \v_1 + \v_2\rVert}{2\lVert \v_2\rVert}. $$ Therefore $$ 2\cos^2\theta = \frac{\lVert \v_1 + \v_2\rVert^2}{2\lVert \v_2\rVert^2}, $$ from which we conclude that \begin{align} \v_3 &= \frac{2\lVert\v_2\rVert^2}{\lVert\v_1 + \v_2\rVert^2}(\v_1 + \v_2) \\ &= \frac{2\lVert\v_2\rVert^2} {\lVert\v_1\rVert^2 + 2\v_1\cdot\v_2 + \lVert\v_2\rVert^2}(\v_1 + \v_2) \\ &= \frac{2\lVert\v_2\rVert^2} {2\v_1\cdot\v_2 + 2\lVert\v_2\rVert^2}(\v_1 + \v_2) \\ &= \frac{\lVert\v_2\rVert^2} {\v_1\cdot\v_2 + \lVert\v_2\rVert^2}(\v_1 + \v_2), \\ \end{align} which agrees with the conclusion of another earlier answer, confirming that that answer is correct.


We therefore have two correct answers already posted. As far as I can tell, each answer involves the same number of additions/subtractions, the same number of multiplications, and the same number of divisions in its calculations, with no other operations required. I think either of these answers is as computationally efficient as you can get unless you are able somehow to exploit some other information that we have not been given about the application in which you are computing this vector.

$\endgroup$

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.