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))]

Wren

Library: Wren-seq

This assumes that a rectangle is such that its lower left vertex is at point (0, 0) and it is then completely defined by its width along the x-axis and height along the y-axis.

It then uses the approach suggested by Nigel Galloway in the talk page.

Assuming the rectangle is to be split into 'n' triangles where n >= 3, we first bisect the rectangle into two triangles, add the top one to the result list and then divide the bottom one into (n-1) triangles. We do this by choosing (n - 2) points at random on the bottom side of the rectangle which together with the two bottom vertices are such that, after sorting, the difference between successive pairs is never the same. We then link each pair of points with the upper right vertex of the rectangle to form the requisite number of triangles.

This process should ensure that all the triangles are different, albeit the first one is usually much larger than the others. However, to be absolutely sure, we check that the areas of all the triangles are different. <lang ecmascript>import "random" for Random import "./seq" for Lst

var rand = Random.new()

var pointsOfRect = Fn.new { |w, h| [[0, 0], [h, 0], [h, w], [0, w]] }

var dist = Fn.new { |p1, p2|

   var dx = p2[0] - p1[0]
   var dy = p2[1] - p1[1]
   return (dx * dx + dy * dy).sqrt

}

// Heron's formula var area = Fn.new { |tri|

   var a = dist.call(tri[1], tri[0])
   var b = dist.call(tri[2], tri[1])
   var c = dist.call(tri[0], tri[2])
   var s = (a + b + c) * 0.5
   return (s * (s - a) * (s - b) * (s - c)).sqrt

}

var divideRectIntoTris = Fn.new { |w, h, n|

   if (n.type != Num || !n.isInteger || n < 3) {
       Fiber.abort("'n' must be an integer >= 3.")
   }
   var pts = pointsOfRect.call(w, h)

   // upper triangle
   var upper = [pts[0], pts[1], pts[2]]
   var tris = [upper]

   // divide the side of the rectangle along the x-axis into
   // 'n-1' sections of different lengths
   var xs   = List.filled(n, 0)
   var lens = List.filled(n - 1, 0)
   xs[n-1] = w

   // need n-2 random numbers in the open interval (0, w)
   // it's very unlikely that the following loop will need more than one iteration
   while (!Lst.distinct(lens).count == n - 1 || lens.any { |l| l == 0 }) {
       for (i in 1..n-2) xs[i] = rand.float(w)
       xs.sort()
       for (i in 0..n-2) lens[i] = xs[i+1] - xs[i]
   }
   for (i in 0..n-2) tris.add([[xs[i], 0], pts[2], [xs[i+1], 0]])
   return tris

}

var dims = [ [20, 10, 4], [30, 20, 8] ] for (dim in dims) {

   var w = dim[0]
   var h = dim[1]
   var n = dim[2]
   System.print("A rectangle with a lower left vertex at (0, 0), width %(w) and height %(h)")
   System.print("can be split into the following %(n) triangles:")

   // make sure all triangles have different areas
   while (true) {
       var areas = []
       var tris = divideRectIntoTris.call(w, h, n)
       for (tri in tris) areas.add(area.call(tri))
       if (Lst.distinct(areas).count == n) {
           System.print(tris.join("\n"))
           break
       }
   }
   System.print()

}</lang>

Output:

A rectangle with a lower left vertex at (0, 0), width 20 and height 10
can be split into the following 4 triangles:
[[0, 0], [10, 0], [10, 20]]
[[0, 0], [10, 20], [8.0564138517119, 0]]
[[8.0564138517119, 0], [10, 20], [14.094139436569, 0]]
[[14.094139436569, 0], [10, 20], [20, 0]]

A rectangle with a lower left vertex at (0, 0), width 30 and height 20
can be split into the following 8 triangles:
[[0, 0], [20, 0], [20, 30]]
[[0, 0], [20, 30], [0.65937939308462, 0]]
[[0.65937939308462, 0], [20, 30], [4.2532489308194, 0]]
[[4.2532489308194, 0], [20, 30], [14.155948215869, 0]]
[[14.155948215869, 0], [20, 30], [14.557956830854, 0]]
[[14.557956830854, 0], [20, 30], [17.090800736769, 0]]
[[17.090800736769, 0], [20, 30], [23.99024789249, 0]]
[[23.99024789249, 0], [20, 30], [30, 0]]