0
$\begingroup$

Answered (I think!):

The triple product's purpose is to find a direction to the origin, perpendicular to the baseline, which is super trivial in 2D as there is only two perpendicular orientations, but the "cylinder" distinction is made in 3D because there are infinite perpendicular orientations - hence the triple product. Diagram in one of the answers shows this nicely!

Original Question:

I was looking at a video explaining the G-J-K algorithm for finding the two closest features on two convex shapes - when it came to a bit about, given a line, what is the direction in 3D space, from a point on the line, which points to the origin. Seems easy enough: just invert the position vector to point backwards to the origin - and that's exactly what the code does in an earlier step of the algorithm. Bizarrely, they say that as "the origin could be in a cylinder around the line in 3D space", the direction to the origin is given by the following:

Let X be the vector between points A and B on the line (from A to B), and Y be the inverse position vector from A to the origin. The direction to the origin, apparently, is (X cross Y) cross X! I expanded this out, saw an interesting pattern but could not link it to the problem:

For two vectors A, B; (A cross B) cross A I found to be equal to:

Ax(AyBy + AzBz) - Bx(AyAy + AzAz)

Ay(AxBx + AzBz) - By(AxAx + AzAz)

Az(AxBx + AyBy) - Bz(AxAx + AyAy)

Notated as a column vector, with "Vn" meaning the Nth coordinate of vector V. By "cross" I mean the 3D cross product.

I know this isn't the computer science stack exchange - I would like the mathematical meaning of "(A cross B) cross A", and a reason why the code does this, and not just another inverse position vector as it did previously, to find a direction to the origin. Many thanks for any help, and I will repost this on a different stack if it's too offensive here!

$\endgroup$

3 Answers 3

2
$\begingroup$

Double cross product is a very common technique to project a vector onto the surface. Consider the triple product

$$-\vec{n} \times \vec{n} \times \vec{v}$$

where $\vec{n}$ is a normal vector to some surface. $\vec{n}$ is typically normalized, meaning that its length $|\vec{n}| = 1$. Any cross-product with a normal is going to be orthogonal to that normal, so it will land on the surface the normal is orthogonal to. It will also be orthogonal to the original $\vec{v}$. Now the second cross product will rotate the vector counter-clockwise 90 degrees, still within that surface. The result of that will be that it will now be parallel to $\vec{v}$ in some sense. More precisely, we will have obtained the projection of the vector $\vec{v}$ onto the surface, for which $\vec{n}$ is a normal. It turns out that the cross product rotates the vector in the wrong direction, so we also need to add a minus sign in front to correct for that.

enter image description here

$\endgroup$
3
  • $\begingroup$ Although that being said, is it possible to arrange "-n X n X v" as "(n X v) X n"? If so then this is useful! $\endgroup$
    – FShrike
    Commented Jan 18, 2021 at 12:15
  • $\begingroup$ I take it back - this is very relevant thank you $\endgroup$
    – FShrike
    Commented Jan 18, 2021 at 12:18
  • 1
    $\begingroup$ Yes, cross product is anti-symmetric, namely A x B = - B x A. Have a look at full list of identities here, maybe you find something else useful as well en.wikipedia.org/wiki/Vector_algebra_relations $\endgroup$ Commented Jan 18, 2021 at 16:14
2
$\begingroup$

Vector triple product is defined as $$\vec P \times (\vec Q \times \vec R)= (\vec P \cdot \vec R)\vec Q-(\vec P\cdot \vec Q) \vec R.$$ Then $$\vec V=(\vec A \times \vec B) \times \vec A=-\vec A \times (\vec A \times \vec B)=-(\vec A \cdot \vec B)\vec A+(\vec A \cdot \vec A)\vec B.$$ If $\vec A$ is unit vector then, $$\vec V=\vec B-(\vec B \cdot \hat A)\hat A.$$ Then $\vec V$ is the component of $\vec B$ perpendicular to $\vec A$.

Otherwise ingeneral $\vec V$ is perpendicular to $\vec A$ and coplanar with $\vec A$ anf $\vec B$.

Edit: $\vec V$ is also the direction of projection of a line (with direction as $\vec B$) in the plane $ \vec A. \vec r=d$.

$\endgroup$
7
  • $\begingroup$ Try \cdot instead of the sentence full-stop for a scalar product. :) $\endgroup$
    – CiaPan
    Commented Jan 18, 2021 at 11:29
  • $\begingroup$ Thanks I will do this. $\endgroup$
    – Z Ahmed
    Commented Jan 18, 2021 at 11:30
  • $\begingroup$ So by your answer you mean: (if I visualise this in a 2D context) the line joining the two points will have this new product perpendicular to it, and pointing toward the origin? And this is different to simply a inverse position vector because while pointing to the origin it is also perpendicular to the original line> $\endgroup$
    – FShrike
    Commented Jan 18, 2021 at 12:12
  • 1
    $\begingroup$ $\vec V$ is also the direction of projection of a line (with direction as $\vec B$) in the plane $ \vec A. \vec r=d$. $\endgroup$
    – Z Ahmed
    Commented Jan 18, 2021 at 12:32
  • $\begingroup$ @ZAhmed That would make perfect sense with what the algorithm requires, thank you $\endgroup$
    – FShrike
    Commented Jan 19, 2021 at 12:19
0
$\begingroup$

I must be missing something, but taking the question in isolation, namely "Let X be the vector between points A and B. The direction to the origin, apparently, is:"

... Welp, If we know all about the endpoints of the line, namely $\vec{A}$ and $\vec{B}$, then some point on the line connecting the endpoints must be $$\vec{X} = \alpha \vec{A} + \left(1-\alpha\right) \vec{B} \:,$$ where $\alpha$ is a dimensionless parameter between zero and one, inclusive. If that form is agreeable, just take $-\vec{X}$ to reach back to the origin, or calculate $-\hat{X}$ to simply point there.

$\endgroup$
1
  • $\begingroup$ I agree with you - but I am asking about the mystery of X cross Y cross X and how it relates to anything at all - did the author of the video make a mistake? make unnecessary complexity? I can't figure it out $\endgroup$
    – FShrike
    Commented Jan 18, 2021 at 11:14

You must log in to answer this question.

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