algorithm - 当我想要有效地搜索所有区域时，什么是用于存储矩形的好数据结构至少包含给定的大小

Question

所以我有一组不重叠的矩形，我想有效地确定给定大小的矩形可以放在哪里。哦，它还需要在更新时相当有效，因为一旦我找到可能的有效位置，我将根据其他一些约束“分配”空间。

“复杂的部分”是矩形可以触摸（例如，（0,0）100 单位宽和 50 单位高的矩形，以及（0,50）和 50x50 的第二个矩形允许 50 宽乘 80 高从 (0,0) 到 (0,20) 的矩形。找到合适的可能涉及“合并”两个以上的矩形。

（注意：我将从少量相邻的矩形开始，大约 3 个，并在我“分配”它们时删除矩形区域。我希望这些分配的大量不会完全覆盖现有的矩形，并且会离开我还有 2 个更新的矩形。）

起初我以为我可以保留我的矩形的两个“视图”，一个更喜欢在 y 轴上断开以保持尽可能宽的矩形，另一个在 x 轴上断开以保持可能的高度，然后我可以做到。 ..um ...一些聪明的搜索。

然后我想“嗯，人们已经在这个东西上工作了很长时间，只是因为我不知道如何构建正确的谷歌查询，这并不意味着这不是四叉树或 r 的直接应用。 -我不知何故忘记知道的列表”</p>

那么这个问题已经有很好的解决方案了吗？

（那么我到底在做什么？我正在将特征激光切割到盒子的地板上。像“NxM 圆圈直径为 1.23 英寸，间距为 0.34 英寸”之类的特征。地板从一个矩形开始，小矩形已经从角落移除支持。我目前正在保留一个未分配矩形列表，按 y 排序，x 作为决胜局，在某些有限的情况下，如果它产生足够大的结果以适合我当前，我可以在该列表中的 2 个矩形之间进行合并目标进入。这并不是那么好。我也可以手动放置功能，但我宁愿为它编写一个程序。）

（另外：我要做多少“事情”？到目前为止，我的盒子已经有 20 到 40 个“功能”可以放置，而且计算机速度很快，所以一些非常低效的算法可能会很好用，但这是一个爱好项目，并且我不妨学习一些有趣的东西，而不是粗暴地将一些代码捆绑在一起）

好的，所以没有一个好的答案，我从另一个角度来了。我查看了我所有的政策，并提出了一个非常简短的清单：“在任何合适的地方分配”、“在特定的 x、y 位置分配”和“在任何地方分配 y>（特定值）”。

我决定用一个非常简单的数据结构进行测试。表示可分配空间的非重叠矩形列表。未以任何特定方式排序、合并或组织。最有趣的是我跟踪矩形的范围以快速检索最小/最大 X 或 Y。

我自己做了一个小函数，检查特定位置的分配，并返回一个矩形列表，阻塞分配，所有修剪到与预期分配的交叉点（如果适用，则生成一个新的空闲列表）。我用它作为实现所有 3 个策略的原语。

“在特定的 x,y 位置分配”很简单，如果您没有看到分配成功的阻塞矩形，请使用原语。

我将“随处分配”实现为“使用 y>N 分配”，其中 N 是空闲列表中的“最小 Y”。

"allocate where y>N" 从空闲列表中的 x=min-X 开始并检查那里的分配。如果它没有发现任何阻碍，它就完成了。如果它找到阻塞器，它会将 x 移动到阻塞器列表的 max-X 处。如果这将预期分配的右边缘置于空闲列表的 max-X 之后，则将 x 设置回空闲列表的 min-X，并将 y 设置为遇到的所有阻塞列表中所有 max-Y 的最小值自上次 Y 更改以来。

对于我的使用模式，我还从记住上次失败分配的大小（N=minY）以及快速失败至少与上次失败一样宽/高的任何内容中获得了一些里程。

对于我的使用模式，性能足够快（从一到三个项目开始的空闲列表，从十到四十的分配）。

标签： algorithm