Optimization (min) Problem

[Illuminator]

I belive this qualifies as a backpack problem for those of you familliar with NP problems.

Take n arbitrary triangles. You are given the (u,v) coordinates of each point for a triangle. Now find the smallest rectangle that those triangles can be placed in.

I'm making a 3d modeling program where you can paint the model directly in 3d. I would like to minimize the size and amount of files used. I dont want to save a complete image file for each triangle in the model. I have figured out basic non optimized solutions for this already. I was wondering if anyone has any ideas (or experience) for this optimization.

[kedaman]

Sort the triangles by the length of the longest side (I assume it's better to start off with the most awkward pieces)

The algoritm picks out triangles from a pool in all possible combinations starting off with the sorted order.

For each triangle (sorted from length of longest side), for each available side of the already connected triangles (sorted from shortest side) for each side (sorted from longest side) on the triangle picked, for each end of the source side triangle, for each end of target side triangle, do the recursive call to connect.

The triangles connect corner to corner, side connected

The recursion should terminate when
1. The new triangle overlaps another triangle
2. The area is larger than which the current smallest rectangle for a full triangle combination found

When these are passed, all new sides added to the list of available sides, the connected sides could either exclude each other or have one split the other in two and exclude itself.

The list of available sides are sorted and then the next recusion is done.

There is a permutation issue, although the 2 termination inhibitors should short circuit most impossible cases.