Forming triangles

Question

Suppose we are given a set of triangles (each triangle being a set of three integers which are side lengths). Is there any (reasonable) algorithm to check whether the shapes can be put together to form one big triangle?

By put together, I mean placed on a 2D plane so that - no two triangles overlap. - every portion of every triangle border overlaps with that of some other triangle, or forms the border of the large triangle. - the large triangle has no empty space leftover.

For 3-4 triangles, it makes sense to test cases manually as done here. Is there any way of automatically generating these cases? Also some cases require calculation of angles. Is that to be done using the cosine rule or is there a better approach that won't require floating point (and hence imprecise) calculations.

P.S. This is not a homework problem; I'm just curious.

Are you trying to assemble some kind of mesh from the given triangles? — Codor, Mar 13 '17 at 11:55
I meant a [polygon mesh](https://en.wikipedia.org/wiki/Polygon_mesh), a grid that can be obtained by rearranging the polygons of a three-dimensional object on a surface. — Codor, Mar 13 '17 at 12:02
@Codor It's clearer in the link provided...its like pieces of paper being placed together like in a tangram for example — ghosts_in_the_code, Mar 13 '17 at 12:02
angles and float - you could avoid trigonometric functions for most test. e.g. you can test for supplementary angles in a 2-triangles-problem by checking height equality. always check without perfoming square roots. — stefan, Mar 13 '17 at 20:23

score 1 · Answer 1 · answered Mar 13 '17 at 20:35

that sounds like a hard problem. however you can do some checks to prove it impossible on a given set. the area (see Heron) of the big one must be achieved by three sides which are sums of given sides. angles must sum to either 180 or 360 or one of thre corners. i'm sure you could work out some more tests. if you cannot prove it impossible you could set up a search for fitting sides and angles.

score 1 · Answer 2 · answered Mar 14 '17 at 05:40

Any algorithm to do this will have a time complexity like n⁷ or worse, so a large input is always going to be problematic. That being said, I suggest something like this:

Find and mark identical triangles (so that you don't check identical solutions multiple times).
Find and mark equilateral triangles (these don't have to be rotated).
Calculate the angles of each triangle (this requires two cosines and two square roots).
Calculate the area of each triangle (this requires a sine or a square root).
Sum the areas to find the total area of the large triangle.

With these preparations, we're still in linear time. But then:

Try every combination of triangles and every rotation of them as the base of the large triangle. (red triangles)
Try all orderings of the triangles so that there are no overlaps.
Use the length of this base and the area to calculate the height of the large triangle. (blue line)
Try every combination of sides of the leftover triangles that is greater than or equal to the height as the second side. (green triangles)
Try all orderings of the triangles so that there are no overlaps with eachother, or with the triangles in the base (a gap between the corner triangles is ok).
Calculate the length of the third side of the large triangle.
Try every combination of sides of the leftover triangles to form the third side of the large triangle. (yellow triangles)
Try all orderings of the triangles so that there are no overlaps with eachother, or with the triangles in the base or second side (a gap between the corner triangles is ok).
Find the corners of the leftover space in the middle of the large triangle, and try every combination of corners of leftover triangles to fill these corners. (blue triangles)
If the last leftover triangle fits the last leftover space, you've found a solution.

Counting the number of times I've used the words "try every" will give you an idea of the time complexity; of course, many combinations will be found not to work early on, so the actual time it takes will depend very much on the specific input.

Forming triangles

2 Answers2