Divide a rectangle into a number of unequal triangles

Divide a rectangle into a number of unequal triangles is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given the coordinates of a rectangle and a number, cut the rectangle into that number of random, non-similar triangles that exactly cover the rectangle without gaps or overlaps.

The number of triangles may have reasonable limits such as being above a small limit, and/or odd or even, and/or prime for example.
The number should not have an upper bound however, so that many triangles can be generated.

• Explain, or refer to the algorithm employed.
• Give a sample of sets of triangles produced from running the algorithm, on this page.

Python

I thought up two algorithms that are explained in the docstrings of functions `rect_into_tri`and `rect_into_top_tri`.

It is assumed that the rectangle has its bottom left coordinate at (0,0) and is not rotated in the coordinate space, meaning that the location of the top-right corner of the rectangle is then enough to define it.

<lang python> import random from typing import List, Union, Tuple

1. Types

Num = Union[int, float] Point = Tuple[Num, Num]

1. %% Algorithms.

def rect_into_tri(

       top_right: Tuple[Num, Num] = (2, 1), # assuming bottom_left is at 0,0
       triangles: int             = 5,      # Odd number > 2
       _rand_tol: Num             = 1e6,    # Sets max random divisions of rectange width
       ) -> List[Tuple[Point, Point, Point]]:
   """
   Divide Rectangle into triangles number of non-similar triangles that
   exactly cover the rectangles area.

   Parameters
   ----------
   top_right : Tuple[Num, Num], optional
       Rectangle bottom-left is always at (0, 0). The default is (2, 1).
   triangles : int, optional
       Number of triangles created. An odd number > 2. The default is 5.
   _rand_tol : Num, optional
       Sets max random divisions of rectange width. The default is 1e6.

   Returns
   -------
   List[Tuple[Point, Point, Point]]
       A list of triangles; each of three points - of two numbers.

   Algorithm "Divide into top and bottom triangles"
   ================================================

   Think of a rectangle lying, without rotation, on a plane. Lets name the corners A, B, C, and D like this:

       A        B

       D        C

   Add one point, `p` between-but-not-equal-to A and B giving

       A p      B

       D        C

   Create the two extra lines D-p and p-C creating 3 triangles A-p-D, D-p-C and p-B-C. Now if distances A-p, p-B and B-C are all different, then the triangles will be different.

   If we instead inserted **two** points between A-B, p0 and p1, we can insert **one** point q0, along D-C

         0  1
       A p  p   B

       D   q    C
           0

   We think of the L-to-R ordered top points as A p0 p1 then B; and the ordered l-to-R bottom points as D q0 then C.
   * Create the triangles by using the i'th, (i+1)'th top points and the i'th bottom point; alternating with the (i)'th (i+1)'th bottom point and the (i+1)'th top point.
   * Ensure the distances between successive top points, B-C, and successive bottom points are all different to get different triangles.
   * If you insert `n`top points p, then you need `n-1` bottom points q.

   Randomly divide A-B n times, and D-C n-1 times; then redo this if all the distances aren't different to your required precision.

   This algorithm generates many triangles with a side along D-C as well as A-B

   """

   width, height = top_right
   assert triangles > 2 and triangles % 2 == 1, "Needs Odd number greater than 2"
   #assert triangles * 100 < _rand_tol, "Might not have enough tolerance to ensure disimilar triangles"

   _rand_tol = int(_rand_tol)

   #%% Point insertion
   insert_top = triangles // 2
   p = q = None
   while not p or not different_distances(p, q, height):
       p = [0] + rand_points(insert_top,     width, int(_rand_tol)) + [width]  # top points
       q = [0] + rand_points(insert_top - 1, width, int(_rand_tol)) + [width]  # bottom points

   #%% Triangle extraction
   top_tri = [((t0, height), (t1, height), (b0, 0))
              for t0, t1, b0 in zip(p, p[1:], q)]
   bottom_tri = [((b0, 0), (b1, 0), (t1, height))
                 for b0, b1, t1 in zip(q, q[1:], p[1:])]

   return top_tri + bottom_tri

