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

Question

我正在寻找一种算法来为二维区域中不同大小的非重叠四边形生成随机位置。一个例子可以是：

四边形的随机大小介于 a a 和 b b 之间，并且它们平行于 xy 坐标。我正在使用 JQuery (javaScript)。

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

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

Answer 1

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