Divide a rectangle into a number of unequal triangles: Difference between revisions
Divide a rectangle into a number of unequal triangles (view source)
Revision as of 22:50, 18 December 2021
, 2 years ago→{{header|Wren}}: Added a further check that the areas of all triangles are different.
(Added Wren) |
(→{{header|Wren}}: Added a further check that the areas of all triangles are different.) |
||
Line 253:
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|
Line 294 ⟶ 310:
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:")
System.print(divideRectIntoTris.call(w, h, n).join("\n"))▼
// make sure all triangles have different areas
while (true) {
var areas = []
for (tri in tris) areas.add(area.call(tri))
if (Lst.distinct(areas).count == n) {
System.print(tris.join("\n"))
break
}
}
System.print()
}</lang>
| |||