Efficient Packing Algorithm for Irregular Polygons

Question

I'm looking for a packing algorithm which will reduce an irregular 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). It should also prefer rectangles over triangles where possible.

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

This should run in deterministic time for irregular polygons with less than 100 vertices.

The goal is to produce a "sensible" breakdown of the irregular polygon for a layman.

The first heuristic applied to the solution will determine if the polygon is regular or irregular. In the case of a regular polygon, we will use the approach outlined in my similar post about regular polys: Efficient Packing Algorithm for Regular Polygons

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Milewski

Your diagram is interesting, in that it is not the first example of an 'irregular polygon' that comes to mind. Is it possible that the polygons you and your users want to tessellate can be characterized more narrowly? Such as sides being parallel, and maybe the polygons look like thickened strokes? Could you perhaps supply some more examples of what you're looking for? – Ashmead

Are there any constraints on the segments making up the polygons? For example, they always have sides oriented at multiples of X degrees, or the corners are aways angles multiple of Y degrees? I'm trying to figure out if we can have an exact algorithm (fixed point operations), that doesn't run into this sort of problems: flixxy.com/geometric-puzzle-solution-i.jpg. – Nicolnicola

Answer 1

I don't know if this would give the optimal answer, but it would at least give an answer:

1. Compute a Delaunay triangulation for the given polygon. There are standard algorithms to do this which will run very quickly for 100 vertices or fewer (see, for example, this library here.) Using a Delaunay triangulation should ensure that you don't have too many long, thin triangles.
2. Divide any non-right triangles into two right triangles by dropping an altitude from the largest angle to the opposite side.
3. Search for triangles that you can combine into rectangles: any two congruent right triangles (not mirror images) which share a hypotenuse. I suspect there won't be too many of these in the general case unless your irregular polygon had a lot of right angles to begin with.

I realize that's a lot of detail to fill in, but I think starting with a Delaunay triangulation is probably the way to go. Delaunay triangulations in the plane can be computed efficiently and they generally look quite "natural".

EDITED TO ADD: since we're in ad-hoc heuristicville, in addition to the greedy algorithms being discussed in other answers you should also consider some kind of divide and conquer strategy. If the shape is non-convex like your example, divide it into convex shapes by repeatedly cutting from a reflex vertex to another vertex in a way that comes as close to bisecting the reflex angle as possible. Once you've divided the shape into convex pieces, I'd consider next dividing the convex pieces into pieces with nice "bases", pieces with at least one side having two acute or right angles at its ends. If any piece doesn't have such a "base" you should be able to divide it in two along a diameter of the piece, and get two new pieces which each have a "base" (I think). This should reduce the problem to dealing with convex polygons which are kinda-sorta trapezoidal, and from there a greedy algorithm should do well. I think this algorithm will subdivide the original shape in a fairly natural way until you get to the kinda-sorta trapezoidal pieces.

Weaken

+1 for a solid breakdown answer. My first go-round that's actually what I did. Unfortunately, because it's not specifically designed to create rectangles, it's unusual (except in super special cases) to find any combination of those triangles that create a rectangle. The users complained that the breakdown seemed too complicated. And they are really pushing for rectangles. – Milewski

It sounds like the users are pushing this problem into the realm of "things that sound really easy until you try to implement them". There's a lot of geometry like that. – Weaken

Definitely! No argument about that here! – Milewski

It sounds pretty good. However, how can you ensure that you're not combining triangles into slightly wonky rectangles, i.e. how can you overcome numerical errors when checking for 'rectanglizability'? – Nicolnicola

Mau: there's probably no good way to prevent the numerical errors you're describing; I'd be willing to accept a margin of error. I imagine that a very slight wonkiness would be acceptable as long as it doesn't look too bad visually, but Steve's users would be the final judge of that. Steve: see my edit. – Weaken

Answer 2

I wish I had time to play with this, because it sounds like a really fun problem!

My first thought (from looking at your diagram above) would be to look for 2 adjacent right angles turning the same direction. I'm sure that won't catch every case where a rectangle will help, but from a user's point of view, it's an obvious case (square corners on the outside = this ought to be a rectangle).

Once you've found an adjacent pair of right angles, take the length of the shorter leg, and there's one rectangle. Subtract this from the polygon left to tile, and repeat. When there's no more obvious external rectangles to remove, then do your normal tiling thing (Peter's answer sounds great) on that.

Disclaimer: I'm no expert on this, and I haven't even tried it...

Unlawful

+1 for the idea of subtracting a shape and repeating on the resulting polygon. Could be extended to subtracting a triangle and repeating, if two parallel lines joined by a non-perpendicular line are found (i.e. if two adjacent angles sum to 180 degrees) – Shrewsbury

+1 agreed with Chris. I'm thinking something similar to subtracting off triangles, but extended with some heuristics to clip off rectangles. – Milewski

Chris: ooh, great call on parallel lines => another possibility for a rectangle (with a triangle). – Unlawful