Find triangles to fill rectangle [closed]

I'm looking to solve the following problem:

Given a rectangle R and a shape S within that rectangle, find all shapes that, if combined with S, would fill R (without overlapping). The shapes are give by a set of points that make up the path around that shape.

This is probably a fairly common problem in computer graphics but I couldn't find anything when googling this.

If it makes things easier the shapes could all be triangles.

There are uncountably many ways of dividing the region between a rectangle $R$ and an interior polygon $S$. Since you are representing polygons as a sequence of vertices, you probably want a simply-connected polygon (no holes) so that there is a single border.

The simplest method to get this is to just draw a line segment from some point on $S$ to some point on the boundary $R$, in a direction that doesn't intersect $S$ again:

This converts $R\setminus S$ into a single polygon, with boundary $(a,b,c,d,a,e,f,g,h,i,e,a)$. Note that this polygon borders itself, including the line segment $\overline{ae}$ twice in its boundary. For many applications, this is not a problem. But if it is, you can always add a second cut line, for example from $b$ to a point $j$ on $\overline{hi}$. That divides $R\setminus S$ into two polygons: $(a,d,c,b,j,h,g,f,e,a)$ and $(a,b,j,i,e,a)$.

If your polygons need to be convex, then perhaps the most straightforward approach is to simply extend the sides of $S$ until they intersect $R$. This works even if $S$ itself is not convex. Ignore where the lines lay inside $S$, but cut up $R\setminus S$ along the lines to get convex polygons.