John Shaughnessy

Projective geometric algebra

Meet and join in PGA 2D

Meet and join are incidence operations on projective flats. Meet is intersection. Join is span. The product symbols used for those operations depend on how the model represents flats.

The previous article introduced the 2D ganja.js convention, Algebra(2,0,1), where a line is a grade-1 vector and a finite point is a grade-2 bivector. This article keeps that convention and adds the two incidence operations needed to construct intersections and spans.

A flat is a projective linear subspace. In 2D projective geometry the main flats are points and lines. In 3D projective geometry they are points, lines, and planes. Meet and join are defined for flats first; the algebraic products are how a specific model computes those definitions.

Let U and W be vector subspaces of homogeneous space V.

projective flat for U = P(U)

join(P(U), P(W)) = P(U + W)
meet(P(U), P(W)) = P(U intersect W)

A join asks for the smallest projective flat containing both inputs. A meet asks for the largest projective flat contained in both inputs. In a projective plane, the join of two distinct points is their line, and the meet of two distinct lines is their point.

Flats, Blades, And Products

The homogeneous model begins with a real vector space V. A projective point is a nonzero vector with scalar multiples identified:

[v] = {..., -2v, -v, v, 2v, ...}

P(V) = all one-dimensional subspaces [v]

A projective flat comes from any vector subspace U of V. If U has vector dimension k, then P(U) has projective dimension k - 1.

dim(U) = 1  ->  P(U) is a point
dim(U) = 2  ->  P(U) is a line
dim(U) = 3  ->  P(U) is a plane

A blade is the exterior-algebra representative of one subspace. If v1, v2, andv3 are independent vectors, then

A = v1 ^ v2 ^ v3

is a grade-3 blade representing span(v1, v2, v3). Meet and join have their cleanest geometric reading on blades, because a blade represents one flat. The products extend by linearity to general multivectors, and a mixed-grade multivector is usually read grade by grade.

In the standard point-based projective exterior algebra, grade-1 elements are points and the wedge product builds spans:

point-based projective algebra:

P = one point vector
Q = one point vector

P ^ Q = line blade containing P and Q

In the dual, plane-based projective exterior algebra, grade-1 elements are hyperplane equations. In 2D, those hyperplanes are ordinary lines. Wedging line equations combines constraints:

plane-based 2D PGA:

lineA = one line vector
lineB = one line vector

lineA ^ lineB = point blade satisfying both line constraints

The grade-to-geometry table changes with the representation:

point-based projective plane:
  grade 1 -> point
  grade 2 -> line

plane-based projective plane:
  grade 1 -> line
  grade 2 -> point

This is the convention shift behind the product choices in this article. In point-based projective exterior algebra, wedge computes joins. In ganja's plane-based 2D PGA, wedge computes meets of line constraints, and a separate regressive product computes joins.

Duality And The Regressive Product

The dual vector space of V is the space of real-valued linear maps on V:

V* = Hom(V, R)

An element phi of V* is a linear equation. Its kernel is a hyperplane:

ker(phi) = { v in V : phi(v) = 0 }

For a subspace U of V, its annihilator is the subspace of all dual vectors that vanish on every vector in U:

U^0 = { phi in V* : phi(u) = 0 for every u in U }

The annihilator is the formal version of "all equations containing this flat." It reverses incidence:

(U + W)^0          = U^0 intersect W^0
(U intersect W)^0  = U^0 + W^0

Those two identities are the reason duality exchanges join and meet. A span of generators becomes an intersection of equations. An intersection of generators becomes a span of equations.

Poincare duality is the grade-reversing map that moves between the blade representing a subspace and the blade representing its annihilator. In a nondegenerate exterior algebra this can be written using the pseudoscalar. In PGA, the pseudoscalar is null, so ganja implements a coordinate duality with fixed basis signs.

!e0  =  e12    !e12 =  e0
!e1  = -e02    !e02 = -e1
!e2  =  e01    !e01 =  e2

