将一个矩形分割成更小的矩形的算法？

Question

如何将一个矩形（c中的struct，包含4个int）划分为随机数量的小矩形（返回一个struct列表）的算法是什么？如果可以通过参数控制较小矩形的最大和最小尺寸，那就更好了。

例如：

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -->     |---+---+--| (good)
|          |            |   |      |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

小的形状应该是四边形，以下不好：

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -->     |---+---+--| (not good)
|          |            |          |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

谢谢！

附录：（矩形用于莫伦的讨论）

  +----+--------+
  |    |        |
  |    +---+----+
  |    |   |    | (rectangle-chase)
  +----+---+    |
  |        |    |
  +--------+----+

- ohho

---

小矩形的结构有什么限制吗？ - andand

我不会用C语言编程，但是我认为将矩形递归地分成两个矩形应该可以完成任务。 - Mathias

@andand 较小矩形的大小应受到上下限参数的限制，即在x轴上不小于父矩形的%、不大于父矩形的%；在y轴上不小于父矩形的%、不大于父矩形的%。 - ohho

@Horace：被接受的答案缺少一些配置（请参见我对该答案的评论）。 - Aryabhatta

一个小矩形位于一个大矩形的中心是否可接受？您希望每个子矩形数是等概率的，还是每个子矩形配置都是等概率的？每个有效的配置都必须是可达到的吗？ - BlueRaja - Danny Pflughoeft

Answer 1

将矩形分成两个部分。递归处理。

- Axel Gneiting

---

错误。它缺少一些配置。类似于JP摩根银行的标志，但完成后形成一个矩形。http://bp1.blogger.com/_YdwmIhUxTJY/R6PknAooqlI/AAAAAAAAAco/k6jOGsQOT48/s400/chase-logo.jpg。抱歉没有更好的描述，但我想你明白我的意思：正中间是一个正方形，每个正方形的边都延伸到恰好触碰主矩形的一侧。 - Aryabhatta

@Moron，我添加了一个附录，其中包含我能想到的标志。这是你所指的吗？ - ohho

@Horace Ho 你应该看一下kd树：http://en.wikipedia.org/wiki/Kd_tree。你想要实现的基本上是一个k=2的kd树。 - Dave O.

@Dave：不是的。Kd树基本上给出与这个解决方案相同的答案。请看我对那个回答的评论。 - Aryabhatta

@Dave：在@Moron提出异议之前，这个答案已经被采纳了；它确实是错误的。此外，仅仅因为问题提出者接受了一个答案并不意味着我们应该停止寻找更好（或正确）的答案。 - BlueRaja - Danny Pflughoeft

Answer 2

没有指定矩形分割条件，询问这个问题有点奇怪。不过我猜你想要的是kd树。kd树是一种二叉树，节点根据条件分成两个子节点。参考链接：http://en.wikipedia.org/wiki/Kd-tree。

还有一种四叉树，实现起来可能会稍微简单一些。它将节点分成4个相等大小的子节点，每个子节点都以相同方式递归地分割，直到满足某个停止条件。参考链接：http://en.wikipedia.org/wiki/Quadtree。

对于你正在做的事情，也许更简单的方法是先将矩形分成均匀的网格，然后决定合并哪些元素。基本上是自下而上的方法：随意选择一个单元格并开始合并相邻的单元格。不要为已经遍历过的单元格做此操作，合并后的结构应该具有宽度和高度，使得扩展2x1单元格网格将扩展到2x2或3x1，以确保始终保持合并节点的四边形形状。

如果你想要一个更高级的方法，可以像处理kd树一样从顶部开始构建，但你需要根据随机条件和最小/最大宽度/高度参数合并整个子树。

- stinky472

---

kd树与已接受的解决方案存在相同的问题。考虑根节点。如果您在x上进行拆分，则会有一条垂直线将矩形分开。如果您在y上进行拆分，则会有一条水平线将矩形分开。实际上，这个解决方案与已接受的解决方案并没有太大区别。 - Aryabhatta

@Moron，我不明白这个解决方案的问题在哪里。请发布一个回答，描述建议/接受的解决方案的问题，并提供您自己的解决方案，省略问题。我看不到问题，因为根据问题，我认为op从来不会想创建类似于您描述的情况的东西。因此，kd树对他的目的足够了。 - Dave O.

@Dave：OP从未说过不想要附录中的矩形（但我想我们很快就会知道）。无论如何，这个kd-tree解决方案与被接受的解决方案相同。实际上，您正在将矩形分成两个部分并进行递归。抱歉，除非我有答案，否则我不会发表评论... - Aryabhatta

每个理智的人都知道这两个答案意思相同。既然操作员接受了这种解决方案，他似乎对其限制感到满意。别再抱怨了。我对你选择的用户名表示赞赏。 - Dave O.

@Dave。哦，请……无论如何，我会停止与你进行这个讨论。毫无意义，浪费时间。 - Aryabhatta

Answer 3

在一条边上选择一个随机点p，并通过该点将矩形分成两部分，直到划分达到指定的限制或随机停止，然后对两个子矩形进行递归处理。

- Mandelbrot