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

Question

我有一堆可变大小的矩形,我需要将它们大致组合成一个圆圈,大概是中心的最大的矩形.

NB.圆圈的大小不是固定的 - 这只是我追求的整体形状.

这更像是我想象一个懒惰的人类包(一旦一件就到位,它就会停留.)

它们已按其宽度和高度的最大值排序,最大值.

理想情况下 - 我认为这可以通过订购得到保证 - 根本没有差距.

我正在努力的算法是:

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

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

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

<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"

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