Divide a rectangle into a number of unequal triangles: Difference between revisions
m (→{{header|Raku}}: fix a mistake) |
(→{{header|Raku}}: revised as using primes is an overkill) |
||
Line 418: | Line 418: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
All triangle vertices lie over the lengths and corners of the rectangle and their locations are defined by ratios among |
All triangle vertices lie over the lengths and corners of the rectangle and their locations are defined by ratios among unique+positive integers drawn from two sequences. |
||
<lang perl6># 20220123 Raku programming solution |
<lang perl6># 20220123 Raku programming solution |
||
Line 425: | Line 425: | ||
if N == 3 { return (0,H), (0,0), ((2/5)*L,H), (L,0), (L,H) } |
if N == 3 { return (0,H), (0,0), ((2/5)*L,H), (L,0), (L,H) } |
||
my @ |
my @base = (1..N/2) and my @roof = ((N/2+1).Int..N) ; # .pick(*) |
||
⚫ | |||
my @base = @primes[0..N/2-1] and my @roof = @primes[N/2..*]; # add .pick(*) |
|||
⚫ | |||
my ($bPartial,$rPartial) = [ @base, @roof ]>>.shift ; |
my ($bPartial,$rPartial) = [ @base, @roof ]>>.shift ; |
||
my @vertices = (0,H), (0,0), (($rPartial/$rTotal)*L,H), ; |
my @vertices = (0,H), (0,0), (($rPartial/$rTotal)*L,H), ; |
||
for ^+@base { |
for ^+@base { |
||
Line 446: | Line 444: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
((0 500) (0 0) ( |
((0 500) (0 0) (181.818182 500)) |
||
((0 0) ( |
((0 0) (181.818182 500) (166.666667 0)) |
||
(( |
((181.818182 500) (166.666667 0) (409.090909 500)) |
||
(( |
((166.666667 0) (409.090909 500) (500 0)) |
||
(( |
((409.090909 500) (500 0) (681.818182 500)) |
||
((500 0) ( |
((500 0) (681.818182 500) (1000 0)) |
||
(( |
((681.818182 500) (1000 0) (1000 500)) |
||
</pre> |
</pre> |
||
Revision as of 17:10, 25 January 2022
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> <lang julia>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()
</lang>
- 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))
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.
<lang python> 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))
</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))]
Raku
All triangle vertices lie over the lengths and corners of the rectangle and their locations are defined by ratios among unique+positive integers drawn from two sequences. <lang perl6># 20220123 Raku programming solution
sub UnequalDivider (\L,\H,\N where N > 2) {
if N == 3 { return (0,H), (0,0), ((2/5)*L,H), (L,0), (L,H) } my @base = (1..N/2) and my @roof = ((N/2+1).Int..N) ; # .pick(*) my ($bTotal,$rTotal) = [ @base, @roof ]>>.sum ; my ($bPartial,$rPartial) = [ @base, @roof ]>>.shift ; my @vertices = (0,H), (0,0), (($rPartial/$rTotal)*L,H), ;
for ^+@base { @vertices.push: ( ($bPartial/$bTotal)*L , 0 ); if +@base == 1 { # last segment, the rest just by hand return N %% 2 ?? @vertices.append: (L,H) , (L,0) !! @vertices.append: (L*(1-@roof[*-1]/$rTotal),H), (L,0), (L,H) } ($bPartial,$rPartial) <<+=<< [ @base, @roof ]>>.shift ; @vertices.push: ( ($rPartial/$rTotal)*L , H ); }
}
.say for UnequalDivider(1000,500,7).rotor( 3 => -2 );</lang>
- Output:
((0 500) (0 0) (181.818182 500)) ((0 0) (181.818182 500) (166.666667 0)) ((181.818182 500) (166.666667 0) (409.090909 500)) ((166.666667 0) (409.090909 500) (500 0)) ((409.090909 500) (500 0) (681.818182 500)) ((500 0) (681.818182 500) (1000 0)) ((681.818182 500) (1000 0) (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. <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]]