包装矩形以实现紧凑表示

发布于 2024-07-06 13:56:52 字数 303 浏览 7 评论 0原文

我正在寻找解决以下问题的指针：我有一组矩形，其高度已知，x 位置也已知，我想以更紧凑的形式打包它们。通过一点绘图（其中所有矩形的宽度相同，但宽度在现实生活中可能会有所不同），我想要，而不是。

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

就像是。

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

所有提示将不胜感激。我不一定在寻找“最佳”解决方案。

原文

I am looking for pointers to the solution of the following problem: I have a set of rectangles, whose height is known and x-positions also and I want to pack them in the more compact form. With a little drawing (where all rectangles are of the same width, but the width may vary in real life), i would like, instead of.

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

something like.

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

All hints will be appreciated. I am not necessarily looking for "the" best solution.

分享到QQ

分享到微博

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

发布评论

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

嘿嘿嘿 2024-07-13 13:56:52

您的问题是一个更简单的变体，但您可能会在阅读有关为“装箱”问题开发的启发式方法时获得一些提示。关于这一点已经有很多文章，但是此页面是一个很好的开始。

回复收藏 0 原文

三五鸿雁 2024-07-13 13:56:52

Topcoder 举办了一场竞赛来解决此问题的 3D 版本。获胜者在此处讨论了他的方法，它可能对您来说是一本有趣的读物。

回复收藏 0 原文

绝不放开 2024-07-13 13:56:52

这些矩形的高度都相同吗？如果是，并且问题只是将每个矩形放在哪一行，那么问题就归结为对所有矩形对 (X,Y) 的一系列约束，其形式为“矩形 X 不能与以下形式位于同一行”当矩形 X 在 x 方向与矩形 Y 重叠时，

“贪婪”算法会从左到右对矩形进行排序，然后将每个矩形依次分配给它适合的编号最低的行。由于矩形是从左到右处理的，因此只需担心当前矩形的左边缘是否会与任何其他矩形重叠，这在一定程度上简化了重叠检测算法。

我无法证明这给出了最佳解决方案，但另一方面也无法立即想到任何反例。任何人？

回复收藏 0 原文

作死小能手 2024-07-13 13:56:52

像这样的东西吗？

按 x 位置对矩形集合进行排序

编写一个方法来检查 x 轴的特定间隔上存在哪些矩形

集合<矩形>   重叠（int startx，int endx，集合<矩形>矩形）{ 
  ... 
  }

在矩形集合上循环

集合<矩形>   绘制； 
  集合<矩形>   画; 
  foreach（toDraw 中的矩形 r）{ 
  集合<矩形>   重叠=重叠（rx，r.x+r.width，绘制）； 
  整数y=0； 
  foreach(重叠中的矩形重叠矩形){ 
  y += 重叠矩形. 高度; 
  } 
  绘制矩形（y，矩形）； 
  绘制.add(r); 
  }

Something like this?

Sort your collection of rectangles by x-position

write a method that checks which rectangles are present on a certain interval of the x-axis

Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
...
}

loop over the collection of rectangles

Collection<Rectangle> toDraw;
Collection<Rectangle> drawn;
foreach (Rectangle r in toDraw){
Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
int y = 0;
foreach(Rectangle overlapRect in overlapping){
y += overlapRect.height;
}
drawRectangle(y, Rectangle);
drawn.add(r);
}

回复收藏 0 原文