如何优雅地将不同大小的矩形适配到一个圆形中？

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

这对于前几个矩形运作良好，但是边缘合并非常棘手，我目前选择使用哪个边缘部分的方法（一端或另一端）往往会留下很多间隙。

虽然我认为最终我会让这种方法相当令人满意，但感觉有一种更优雅的（图？）算法我还没有掌握。

- Long Ears

---

小修正：尽管您不寻求最佳解决方案，但实际上这是一个二维装箱问题。符合您所有要求的最简单算法是将每个下一个矩形放置在上一个矩形的右侧，然后在其周围画一个半径为MAX_INTEGER的圆形 :) 但这可能不是您要寻找的。您可能正在寻找一种良好的近似算法，以获得体面（虽然不是最优）的解决方案。该实现看起来像是最佳适应度递减方法的变体（请参见Bin Packing的维基百科）。 - Geoffrey De Smet

@Geoffrey 谢谢，你说得对，我已经更新了问题。我加上免责声明是因为我还没有看到这个应用程序，但它占据了我的搜索结果。现在我会更有希望地看待它 :) - Long Ears

Answer 1

你说的“按大小排序”是指长度还是面积？我猜想它必须按最大长度排序。

你如何“找到最靠近原点且有空间容纳矩形的边缘”？就我理解任务，你已经按长边的长度对矩形进行了排序。你将最长的矩形放在原点上。

然后，你从剩余的矩形中选择最长的一个，并将其放置在第一个矩形的长边/矩形堆的最长边上。可能你不会将其放置在边的中心，而是将第二个矩形的一个角落与第一个矩形的一个角落重合。

通常建议始终使用最长剩余边缘的西端或北端（根据您的喜好）。也许总是选择具有更长边的角落会更好。

这样，你就得到了一条新的边缘，使得矩形附着的角变直，现在可能是最长的剩余边缘。

这就是你做的吗？有什么问题吗？你有一个不想要的结果的图片吗？

好的，在看到你的示例之后，这里是一些伪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"

我希望我的论述更加透明。这种方法应该不会出现任何空缺和冲突，因为我认为它会产生一个更或多或少凸形的形状（不确定）。

- jammon

---

感谢您的反馈，我已经更新了问题以澄清排序和边缘选择。我将尝试说明当前和期望的结果。 - Long Ears

为什么不直接将下一个矩形愚蠢地添加到最长的边上，无论矩形堆叠在哪里，最后将所有矩形偏移，使堆叠的中心位于原点？ - jammon

如果我理解你的意思正确，那仍然需要跟踪边缘并合并它们，我不知道它如何产生一个大致圆形的堆。现在已经更新了问题，并附上了插图。 - Long Ears

谢谢，伪代码非常感谢。我会尝试一下。 - Long Ears

Answer 2

您能否请更详细地解释以下问题： 1. 什么是“pretty evenly around the center”？ 2. 目标是什么？即要最大化可放置的矩形数量，还是已知所有矩形都能放置，希望尽量减少空间浪费？

我不确定懒惰的人会如何打包。但如果我想优化包装，我会从角落开始，然后到达中心。

- Sumod

---

我提前提交了那个评论，很抱歉。更新问题以澄清这些要点。 - Long Ears