在二维区域内为不同大小的非重叠四边形生成随机位置

Question

我正在寻找一种算法，在 2D 区域内生成不重叠的不同大小的四边形的随机位置。一个例子如下： 四边形的随机大小在 a 和 b 之间，它们平行于 xy 坐标系。我使用 JQuery (javaScript)。

如果我为每个矩形生成两个独立的随机数（用于 x 和 y 坐标），那么我必须检查此新矩形是否与其他现有矩形重叠。如果是，则忽略此选择并生成一对新数字（即新位置）。因此，这可能不是一个好的算法。

有人有什么建议吗？ 谢谢。

- Bahar S

---

我喜欢早上闻到作业的味道。 - Rory McCrossan

它必须是真正的随机还是一个类似于随机的版本就可以？ - chm

好的。很酷的问题，我很惊讶为什么没有更多人关注它！如果在我的考试后你还没有得到一个明确的答案，我会努力解决并发布它。 - chm

Answer 1

您可以使用四叉树或kd树来细分表面。空间索引也可以工作。寻找空间填充曲线和空间索引以及quadkey或geohash如何找到象限。也许r-tree也很好，因为空间填充曲线非常复杂。这里是必应地图quadkey示例：http://msdn.microsoft.com/en-us/library/bb259689.aspx。然后您可以随机使用广度优先搜索。

- Micromega

---

谢谢。你的回答非常好。然而，我正在寻找一个更实用、不那么复杂的解决方案。最后，我只是从“空闲空间”中删除了分配给每个字符的空间，并尝试在剩余的“空闲空间”中随机定位下一个字符。 - Bahar S

我不太明白，但它非常接近于k-d树、r树或四叉树。你应该学习其中之一，这样我们交流起来更容易，而且你不需要重新发明轮子。 - Micromega