Using GA to test if a point lies on a line

From the discussion about point-plane distance queries, we saw that p ⌋ π ≡ p ∧ Π = 0 when points and planes coincide.

Does the same apply to point-line distance queries as well?

Let's find out with a simple example:

Let L = | (1, 2, 3, 1) ∧ (4, 5, 6, 1) | =

(1 / √3) ( -e₁₂ - 2e₁₃ - e ₂₃ - e₁₄ - e₂₄ - e₃₄ ) be a normalized line in P₃ .

Let p = (7e₁ + 8e₂ + 9e₃ + e₄ ) be a normalized point in P₃ .

It's not hard to visualize that the point p = (7, 8, 9, 1) lies on the line passing through points (1, 2, 3, 1) and (4, 5, 6, 1) .

Does the math work?

Compute p ∧ L =

(1 / √3) (7e₁ + 8e₂ + 9e₃ + e₄ ) ( -e₁₂ - 2e₁₃ - e₂₃ - e₁₄ - e₂₄ - e₃₄ ) =

(1 / √3)( -7e₁₂₃ - 7e₁₂₄ - 7e₁₃₄ - 16e₂₁₃ - 8e₂₁₄ - 8e₂₃₄ - 9e₃₁₂ - 9e₃₁₄ - 9e₃₂₄ -e₄₁₂ - 2e₄₁₃ - e₄₂₃) .

Now is a good time to re-arrange (i.e., 'swap') basis blade indices so that they're ordered in 'canonical form'.

Negate the coefficient of basis elements whose indices require an odd number of swaps:

e₂₁₃ ≡ -e₁₂₃ so that -16e₂₁₃ becomes +16e₁₂₃ .

e₂₁₄ ≡ -e₁₂₄ so that -8e₂₁₄ becomes +8e₁₂₄ .

e₃₁₄ ≡ -e₁₃₄ so that -9e₃₁₄ becomes +9e₁₃₄ .

e₃₂₄ ≡ -e₂₃₄ so that -9e₃₂₄ becomes +9e₂₃₄ .

For an even number of swaps, just write the indices in order.

Now the equation reads:

(1 / √3)

( -7e₁₂₃ - 7e₁₂₄ - 7e₁₃₄ + 16e₁₂₃ + 8e₁₂₄ - 8e₂₃₄ - 9e₁₂₃ + 9e₁₃₄ + 9e₂₃₄ - e₁₂₄ - 2e₁₃₄ - e₂₃₄)

Grouping terms:

(1 / √3)( (-7 + 16 - 9)e₁₂₃ + (-7 + 8 - 1)e₁₂₄ + (-7 + 9 - 2)e₁₃₄ + (-8 + 9 - 1)e₂₃₄ )

Simplifying, we end up with:

p ∧ L = (1 / √3)( 0e₁₂₃ + 0e₁₂₄ + 0e₁₃₄ + 0e₂₃₄ )

which is the zero trivector (i.e., a degenerate plane formed by wedging together three collinear points), so the point does indeed lie on the line!

I'd also like to mention that while writing the calculations out by hand appears tedious (and it is), an efficient computer implementation of the above only performs 12 floating-point muls and 8 floating-point adds.

The ordering of basis blade indices, handling which coefficients go where, etc. can be performed at compile-time with template meta-programming techniques in the C++ or D programming languages.

Storage requirements are fairly undemanding: for 3-d k-flats, we need

• 4 floats to store a point,
• 4 floats for a plane, and
• 6 floats for a line.

This is pretty much matches the storage requirements for these same entities within a standard 3-d engine setting. Note, however, that a line doesn't directly store any information about the points used to construct it (it's not a line segment).