Divide a rectangle into a number of unequal triangles

From Rosetta Code
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 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

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

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