What's an elegant algorithm for fitting differently sized rectangles into a circle?

Question

I have a bunch of rectangles of variable size which I need to fit together roughly into a circle, presumably with the largest ones at the center.

NB. The circle is not of a fixed size - that's just the overall shape I'm after.

This is more like how I'd imagine a lazy human packs (once a piece is in place, it stays.)

They are already ordered by the maximum of their width and height, largest first.

Ideally - and I think this can be guaranteed by the ordering - there would be no gaps at all.

The algorithm I'm struggling with is:

for each rectangle:
    if first:
        place rectangle at origin
        add all edges to edge list
    else:
        for each edge in edge list:
            if edge is long enough to accomodate rectangle (length <= width or height depending on orientation):
                if rectangle placed on this edge does not collide with any other edges:
                    calculate edge score (distance of mid-point from origin)
        use edge with lowest edge score
        place rectangle on edge
        for each of this rectangles edges:
            if edge overlaps one already in the edge list:
                merge or remove edge
            else:
                add to edge list
        remove used edge from edge list
        add unused sections of this edge into edge list

This works alright for the first few rectangles, but the edge merging is pretty hairy and my current method of choosing which section of an edge to use (one end or the other) tends to leave lots of gaps.

Although I think I'd eventually get this method working fairly satisfactorily, it feels like there's a far more elegant (graph?) algorithm that I'm missing.

Answer 1

What do you mean "ordered by size" - length or area? I suppose it must be sorted by max length.

How do you "find the edge closest to the origin which has space for rectangle"? As far as I understand the task, you have rectangles sorted by the length of their longer side. You place the longest one at the origin.

<Loop> Then you take the longest of the remaining rectangles and place it on the long side of the first one / the longest edge of the pile of rectangles. Probably you will place it not in the middle of the edge, but with one corner of the second on one corner of the first rectangle.

As a rule I suggest to always use the west or north end of the longest remaining edge (as you like). Maybe it's even better to always choose the corner with the longer edge.

So you get a new edge, that straightens the corner to which the rectangle has been attached, which now might be the longest remaining edge. </Loop>

Is that what you do? And what seems to be the problem? Do you have a picture of an unwanted result?

Ok, after seeing your example now here some pseudo-python:

class Point(object):
    x, y: Integer
class Rectangle(object):
"""Assuming that the orientation doesn't matter, length>=width"""
    length, width: Integer
class Edge(object):
    from, to: Point
    length: Integer
class Pile_Of_Rectangles(object):
    edges: list of Edges #clockwise
    def add_rectangle(r):
        search longest edge "e1"
        search the longer of the two adjacent edges "e2"
        attach r with its longer side to "e1" at the end, where it adjoins to "e2":
            adjust "e1" so that e1.length = e1.length - r.length
            insert the new edges with length r.width, r.length and r.width into self.edges
            connect the last edge with "e2"

I hope, that makes my reasoning more transparent. This approach should give you no gaps and no collisions, since I reckon that it produces a more or less convex shape (not sure).

Answer 2

Can you please elaborate more on 1. pretty evenly around the center? 2. what is the goal? i.e. do you want to maximize the number of rectangles that can fit or you know that all of them will fit and you want to minimize the wastage of space?

I am not sure how a lazy human will pack. But if I wan to optimize the packing, I will start from the corners and then come to the center.