The regressive product imports wedge through that duality:

A & B = dual^-1(dual(A) ^ dual(B))

ganja 2D sign convention:
A & B = !(!B ^ !A)

The order in the ganja formula fixes orientation signs. Multiplying every coefficient of a projective representative by the same nonzero scalar keeps the represented flat, while the orientation and normalization choices still matter for computations and display.

The dual map is linear, so it acts term by term on any multivector. The example below is a mixed-grade multivector; the operation is valid algebraically, while the individual blade terms carry the flat readings.

X = 2e0 - 3e1 + 4e2 + 5e01 - 7e02 + 11e12

!X =
  2 !e0
- 3 !e1
+ 4 !e2
+ 5 !e01
- 7 !e02
+ 11 !e12

= 2e12 + 3e02 + 4e01 + 5e2 + 7e1 + 11e0
= 11e0 + 7e1 + 5e2 + 4e01 + 3e02 + 2e12

The 2D PGA Representatives

These pages use the following representatives for finite points and lines:

point(x, y) = e12 - x e02 + y e01
line(a, b, c) = a e1 + b e2 + c e0

A finite point has homogeneous weight in the e12 component. Dividing by that weight gives ordinary chart coordinates:

P = w e12 - X e02 + Y e01

x = X / w = -P.e02 / P.e12
y = Y / w =  P.e01 / P.e12

A line has the ordinary equation ax + by + c = 0. If the e1 and e2 components have unit Euclidean length, then ax + by + c is signed distance. With any other nonzero scale, it is still the incidence value up to that scale.

P = e12 - x e02 + y e01
line = a e1 + b e2 + c e0

P ^ line = (a x + b y + c) e012

Two Lines Meet

In the plane-based convention, a line is a grade-1 constraint. Wedging two line constraints gives their common solution:

lineA = a1 e1 + b1 e2 + c1 e0
lineB = a2 e1 + b2 e2 + c2 e0

meet = lineA ^ lineB

The result is a grade-2 point blade. A nonzero e12 coefficient means the point is finite. A zero e12 coefficient with surviving e01 or e02 components means the point is ideal.

Work through two numerical lines:

lineA = 2e1 - e2 - 4e0       // 2x - y - 4 = 0
lineB = -e1 + 3e2 - 5e0      // -x + 3y - 5 = 0

lineA ^ lineB =
  (2e1 - e2 - 4e0) ^ (-e1 + 3e2 - 5e0)

= (2e1) ^ (3e2)
+ (2e1) ^ (-5e0)
+ (-e2) ^ (-e1)
+ (-e2) ^ (-5e0)
+ (-4e0) ^ (-e1)
+ (-4e0) ^ (3e2)

= 6e12 + 10e01 - e12 - 5e02 + 4e01 - 12e02
= 5e12 + 14e01 - 17e02

Normalize by the e12 coefficient to read the finite point:

meet / meet.e12 =
  e12 + (14 / 5)e01 - (17 / 5)e02

x = -meet.e02 / meet.e12 = 17 / 5
y =  meet.e01 / meet.e12 = 14 / 5

meet point = (17/5, 14/5)

Substitution verifies the incidence:

2(17/5) - 14/5 - 4 = 0
-(17/5) + 3(14/5) - 5 = 0

Two Points Join

In this convention, point-point join uses the regressive product &. The inputs are grade-2 point blades and the result is a grade-1 line:

A = point(x1, y1)
B = point(x2, y2)

A & B = line through A and B

The general component formula is:

A = e12 - x1 e02 + y1 e01
B = e12 - x2 e02 + y2 e01

A & B =
  (y2 - y1)e1
+ (x1 - x2)e2
+ (x2 y1 - x1 y2)e0

Here is the same calculation through ganja's dual-wedge-dual rule, using two finite points with ordinary coordinates (-1, 2) and (3, -1):

A = point(-1, 2)
  = e12 + e02 + 2e01

