7

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.

eruciform
  • 7,680
  • 1
  • 35
  • 47
Steve
  • 31,144
  • 19
  • 99
  • 122

3 Answers3

8

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.

https://content.screencast.com/users/Tom/folders/Jing/media/04cb9283-7fc0-4ccd-99ad-a4e056f81b23/2010-06-21_0056.png

Community
  • 1
  • 1
Tom Sirgedas
  • 3,208
  • 20
  • 17
  • You could gain some extra credit by proving that this produces the minimum number of tiles. :) – Svante Jul 21 '10 at 09:33
  • 1
    I now believe this is actually optimal :-) – Mau Jul 21 '10 at 12:48
  • 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. – abc Jul 21 '10 at 13:19
  • This does generate 1 rectangle + 2 triangles if you are careful enough to 'split' the polygon (generate a rectangle) along the longest chord first. – Mau Jul 21 '10 at 13:38
  • 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. – Steve Jul 21 '10 at 13:39
  • 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... – eruciform Jul 21 '10 at 14:11
  • 1
    @Mau 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. – abc Jul 21 '10 at 14:13
  • @abc: Correct, I meant 4 triangles. – Mau Jul 21 '10 at 14:14
  • 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. – abc Jul 21 '10 at 14:43
  • One simple case where this algorithm is not optimal is for a right triangle lying on its hypotenuse. But I like its simplicity, +1. – j_random_hacker Jul 22 '10 at 06:50
1

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.

polygon
(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.

Community
  • 1
  • 1
eruciform
  • 7,680
  • 1
  • 35
  • 47
  • Absolutely must be rectangles and right triangles. I know it sounds strange, but it's a user requirement. – Steve Jul 21 '10 at 03:41
  • updated. you can turn any triangle into right triangles and rectangles pretty easily. – eruciform Jul 21 '10 at 03:44
  • 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. – j_random_hacker Jul 21 '10 at 06:24
0

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.

In silico
  • 51,091
  • 10
  • 150
  • 143
  • 1
    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. – Mau Jul 21 '10 at 12:30
  • it wasn't clear what his requirements were. least total shapes or most area in least shapes... – eruciform Jul 21 '10 at 14:13
  • 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. – In silico Jul 21 '10 at 19:58