平铺(可扩展)堆叠算法

发布于 2024-10-20 19:55:27 字数 831 浏览 7 评论 0原文

问题就在这里。我有尺寸为 1 的矩形画布。因此它的坐标系为 (0.0 ... 1.0 - x 和 0.0 ... 1.0 - y)。

我也有一些瓷砖。瓷砖也是矩形的。它们具有不同的尺寸,并且瓷砖的数量是可变的。

我想在矩形画布中堆叠图块,从0.0到1.0(从左到右,从上到下):

1)图块必须适合画布(但填充尽可能多的空间)

2)必须缩放图块(如果它们不适合),每个图块应缩放相同的量(它们必须保持相同的比例)。

3) 想象你手里有这个“图块”,然后将它们一个接一个地放入画布中

4) 它几乎像“TreeMap 算法”,但是 - 图块的形状必须相同(矩形)并且我不需要填充画布的所有空间

“这就是我想要得到的”

有没有人可以向我展示任何类似 C 的语言(C、C++、Java、C#)的算法?

*我尝试过这个。

1)我计算了瓷砖的面积,然后我计算了瓷砖面积的总和(例如:我有两个瓷砖,一个面积为2,另一个面积为1,它们意味着我的总和为3)

2)然后我计算每个图块在“面积总和”中的“比例”(例如:2/3 和 1/3)

3) 然后通过 Math.sqrt(x) 计算矩形图块的大小(例如:Math.sqrt( 2/3))

4) 然后一张一张地绘制图块...

但这并不总是有效。有时我的瓷砖会脱离画布..*

Here is the problem. I have rectangular canvas that have size of 1. So it have coordinate sistem of (0.0 ... 1.0 - x and 0.0 ... 1.0 - y).

I also have some tiles. Tiles are also rectangles. They have diffrent size and amount of tiles is a variable.

I want to stack tiles in rectangular canvas, from 0.0 to 1.0 (from left to right, from top to bottom):

1) tiles have to fit in canvas (but fill as much space as they could)

2) tiles have to be scaled (if they don't fit), each tile should be scaled by the same amount (they have to remain same proportions).

3) imagine that you have this 'tiles' in your hand, and you placing them into this canvas one after another

4) it almost like "TreeMap algorithm" but - shape of tiles have to be the same (rectangles) and i don't need to fill all space of canvas

here is what i want to get

Is there anybody who can show me an algoritm in any C alike language (C, C++, Java, C#)?

*I tried this.

1) i calculated area of tile, then i calculate a sum of tile's areas (for example: i have two tiles, one have area of 2, other area of 1, them it's mean i have total sum of 3)

2) then i calculate what "proportion" each tile have in "total sum of areas" (for example: 2/3 and 1/3)

3) then calculate size of rectangle tile by Math.sqrt(x) (for example: Math.sqrt(2/3))

4) then draw tile one by one...

But this dosen't work always. Sometimes i get tiles to be out of canvas..*

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

傲娇萝莉攻 2024-10-27 19:55:28

我不确定这是否是您想要的,但您可以查看 TreeMap 算法。

TreeMap

维基百科定义

C++ 实现

I am not sure if it's what you want but you can look at TreeMap algorithm.

TreeMap

Wikipedia definition

C++ implementation

情徒 2024-10-27 19:55:27

这可能看起来是一个包装问题,但是如果我们尝试完全按照它所描述的方式解决这个问题,则事实并非如此。换句话说,没有解决方案,因为问题的描述再次没有问题。如果我们只有一个盒子和一组固定的瓷砖,并且要求它们都必须适合盒子,那么就没有优化的空间。
我可以看到几个相关的优化问题:

1. 给定一组固定的瓷砖,必须将其包装到相同或不同尺寸的盒子中,找到最佳包装顺序,以便使用最少数量的盒子。

2. 给定任意大小的单个盒子和一组图块,找到可以放入盒子中的最佳(最大)图块集。

3. 给定一个盒子和一组瓷砖 - 回答问题是否可以将它们放入盒子中。

您想解决其中哪一个问题?

现在设置问题的方式是没有意义的,因为无论你以哪种顺序将瓷砖放入盒子中,它们总是会使用相同的空间,无论它们如何排列,当然,只要它们全部适合。

It may appear that this is a packing problem, however if we try to solve this problem exactly as it described it is not. In other words there is no solution because, again, there is no problem in a question as it is described. If we have ONLY ONE box and fixed set of tiles and requirement that they ALL must fit into box there is no room for optimization.
I can see several related optimization problems:

1. Given fixed set of tiles that must be packed into boxes of same or different sizes find optimal packing order so that minimal number of boxes is used.

2. Given single box of an arbitrary size and set of tiles find optimal (maximum) set of tiles that can be fit into a box.

3. Given a box and set of tiles - answer the question if it is possible to fit them into a box or not.

Which one of these are you trying to solve?

The way problem is set right now is meaningless, because no matter which order you place the tiles in the box they will always use same amount of space no matter how they are arranged, as soon as they all fit in of course.

你是年少的欢喜 2024-10-27 19:55:27

尝试蒙特卡罗算法:

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

所有随机图块选择都应按图块面积进行加权,以便您倾向于首先放置较大的图块。

Try a monte-carlo algorithm:

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

All random tile selections should be weighted by the tile's area so that you tend to place the larger ones first.

咆哮 2024-10-27 19:55:27

我不认为这是一个(装箱)装箱问题,因为我为一维装箱问题编写了一个问题。我认为这里的问题是通过 2D-cutting-stock 问题解决的,也许还有 2D-bin-packing 问题。您想要的也是尝试背包问题。这个问题很难解(NP),无解。这有点像旅行推销员问题,解决方案的数量与城市的数量呈指数关系。如果您可以将复杂度降低为一维问题,您可以尝试我在 phpclasses.org 上的装箱算法。

I don't think this is a (bin)-packing problem because I wrote one for the 1D bin-packing problem. I think the problem here is solved by the 2D-cutting-stock problem, maybe there is also a 2D-bin-packing. What you want is to try the knappsack-problem too. This problem is hard to solve (NP) and there is no solution. It's a bit like the Travelsalesman problem where the number of solution is exponential to the number of cities. If you can reduce the ccomplexity to a 1D problem you may try my bin-packing algorithm at phpclasses.org.

冷弦 2024-10-27 19:55:27

正如其他人指出的那样 - 问题描述不是很清楚。但我假设您可以根据需要缩放每个图块(至少您的示例表明图块缩放是可能的)。所以我的解决方案很简单(但可能不是您想要的也不是最佳的):

  • 按因子缩放每个图块:
    EDGEspace / (EDGEtile * N ½)
  • 将每个图块放置在当前行中,如果图块超出空间限制 - 前进到下一行。

这里N是最接近完全平方大于或等于总数的瓷砖。

ps 如果您需要在图块之间留出一些间距 - 只需将上述比例因子设置得小一点即可。

希望有帮助。

As others pointed - problem description is not very clear. But i'm assuming that you can scale each tile as you need (at least your examples shows that tile scaling is possible). So my solution will be simple (but maybe not what you want nor optimal):

  • Scale each tile by factor :
    EDGEspace / (EDGEtile * N ½)
  • Place each tile in current row, if tile gets out of space limits - advance to next row.

Here N is nearest perfect square greater or equal to the total number of tiles.

p.s. If you need some spacing between tiles - just make above scale factor a little bit smaller.

Hope that helps.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文