Efficient Packing Algorithm for Regular Polygons

Question

I'm looking for a packing algorithm which will reduce a regular polygon into rectangles and right triangles. The algorithm should attempt to use as few such shapes as possible and should be relatively easy to implement (given the difficulty of the challenge).

If possible, the answer to this question should explain the general heuristics used in the suggested algorithm.

Absorbed

is this for an algorithms class or a computer graphics class? – Unidirectional

It's not for a class. I'm not in school. – Absorbed

In fact, i might be willing to give someone who can answer the question well a job offer if they can program for the iPhone, Mac desktop, and .net. ;) – Absorbed

thanks, i work for myself right now, but i'll keep you in mind. :-) – Unidirectional

Answer 1

I think the answer is fairly simple for regular polygons.

Find an axis of symmetry, and draw a line between each vertex and its mirror. This divides the polygon into trapezoids. Each trapezoid can be turned into a rectangle and two right triangles.

Hunker

You could gain some extra credit by proving that this produces the minimum number of tiles. :) – Runnerup

I now believe this is actually optimal :-) – Terrorism

No. It is not always optimal. Take for example a regular hexagon with two sides parallel to the x=0 axis. Then this algorithm generates 2 rectangles and 4 right triangles, but 1 rectangle and 4 triangles would be enough. Nonetheless the solution is probably good enough and easy to implement. – Creepy

This does generate 1 rectangle + 2 triangles if you are careful enough to 'split' the polygon (generate a rectangle) along the longest chord first. – Terrorism

Nice! Going to wait just a bit to see if anyone else weighs in, but this looks great! PS I plan on asking the same question but for irregular polygons with a 200 point bounty. – Absorbed

be careful with regular but odd-numbered-vertex polygons, the algorithm changes slightly. however, this will generally provide the most rectangles with large area. it will also create small triangles on the edges, if that matters for you. let me know if you ned one for irregulars - my post was more directed at that... – Unidirectional

@Terrorism The OP specifies that the triangles need to have a right angle (i.e. 90 degrees). Hence you can't split a regular hexagon into one rectangle and 2 right triangles. There are other cases where the algorithm comes up with one extra rectangle, e.g. a rectangular octagon aligned such that the corners are at at an angle 0, 45, 90 etc away from the center. Again, this may not matter if simplicity of the solution is important. – Creepy

@abc: Correct, I meant 4 triangles. – Terrorism

One nice property is that this algo returns shapes that are axis aligned. I'm not sure this is a requirement, but often it is a helpful property. – Creepy

One simple case where this algorithm is not optimal is for a right triangle lying on its hypotenuse. But I like its simplicity, +1. – Sall

Answer 2

It's not specifically rectangles + right triangles, but a good research point for looking into tesselating polygons is Voronoi Diagrams and Delaunay Triangulations and here and here.

In fact, if "just right triangles" is good enough, these are guaranteed to triangulate for you, and you can always split any triangle into two right triangles, if you really need those. Or you can chop off "tips" of triangles to make more right triangles and some rectangles out of the right-triangles.

You can also try ear-clipping, either by sweeping radially, if you know you have fairly regular polygons, or by "clipping the biggest convex chunk" off. Then, split each remaining triangle into two to create right triangles.

_{(source: eruciform.com)}

You could try to make less breaks by sweeping one way and then the other to make a trapezoid and split it differently, but you then have to do a check to make sure that your sweep-line hasn't crossed another line someplace. You can always ear-clip, even with something practically fractal.

However, this sometimes creates very slim triangles. You can perform heuristics, like "take the biggest", instead of clipping continuously along the edge, but that takes more time, approaching O(n^2). Delaunay/Vornoi will do it more quickly in most cases, with less slim triangles.

Unidirectional

Absolutely must be rectangles and right triangles. I know it sounds strange, but it's a user requirement. – Absorbed

updated. you can turn any triangle into right triangles and rectangles pretty easily. – Unidirectional

Delaunay triangulations aren't ideal here because they introduce additional, unnecessary points in the middle. Each of those internal points can be "dragged" to an adjacent polygon vertex and you are left with a smaller set of triangles. – Sall

Answer 3

You can try "cuting out" the largest rectangle that can fit in the polygon, leaving behind some leftovers. Keep repeating the cutting out of rectangles on the leftovers, until you end up with triangular pieces. Then, you can split them into two right triangles if necessary. I do not know if this will always yield solutions that will give you the least amount rectangles and right triangles.

Brummell

I think this is not a good idea either: eating away as much area as possible with the first rectangle is not going to leave you with the "easiest" shape afterwards. – Terrorism

it wasn't clear what his requirements were. least total shapes or most area in least shapes... – Unidirectional

For regular polygons though, it would still give you "nice" shapes. Again, I don't know if this will give you the "most optimal" solutions. – Brummell