I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

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.

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 Colorsusing Luxorusing Primesusing Random mutable struct Triangle    v1::Point    v2::Point    v3::Pointend 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 trianglesend colors = shuffle(collect(Colors.color_names))idx = 1Drawing(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 += 1end 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

Library: Phix/pGUI
Library: Phix/online

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_triand 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 randomfrom typing import List, Union, Tuple  # TypesNum = 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 ntop 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 #%% Helpersdef 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

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.

import "random" for Randomimport "./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 formulavar 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]]