\chapter{Simplicial partitioning}

Tiles which are capable of partitioning one another are 
eliminated through minimal partitioning of simplices.  
To identify the cases, a bottom-up approach is taken: we first determine 
the meaningful ways to partition lower-dimensional simplices, and then 
extend this to higher dimensions. In the scope of this work, two 
tiles intersect if and only if one is capable of partitioning the 
other. Intersection of two tiles is not taken in the set theoretic
sense, while intersections of two 0--2-dimensional affine subspaces
are taken in the set theoretic sense.

There is no meaningful way to partition a point by another point, so 
that case is omitted. A point can divide a line segment into two if they 
intersect, so this case is retained. A point and a triangle have no 
meaningful partitioning with respect to each other.  

A line segment can partition another line segment, and a line segment 
can also be partitioned by a triangle. Finally, a triangle can be 
partitioned by another triangle. For reasons of minimality, only one 
of the two intersecting simplices is partitioned in each case.

\section{Line segment by point}

We first check whether a point lies on a line segment, and if it does, 
we partition the line segment at that point. To perform this test, the 
line segment is expressed as a one-dimensional affine basis by replacing 
the second endpoint with its difference from the first. We then compute 
the vector from the affine origin to the point.\looseness-1

Next, we take the orthogonal projection of this vector onto the segment's 
direction vector. If the sum of this projection with the affine origin is 
nearly coincident with the point, we proceed with testing; otherwise, the 
point is not on the segment. To confirm, we apply Gauss--Jordan elimination 
to express the point in terms of the line's affine basis. If the resulting 
coordinate lies within the unit interval, the point is indeed on the 
segment, and the segment is partitioned.\looseness-1

\section{Line segment by line segment}

We first check whether two line segments intersect, and if they do, 
we partition one of them at the intersection point. To detect an 
intersection, each segment is expressed as a one-dimensional affine 
basis. The lines spanned by these bases are then intersected using 
Gauss--Jordan elimination. If the resulting parameters for both 
segments lie within their respective unit intervals, the segments 
intersect, and partitioning is performed.

\section{Line segment by triangle}

If an intersection between the line segment and the triangle can be 
detected, we partition the line segment at that point. Both simplices 
are expressed as affine bases in their respective dimensions, and the 
intersection is obtained by solving the resulting linear system via 
Gauss--Jordan elimination. If the line segment's coefficient lies 
within the unit interval, the candidate intersection is retained; 
otherwise, it is discarded. 

When the line segment does intersect the plane of the triangle, we 
determine whether the intersection point lies inside the triangle 
using a common cross-product method. In this approach, the 
triangle is tessellated into one-dimensional affine bases---its 
edges, and each vertex is connected to the point being tested, forming 
another one-dimensional affine basis. For every pair of affine bases 
emanating from a common vertex, we compute their rotationally ordered 
cross product. If all such cross products point in the same direction, 
the point lies inside the triangle. If the point lies outside, at 
least one rotationally ordered cross product will traverse its angle 
in the opposite orientation, producing an anticommutative result.\looseness-1

\section{Triangle by triangle}

The partitioning of a triangle by another triangle builds upon the 
previous cases. The first step is to detect intersections between 
their edges. If two intersections are found---the expected outcome, 
though safeguards are included for degenerate cases---the cutting 
triangle partitions the other along the line defined by these two 
points. This produces a triangle and a quadrilateral, the latter of 
which is subdivided into two triangles. The intersections themselves 
are computed by treating each edge as a line segment and determining 
its intersection with the opposing triangle.