Projective geometric algebra

Shape intersections in PGA 2D

PGA gives direct primitives for edge lines, side tests, and crossing points. Polygon intersection still needs an algorithm, while the geometric tests inside that algorithm become explicit.

Points, lines, meets, joins, and motions are enough for a practical graphics problem: intersect two convex polygons. Convex shapes reduce the problem to half-space clipping against one support line at a time.

Each oriented edge of the clipping polygon defines a support line. Points on the inside side of every support line survive; points outside get clipped away. When an edge crosses a support line, PGA gives the candidate vertex as a line-line meet.

Edges Become Lines

A polygon edge is the vee join of its endpoint points:

A = e12 - ax e02 + ay e01
B = e12 - bx e02 + by e01
edgeLine = A & B

For counter-clockwise polygons, the inside half-space is the nonpositive side of that line:

inside if (P ^ edgeLine).e012 <= tolerance

Meets Supply Candidate Vertices

When a subject polygon edge crosses the active clipping line, the boundary point is a meet:

subjectEdge = subjectStart & subjectEnd
candidate = edgeLine ^ subjectEdge

The clipping algorithm decides whether the candidate should be inserted, based on the inside/outside states of the segment endpoints. PGA supplies the candidate geometry and side tests; the algorithm handles output ordering and insertion.

Tolerances And Limits

Real polygon intersection code needs tolerances. A vertex close to a support line can be numerically ambiguous, and nearly parallel edges can produce candidate meets that are sensitive to small coefficient changes. Side tests need a small tolerance around e012 = 0.

Non-convex shapes need more machinery: decomposition, winding rules, or a more general clipping algorithm. PGA still helps express the local geometry inside those larger algorithms.