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

Question

我有一堆大小可变的矩形，我需要将它们大致拼成一个圆，大概最大的圆在中心。

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

这更像是我想象中的一个懒惰的人如何打包(一旦一 block 到位，它就会留下来。)

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

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

我遇到的算法是:

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"

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