1
$\begingroup$

Given three points $A$, $B$ and $C$, that are not colinear, I want to find the vector $v$ which is perpendicular to the line $L$ that passes from $A$ and $B$ AND points to the half-plane created by $L$ that $C$ lies on.

enter image description here

I know that there are two orthogonal vectors to $T$: $\vec{v_1} = [t_y, -t_x]$ and $\vec{v_2} = [-t_y, t_x]$. I can find equation of the line, like $L: y=ax+c$, and solve it for both $C_x$ and $t_y+A_x$. I will return $\vec{v_1}$ if results had same sign, and $\vec{v_2}$ otherwise. And, of course, I have to take care of special case where $L: y=c$. Searching for an algebraic solution, I found this question: Find closest vector to A which is perpendicular to B. I tried to simplify the accepted answer for 2D, which resulted in:

\begin{aligned} s&=u\times t = (u_xt_y-u_yt_x)\vec{k} = s_z\vec{k}\\ v&=t\times s = s_z(t_y\vec{i}-t_x\vec{j}) = s_z\vec{v_1} \end{aligned}

That can be written as following, if the magnitude of the resulting vector is unimportant: $$ v = \begin{cases} \vec{v_1}, & \text{if $s_z > 0$} \\[2ex] \vec{v_2}, & \text{if $s_z<0$} \\[2ex] \vec{0}, & \text{if $s_z =0$} \end{cases} $$

But I'm not sure about the followings:

  1. Is the linked question really relevant to my problem? It says the closest vector that ..., which I don't even know what it means.
  2. Did I do the math right?
  3. Is there an even faster (less logical and floating point operations when implementing it) way to choose one of $\vec{v_1}$ and $\vec{v_2}$? I really don't care about the magnitude of the resulting vector.
$\endgroup$
1
$\begingroup$

The vectors $v_1$ and $v_2$ are indeed both nonzero and perpendicular to $L$, and also point in opposite directions, so one of them has to be a "good" one.

If you compute $u = C - A$, then you can compute $$ h = u \cdot v_1, $$ the dot product of $u$ and $v_1$.

If this turns out positive, then $u$ and $v_1$ point into the same halfplane, and your answer is $v_1$; if it's negative, your answer is $v_2$. If it's $0$, then $C$ is actually collinear with $A$ and $B$, which is kind of a free sanity-check that your inputs were valid. [All this is a rehash of what you wrote in your question as the first displayed equation.]

An alternative approach is to compute $s = u \times t$ (in 3-space), which seems bad because it's a cross-product, which looks like 2 multiplies and a subtraction for each term...but you only need to compute the "z" term because the other two are always zero. Then you compute $v = t \times s$, and this vector will point in the right direction. You needn't compute the $z$-component (it'll be zero), so you end up doing a total of $6$ multiplies and $3$ subtracts, plus the 6 subtractions to compute $u$ and $t$ in the first place.

Is this a winning algorithm? I haven't counted the operations in the other one. But it has one advantage: there's no branching, which can be helpful on some highly-parallel architectures (or at least this used to be the case).

It also has a downside: if $C$ is very close to the line $AB$, the magnitude of the resulting vector gets very small. You have to decide whether that matters to you. You said not, but in practice, I've often found such things annoying.

Here's something like an algorithm, written in very explicit Matlab

function v = findVec(A, B, C)
% Given points A,B,C in the xy-plane, C not on the line AB, find
% a vector v in the xy-plane that is perpendicular to AB, and points
% into the halfplane containing C

u = [C(1) - A(1), C(2) - A(2)]; 
t = [B(1) - A(1), B(2) - A(2)]; 

s = [0, 0, u(1)*t(2) - u(2)* t(1)]; % first cross product
v = [t(2)*s(3), -t(1) * s(3)];

and here's the more idiomatic, minimal operations, version:

function v = findVec(A, B, C)
% Given points A,B,C in the xy-plane, C not on the line AB, find
% a vector v in the xy-plane that is perpendicular to AB, and points
% into the halfplane containing C

trot = [B(2) - A(2), A(1) - B(1)]; % the t vector, rotated 90 degrees
     % because that's what I'll need in a minute.  

sz = (C(1) - A(1)) * trot(1) + (C(2) - A(2)) * trot(2);
v = sz * trot; 
$\endgroup$
3
  • $\begingroup$ Thank you very much John. I actually made a terrible mistake in my calculations and probably misled you. Because in fact the equation I put was obtained from your second method! I edited my question. But it was very beautiful that in the end both methods came to the same result, since u.v1=sz=(ux*ty-uy*tx). However, I prefer to look at it as the result of the dot product, thanks again for bringing it up. $\endgroup$
    – saastn
    Oct 6 '20 at 6:09
  • $\begingroup$ And there was an H after your first equation. Did you mean u or I'm missing something? And I believe that's s(3) in your first code sample. $\endgroup$
    – saastn
    Oct 6 '20 at 6:22
  • $\begingroup$ Fixed both --- sorry about the glitches. $\endgroup$ Oct 6 '20 at 11:10
1
$\begingroup$

The component of $\vec{u}$ that is parallel to $\vec{t}$ is

$$ \vec{u}_\parallel = \frac{ \vec{t} \cdot \vec{u} }{ \| \vec{t} \|^2 }\, \vec{t} $$

So subtract it form $\vec{u}$ to get $\vec{v}$

$$ \vec{v} = \vec{u} - \frac{ \vec{t} \cdot \vec{u} }{ \| \vec{t} \|^2 } \, \vec{t}$$

Proof

$$ \vec{t} \cdot \vec{v} = \vec{t} \cdot \vec{u} - \frac{ \vec{t} \cdot \vec{u} }{ \| \vec{t} \|^2 } \, (\vec{t} \cdot \vec{t}) = \vec{t} \cdot \vec{u} -\vec{t} \cdot \vec{u} = \vec{0} $$

$\endgroup$
1
  • $\begingroup$ Thanks John. That is aد interesting solution. But the calculations needed to get the answer from this method are huge. That norm in the denominator really terrifies me :) $\endgroup$
    – saastn
    Oct 6 '20 at 6:37

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.