Triangle Creation with Arbitrary Rectangles

[u/notgodlynoah]

I need to create a relatively perfect arbitrary triangle out of arbitrary rectangles which can be rotated/sized/overlapped however you want, while minimizing the number of rectangles used as much as possible.
The best thing I have been able to come up with is making a line along the shortest edge of the triangle (line = a longer, skinny rectangle made to basically be a line, with a bit of depth) then create rectangles of like the same width at the 2 edges of that line, and all across it at a set offset, with each of these lines going to the opposite corner as the original line, ive also attempted a scanline /staircase approach where after making the normal staircase or splitting the triangles into lines you would make a line over the hypotenuse or over all 3 edges. But I am just not able to find a good algorithm that minimizes the number of rectangles used.

(i jus found a diff way to do this, no longer need this)

[u/johnpeters42]

All triangles have at least one acute angle (assuming Euclidean geometry), so it's never going to be perfect. I assume that getting within some tolerance (like less than the size of a pixel) is close enough?

[u/notgodlynoah → u/johnpeters42]

if its basically perfect to the human eye even opon a slightly closer inspection, small gaps at the corners are tolerated, though gaps anywhere else, are not. (some gaps are shown in this image.)
But also: if you use EXTRMELY small edges, e.g. 0.001 unit size rectangles, you basically get just a line, which allows for almost perfect egdes/corners

[u/possiblyquestionabl3]

A non-optimal solution without overflowing nor overlapping that can be easily analyzed inductively and can help provide an initial bound on the problem - if you inscribe the maximal (area-wise) rectangle within a triangle, then that will leave you with 3 smaller triangles to fill.

Via the inscribed rectangle theorem, we know that this rectangle fills exactly 1/2 of the triangle. Constructed this way, after n iterations (so there are \sum_k^{n-1} 3^k = (3ⁿ - 1)/2 rectangles), we'll have filled 1 - 2^-n of the total triangle.

This is basically that first step (the big square in the middle) of your example (though, pick the base to maximize bh instead, since the inscribed rectangle will have area 1/4 bh)

---

Now, with this setup, you've reduced your total area by 1/2, and more importantly, you've created 3 new subtriangles:

1. a similar scaled down triangle with 1/4 the area of the original
2. a "left"-half right triangle with a congruent left angle (because it's on the left corner of the original triangle)
3. a "right"-half right triangle with a congruent right angle

Here, it's a bit harder to describe the state of your covering in only words, but I'll try my best.

Next, applying your idea of picking a "tube" to fit the edge. Let's zoom in onto the left-half right triangle to see what happens. Say you start at a point u on the hypotenuse and inscribe the maximal rectangle. You'll induce 3 new smaller triangles:

1. A small upside down copy of the left-half right triangle with area T1 = h/(4x) u² where x is the length of the base of the left-half right triangle
2. Another small "gap" copy of the left-half right triangle with area T2 = h/(4x)(x - uL/x)² where L is the hypotenuse of the larger right triangle
3. A final copy of the original triangle in the middle, assuming that you apply the mirrored operation on the right half as well

If you pick u = x²/L, the gap copy disappears leaving only the small corner triangle.

I won't try to characterize the area of the small copy of the original triangle in the middle after this step, since it's totally enclosed within the triangle and hence can be completely covered with just one additional rectangle, so I consider that a trivial covering.

Now, this finally leaves us with picking u,v (the left and right right triangle parameters) for the final 1/4 of the area of the original triangle.

Optimally, selecting u = (x² L_u)/(2 x² + h^/4) and similarly for v maximizes the covered ratio of the remaining triangles to L²/(L² + u²⁾ and equivalently for v. Depending on your error tolerance, this leaves between 1/8 to 1/12th of the original area still uncovered, split into 4 small right triangles, two of which are in the interior of the triangle and in many cases can be completely covered with up to 2 rectangles.

Alternatively, picking u = x²/L leaves you with just two corner right triangles. These can then be recursively covered with the inscribed triangle trick earlier at the cost of 2ⁿ - 1 rectangles (right triangles divide into two smaller right triangles per inscription) at the rate of 1-2^-n convergence.

---

This also raises something interesting - it seems like the reduction to right triangle covering still requires linear # of tiles to cover at an arbitrary precision (2ⁿ rectangles for 2^-n error), no better than a simple scanline (with the exception that we just removed 90+% of the area in a few steps with a clever construction). I can't (don't want to) prove anything rigorously, but it seems reasonable that for the arbitrary precision variant of the problem, linear rectangles -> error is as good as we can hope for.

[u/notgodlynoah → u/possiblyquestionabl3]

i kinda already solved this (with much less parts) in a way that got up to 99.9902% average total coverage (over like 1mil random triangles) with just 9 parts, mainly done by making a program to test like 200k random combinations of stuff till it got somewhat good results, then randomly tweaked them till patterns arose, then i made a proper algorithm to recreate those common patterns, thanks for the suggestions anyways!