# Divide a rectangle into a number of unequal triangles

*is a*

**Divide a rectangle into a number of unequal triangles****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.

## Julia

The `cutrectangle` method creates a new triangle by consuming a previously created triangle by cutting it at a location determined by the ratio of two sequential primes, making for guaranteed noncongruence of all triangles thus made. The Luxor code is for the demo. See also <link>https://lynxview.com/temp/luxor-drawing.png</link>

```
using Colors
using Luxor
using Primes
using Random
mutable struct Triangle
v1::Point
v2::Point
v3::Point
end
function cutrectangle(A, B, C, D, n)
n < 2 && error("Cannot cut rectangle into < 2 triangles")
triangles, i, j = [Triangle(A, B, C), Triangle(C, D, A)], 1, 2
for _ in 2:n-1
t = popfirst!(triangles)
p = Point(t.v3.x + i/(2j) * (t.v1.x - t.v3.x), t.v3.y + i/(2j) * (t.v1.y - t.v3.y))
push!(triangles, Triangle(t.v1, t.v2, p), Triangle(t.v2, t.v3, p))
i, j = j, nextprime(j + 1)
end
return triangles
end
colors = shuffle(collect(Colors.color_names))
idx = 1
Drawing(500, 500)
origin()
triangles = cutrectangle(Point(0.0, 0.0), Point(200.0, 0.0), Point(200.0, 200.0), Point(0.0, 200.0), 9)
for t in triangles
@show t
sethue(colors[mod1(idx, length(colors))][1])
poly([t.v1, t.v2, t.v3], :fill)
global idx += 1
end
finish()
preview()
```

- Output:

t = Triangle(Point(200.0, 0.0), Point(150.0, 150.0), Point(105.0, 105.0)) t = Triangle(Point(200.0, 0.0), Point(200.0, 200.0), Point(167.85714285714286, 96.42857142857143)) t = Triangle(Point(200.0, 200.0), Point(150.0, 150.0), Point(167.85714285714286, 96.42857142857143)) t = Triangle(Point(200.0, 200.0), Point(0.0, 200.0), Point(109.0909090909091, 109.0909090909091)) t = Triangle(Point(0.0, 200.0), Point(66.66666666666666, 66.66666666666666), Point(109.0909090909091, 109.0909090909091)) t = Triangle(Point(0.0, 200.0), Point(0.0, 0.0), Point(38.46153846153845, 123.07692307692307)) t = Triangle(Point(0.0, 0.0), Point(66.66666666666666, 66.66666666666666), Point(38.46153846153845, 123.07692307692307)) t = Triangle(Point(0.0, 0.0), Point(200.0, 0.0), Point(64.8529411764706, 64.8529411764706)) t = Triangle(Point(200.0, 0.0), Point(105.0, 105.0), Point(64.8529411764706, 64.8529411764706))

## Perl

All triangle vertices lie on the lengths and the corners and their locations are defined by ratios among two sequences with unique numbers. Since the height is the same but with different base for all triangles, none will share the area.

```
use strict;
use warnings;
use feature 'say';
use List::Util 'sum';
sub UnequalDivider {
my($L,$H,$N) = @_;
die unless $N > 2;
return (0,$H), (0,0), ((2/5)*$L,$H), ($L,0), ($L,$H) if $N == 3;
my ($fail,%unique,%ratios,@base,@roof,$bTotal,$rTotal);
do {
$fail = 0;
%unique = %ratios = () ;
++$unique{int(rand 2*$N) + 1} while keys %unique < $N;
my @segments = keys %unique;
@base = @segments[ 0 .. $N/2-1];
@roof = @segments[$N/2 .. $#segments];
($bTotal,$rTotal) = ( sum(@base), sum(@roof) );
++$ratios{$_/$bTotal} for (@base);
for (@roof) { if ( exists($ratios{$_/$rTotal}) ) { $fail = 1 && last } }
} until ( $fail == 0 );
my ($bPartial,$rPartial) = ( shift(@base), shift(@roof) );
my @vertices = ([0,$H], [0,0], [($rPartial/$rTotal)*$L,$H]);
for (0 .. @base) {
push @vertices, [$bPartial/$bTotal*$L,0];
if (@base == 1) {
0 == $N%2 ? return @vertices, ([$L,$H], [$L,0])
: return @vertices, ([$L*(1-$roof[-1]/$rTotal),$H], [$L,0], [$L,$H]);
}
($bPartial) += shift @base;
($rPartial) += shift @roof;
push @vertices, [$rPartial/$rTotal*$L,$H];
}
}
my @V = UnequalDivider(1000,500,7);
say sprintf( '(%.3f %.3f) 'x3, @{$V[$_]}, @{$V[++$_]}, @{$V[++$_]} ) =~ s/\.000//gr for 0 .. @V-3;
```

- Output:

(0 500) (0 0) (352.941 500) (0 0) (352.941 500) (520 0) (352.941 500) (520 0) (529.412 500) (520 0) (529.412 500) (680 0) (529.412 500) (680 0) (588.235 500) (680 0) (588.235 500) (1000 0) (588.235 500) (1000 0) (1000 500)

## Phix

Extending the approach suggested by Nigel Galloway I devised a scheme that needs no checking, and penned a wee little interactive visualisation demo of it, that can be run here. Should you find a way to make it draw similar triangles, shout out and let me know n and canvas size!

