将不同大小的矩形优雅地放入圆内的算法是什么？

Question

我有一堆大小不一的矩形，我需要把它们大致放进一个圆形里，最大的矩形应该放在中间。

注意，这个圆形并不是固定大小的——我只是想要这样的整体形状。

这更像是一个懒惰的人在打包东西（一旦放好一个，就不动了）。

这些矩形已经按照它们的宽度和高度的最大值排序，最大的在前面。

理想情况下——我觉得通过这种排序可以保证——应该不会有任何空隙。

我现在遇到困难的算法是：

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

这个算法在处理前几个矩形时效果还不错，但在边缘合并时就比较麻烦，我现在选择使用边缘的哪个部分（一个端点或另一个端点）的方法，往往会留下很多空隙。

虽然我觉得最终可以让这个方法工作得还不错，但我感觉还有一种更优雅的（图形？）算法我没有想到。

Answer 1

你能再详细解释一下吗？

1. “在中心附近差不多均匀”是什么意思？

2. 你的目标是什么？也就是说，你是想让能放下的矩形数量尽可能多，还是你知道所有的矩形都能放下，但想尽量减少空间的浪费？

我不太确定一个懒惰的人会怎么打包。不过如果我想优化打包的话，我会先从角落开始，然后再往中心靠近。

Answer 2

你说的“按大小排序”是什么意思？是指长度还是面积？我想应该是按最长边的长度来排序。

你是怎么“找到离原点最近的边，并且能放下矩形的”？根据我对这个任务的理解，你有一些矩形，它们是按最长边的长度排序的。你把最长的那个放在原点上。

<Loop> 然后你取剩下的矩形中最长的一个，把它放在第一个矩形的长边上，也就是那堆矩形的最长边上。可能你不会把它放在边的中间，而是把第二个矩形的一个角放在第一个矩形的一个角上。

通常我建议总是使用剩下的最长边的西端或北端（随你喜欢）。也许总是选择那个角的长边会更好。

这样你就得到了一个新的边，这个边会把矩形连接的角变得更直，而这个角现在可能就是剩下的最长边。

</Loop>

这就是你要做的事情吗？那问题出在哪里呢？你有不想要的结果的图片吗？

好的，看到你的例子后，这里有一些伪代码，像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"

我希望这能让我的思路更清晰。这个方法应该不会有空隙和碰撞，因为我认为它会产生一个或多或少是凸形的形状（不太确定）。