# 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**_{12}
- 2**e**_{13} - **e**
_{23}
- **e**_{14}
- **e**_{24}
- **e**_{34}
) be a normalized line in P_{3}
.

Let *p* = (7**e**_{1}
+ 8**e**_{2}
+ 9**e**_{3}
+ **e**_{4}
) be a normalized point in P_{3}
.

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)
(7**e**_{1}
+ 8**e**_{2}
+ 9**e**_{3}
+ **e**_{4}
)
( -**e**_{12}
- 2**e**_{13}
- **e**_{23}
- **e**_{14}
- **e**_{24}
- **e**_{34}
) =

(1 / √3)(
-7**e**_{123} - 7**e**_{124} - 7**e**_{134} - 16**e**_{213} - 8**e**_{214} - 8**e**_{234} - 9**e**_{312} - 9**e**_{314} - 9**e**_{324} -**e**_{412} - 2**e**_{413} - **e**_{423}) .

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**_{213} ≡ -**e**_{123} so that -16**e**_{213} becomes +16**e**_{123} .

**e**_{214} ≡ -**e**_{124} so that -8**e**_{214} becomes +8**e**_{124} .

**e**_{314} ≡ -**e**_{134} so that -9**e**_{314} becomes +9**e**_{134} .

**e**_{324} ≡ -**e**_{234} so that -9**e**_{324} becomes +9**e**_{234} .

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

Now the equation reads:

(1 / √3)

(
-7**e**_{123} - 7**e**_{124} - 7**e**_{134} + 16**e**_{123} + 8**e**_{124} - 8**e**_{234} - 9**e**_{123} + 9**e**_{134} + 9**e**_{234} - **e**_{124} - 2**e**_{134} - **e**_{234})

Grouping terms:

(1 / √3)(
(-7 + 16 - 9)**e**_{123} +
(-7 + 8 - 1)**e**_{124} +
(-7 + 9 - 2)**e**_{134} +
(-8 + 9 - 1)**e**_{234}
)

Simplifying, we end up with:

*p* ∧ **L** =
(1 / √3)(
0**e**_{123} +
0**e**_{124} +
0**e**_{134} +
0**e**_{234}
)

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)*.