-- demo/rosetta/SpliRT.exw with javascript_semantics include pGUI.e constant title = "Divide rectange into unequal triangles", help_text = """ Press F1 to see this help text. Let the rectangle/canvas be ABCD (clockwise) and P be the leftmost point where Red and Blue touch, and Q (if needed, aka n!=3) the rightmost vertex of the Green triangle. The Red triangle (ACD) is a right angle triangle (no others will be). The Blue triangle (BPC) is an isoceles triangle except when the canvas is square and n=3, in which case P is 1/3 along AC (nearer A) making BPC acture and ABP (Green) obtuse (and therefore non-similar). For a non-square rectangle and n=3 one of BPC and ABP is always acute and the other obtuse (and therefore non-similar). The green triangle (AQP when n!=3, AQ==AB*0.6) is non-isoceles. The remainder (QBP) is split equally along QB to create the remaining n-3 triangles, drawn in black and white, and all of them are acute and non-isoceles and non-similar. In that way, none of the triangles can be similar for any n and do not need checking. Press +/- to alter n, resize the window to change the canvas/rectangle size, which of course can be used to make it square or not square (the canvas is initially square since that can be a bit fiddly). """ integer n = 5 Ihandle dlg, canvas cdCanvas cddbuffer, cdcanvas procedure draw_triangle(sequence t, integer colour) cdCanvasSetForeground(cddbuffer, colour) cdCanvasBegin(cddbuffer,CD_FILL) for c=1 to 3 do atom {x,y} = t[c] cdCanvasVertex(cddbuffer, x, y) end for cdCanvasEnd(cddbuffer) end procedure function redraw_cb(Ihandle /*ih*/) integer {w,h} = IupGetIntInt(canvas,"DRAWSIZE") atom px = w/2, py = h/2 string details = sprintf(" (n=%d, rectangle %dx%d)",{n,w,h}) IupSetStrAttribute(dlg,"TITLE",title&details) cdCanvasActivate(cddbuffer) cdCanvasClear(cddbuffer) if n<3 then cdCanvasSetForeground(cddbuffer, CD_RED) cdCanvasSetTextAlignment(cddbuffer, CD_CENTER) cdCanvasText(cddbuffer,px,py,"NOT POSSIBLE!") else draw_triangle({{0,0},{0,h},{w,0}},CD_RED) if n=3 and w=h then {px,py} = {w/3,h*2/3} end if draw_triangle({{px,py},{w,h},{w,0}},CD_BLUE) if n=3 then draw_triangle({{0,h},{px,py},{w,h}},CD_GREEN) else atom qx = w*0.6, qd = (w-qx)/(n-3) draw_triangle({{0,h},{px,py},{qx,h}},CD_GREEN) atom bw = CD_WHITE for i=4 to n do bw = iff(bw=CD_WHITE?CD_BLACK:CD_WHITE) draw_triangle({{qx,h},{px,py},{qx+qd,h}},bw) qx += qd end for end if end if cdCanvasFlush(cddbuffer) return IUP_DEFAULT end function function map_cb(Ihandle ih) cdcanvas = cdCreateCanvas(CD_IUP, ih) cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas) cdCanvasSetBackground(cddbuffer, CD_WHITE) return IUP_DEFAULT end function function help_cb(Ihandln /*ih*/) IupMessage(title,help_text,bWrap:=false) return IUP_DEFAULT end function function key_cb(Ihandle /*dlg*/, atom c) if c=K_ESC then return IUP_CLOSE end if if c=K_F1 then return help_cb(NULL) end if if c='-' then n-= 1 IupRedraw(dlg) end if if c='+' then n+= 1 IupRedraw(dlg) end if return IUP_CONTINUE end function IupOpen() canvas = IupCanvas("RASTERSIZE=500x500") IupSetCallbacks(canvas, {"MAP_CB", Icallback("map_cb"), "ACTION", Icallback("redraw_cb")}) dlg = IupDialog(canvas,`TITLE="%s"`,{title}) IupSetCallback(dlg, "K_ANY", Icallback("key_cb")) IupShow(dlg) IupSetAttribute(canvas, "RASTERSIZE", NULL) IupSetAttributeHandle(NULL,"PARENTDIALOG",dlg) if platform()!=JS then IupMainLoop() IupClose() end if

## 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.

```
import random
from typing import List, Union, Tuple
# Types
Num = Union[int, float]
Point = Tuple[Num, Num]
#%% 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
#%% 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))
#%% 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))
```

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

## Raku

The first triangle bisects the rectangle via the diagonal. The rest of them all got one vertex at the origin and a side defined by ratios of numbers from a descending positive integer sequence.

```
# 20220123 Raku programming solution
# Proof :
#
# H-----------A---------B-------C-----D---E
# | |
# | |
# | |
# O---------------------------------------L
#
# ▲OEL is unique as its area is the sum of the rest.
#
# and also in terms of area ▲OHA > ▲OAB > ... > ▲ODE
sub UnequalDivider (\L,\H,\N where N > 2) {
my \sum = $ = 0 ; my \part = $ = 0 ; my @sequence = (N^...1) ;
loop { # if ▲OHA ~ ▲OEL
sum = @sequence.sum; # increase 1st term
@sequence[0]*L*L/sum == H*H ?? (@sequence[0] +=1) !! last
}
( [ (0,0), (L,H), (L,0) ], ).Array.append: @sequence.map: -> \chunk {
[ (0,0), (L*part/sum,H), (L*(part+=chunk)/sum,H) ] ;
}
}
.say for UnequalDivider(1000,500,5);
```

- Output:

[(0 0) (1000 500) (1000 0)] [(0 0) (0 500) (400 500)] [(0 0) (400 500) (700 500)] [(0 0) (700 500) (900 500)] [(0 0) (900 500) (1000 500)]

## Wren

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.

```
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()
}
```

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