B = point(3, -1)
  = e12 - 3e02 - e01

!A = e0 - e1 + 2e2
!B = e0 + 3e1 - e2

!B ^ !A =
  (e0 + 3e1 - e2) ^ (e0 - e1 + 2e2)

= e0 ^ (-e1)
+ e0 ^ (2e2)
+ (3e1) ^ e0
+ (3e1) ^ (2e2)
+ (-e2) ^ e0
+ (-e2) ^ (-e1)

= -e01 + 2e02 - 3e01 + 6e12 + e02 - e12
= -4e01 + 3e02 + 5e12

A & B = !(!B ^ !A)
      = !(-4e01 + 3e02 + 5e12)
      = -4e2 - 3e1 + 5e0
      = -3e1 - 4e2 + 5e0

The join line is the equation:

-3x - 4y + 5 = 0

Check the two input points:

A = (-1, 2):  -3(-1) - 4(2) + 5 = 0
B = (3, -1):  -3(3)  - 4(-1) + 5 = 0

The same result comes from the component formula:

x1 = -1, y1 = 2
x2 =  3, y2 = -1

(y2 - y1)e1        = (-1 - 2)e1          = -3e1
(x1 - x2)e2        = (-1 - 3)e2          = -4e2
(x2 y1 - x1 y2)e0  = (3*2 - (-1*-1))e0  = 5e0

A & B = -3e1 - 4e2 + 5e0

Incidence Checks

In 2D PGA, a point lies on a line exactly when their wedge has zero e012 coefficient:

P ^ line = 0e012

Use the join line from the previous section:

A = e12 + e02 + 2e01
B = e12 - 3e02 - e01
join = -3e1 - 4e2 + 5e0

The incidence calculation for A expands as:

A ^ join =
  (e12 + e02 + 2e01) ^ (-3e1 - 4e2 + 5e0)

= e12 ^ (5e0)
+ e02 ^ (-3e1)
+ (2e01) ^ (-4e2)

= 5e012 + 3e012 - 8e012
= 0e012

The same check for B also vanishes:

B ^ join =
  (e12 - 3e02 - e01) ^ (-3e1 - 4e2 + 5e0)

= e12 ^ (5e0)
+ (-3e02) ^ (-3e1)
+ (-e01) ^ (-4e2)

= 5e012 - 9e012 + 4e012
= 0e012

This check is often useful in code. It tests incidence using the same projective representatives used by meet and join.

Ideal And Degenerate Results

The raw algebraic result has to be classified before it is read as coordinates. Parallel finite lines produce an ideal point. For example, x = 1 and x = 3 have the same direction and meet at the vertical ideal point:

lineA = e1 - e0
lineB = e1 - 3e0

lineA ^ lineB =
  e1 ^ (-3e0)
+ (-e0) ^ e1

= 3e01 - e01
= 2e01

The e12 weight is zero, so there is no finite (x, y) coordinate to recover. The remaining ideal component records the shared vertical direction.

Dependent inputs produce zero in these products. Two coincident line representatives have no unique point meet:

lineA = e1 - e0
lineC = 2e1 - 2e0

lineA ^ lineC = 0

Two coincident point representatives have no unique line join:

A = e12 + e02 + 2e01

A & A = 0

The zero result is a dependency signal for the product calculation. The input objects can still be valid projective objects; the requested construction is underdetermined by those inputs.

Using Meet And Join

The useful programming pattern is: represent geometric objects as blades, use meet or join for incidence construction, classify the raw result, then normalize when coordinates or distances need to be displayed.

edgeLine = vertexA & vertexB
cornerPoint = edgeLineA ^ edgeLineB

candidate = movingEdge ^ clippingLine
inside = (point ^ clippingLine).e012 <= tolerance

In later 2D PGA articles, the same line representation also acts as a mirror. A normalized line can participate in incidence calculations and in sandwich actions. The next article uses that line as a reflection operator, then composes two reflections into rotations and translations.