5

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

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

这更像是我想象的懒惰的人类包装（一旦一块到位，它就会留下来。）

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

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

我正在努力的算法是：

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

这对于前几个矩形来说没问题，但是边缘合并非常麻烦，而且我目前选择使用边缘的哪一部分（一端或另一端）的方法往往会留下很多间隙。

尽管我认为我最终会让这种方法相当令人满意地工作，但感觉就像我缺少一种更优雅的（图形？）算法。

4

2 回答 2

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"

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

于 2011-02-23T06:54:14.207 回答
0

您能否详细说明 1. 在中心周围相当均匀？2. 目标是什么？即你想最大化可以适应的矩形的数量还是你知道所有的矩形都适合并且你想最小化空间的浪费？

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

于 2011-02-23T06:30:05.297 回答