将不同大小的矩形拟合成圆形的优雅算法是什么？

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

“按大小排序”是什么意思 - 长度或面积？我想它必须按最大长度排序。

如何“找到最接近原点且有矩形空间的边缘”？据我了解该任务，您有按长边长度排序的矩形。您将最长的放置在原点。

<循环>
然后，取出剩余矩形中最长的一个，并将其放置在第一个矩形的长边/矩形堆的最长边上。您可能不会将其放置在边缘的中间，而是将第二个矩形的一个角放置在第一个矩形的一个角上。

作为一项规则，我建议始终使用最长剩余边缘的西端或北端（根据您的喜好）。也许总是选择边缘较长的角会更好。

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

你就是这么做的吗？问题出在哪里？您有不想要的结果的图片吗？

好吧，在看到你的例子后，现在有一些伪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"

我希望，这使我的推理更加透明。这种方法应该不会给你带来间隙和碰撞，因为我认为它会产生或多或少的凸形（不确定）。

Answer 2

您能否详细说明一下
1. 围绕中心相当均匀？
2. 目标是什么？即，您是否想要最大化可容纳的矩形数量，或者您知道所有矩形都适合并且您希望最大程度地减少空间浪费？

我不知道一个懒惰的人会如何收拾行李。但如果我想优化包装，我会从角落开始，然后来到中心。