def rect_into_top_tri(

       top_right: Tuple[Num, Num] = (2, 1),
       triangles: int             = 4,
       _rand_tol: Num             = 1e6,
       ) -> List[Tuple[Point, Point, Point]]:
   """
   Divide Rectangle into triangles number of non-similar triangles that
   exactly cover the rectangles area.

   Parameters
   ----------
   top_right : Tuple[Num, Num], optional
       Rectangle bottom-left is always at (0, 0). The default is (2, 1).
   triangles : int, optional
       Number of triangles created. An odd number > 2. The default is 4.
   _rand_tol : Num, optional
       Sets max random divisions of rectange width. The default is 1e6.

   Returns
   -------
   List[Tuple[Point, Point, Point]]
       A list of triangles; each of three points - of two numbers.

   Algorithm "Divide along top into triangles"
   ===========================================

   Think of a rectangle lying, without rotation, on a plane. Lets name the corners A, B, C, and D like this:

       A        B

       D        C

   If we add The diagonal D-B we split into two triangles BUT they are similar.

   Add one point, `p` between-but-not-equal-to A and B giving

       A p      B

       D        C

   Create the one extra line D-p creating 3 triangles D-A-p, D-p-B and D-B-C.
   Now if distances A-p, and p-B are all different, then the triangles will
   not be similar.

   If we instead inserted **two** points between A-B, p0 and p1, we get:

         0  1
       A p  p   B

       D        C

   We think of the L-to-R ordered top points as A p0 p1 then B lets call those
   the top points top[0] = A, top[i+1] = p[i], top[-1] = B; 
   * Create the triangles by using the i'th, (i+1)'th top points and bottom point D.
   * Add the Triangle D-B-C
   
   This algorithm generates only one triangle with a side along D-C

   """

   width, height = top_right
   assert int(triangles)==triangles and triangles > 2, "Needs int > 2"
   #assert triangles * 100 < _rand_tol, "Might not have enough tolerance to ensure disimilar triangles"

   _rand_tol = int(_rand_tol)

   #%% Point insertion
   insert_top = triangles - 2
   top = [0] + rand_points(insert_top, width, int(_rand_tol)) + [width]  # top points

   #%% Triangle extraction
   top_tri = [((0, 0), (t0, height), (t1, height))
              for t0, t1 in zip(top, top[1:])]
   bottom_tri = [((0, 0), (width, height), (width, 0))]

   return top_tri + bottom_tri

1. %% Helpers

def rand_points(n: int, width: Num=1, _rand_tol: int=1_000_000) -> List[float]:

   "return n sorted, random points where 0 < point < width"
   return sorted(p * width / _rand_tol
                 for p in random.sample(range(1, _rand_tol), n))

def different_distances(p: List[Num], q: List[Num], height: Num) -> bool:

   "Are all point-to-next-point distances in p and q; and height all different?"
   diffs =  [p1 - p0 for p0, p1 in zip(p, p[1:])]
   diffs += [q1 - q0 for q0, q1 in zip(q, q[1:])]
   diffs += [height]
   return len(diffs) == len(set(diffs))

1. %% Main.

if __name__ == "__main__":

   from pprint import pprint as pp

   print("\nrect_into_tri #1")
   pp(rect_into_tri((2, 1), 5, 10))
   print("\nrect_into_tri #2")
   pp(rect_into_tri((2, 1), 5, 10))
   print("\nrect_into_top_tri #1")
   pp(rect_into_top_tri((2, 1), 4, 10))
   print("\nrect_into_top_tri #2")
   pp(rect_into_top_tri((2, 1), 4, 10))

</lang>

Output:

rect_into_tri #1
[((0, 1), (0.6, 1), (0, 0)),
 ((0.6, 1), (1.4, 1), (0.4, 0)),
 ((1.4, 1), (2, 1), (2, 0)),
 ((0, 0), (0.4, 0), (0.6, 1)),
 ((0.4, 0), (2, 0), (1.4, 1))]

rect_into_tri #2
[((0, 1), (0.2, 1), (0, 0)),
 ((0.2, 1), (1.4, 1), (1.8, 0)),
 ((1.4, 1), (2, 1), (2, 0)),
 ((0, 0), (1.8, 0), (0.2, 1)),
 ((1.8, 0), (2, 0), (1.4, 1))]

rect_into_top_tri #1
[((0, 0), (0, 1), (0.6, 1)),
 ((0, 0), (0.6, 1), (0.8, 1)),
 ((0, 0), (0.8, 1), (2, 1)),
 ((0, 0), (2, 1), (2, 0))]

rect_into_top_tri #2
[((0, 0), (0, 1), (1.0, 1)),
 ((0, 0), (1.0, 1), (1.2, 1)),
 ((0, 0), (1.2, 1), (2, 1)),
 ((0, 0), (2, 1), (2, 0))]