将矩形划分为更小的网格的算法？

将矩形（c struct和4 int s）划分为随机数的更小的矩形（返回列表struct s）是什么算法？更好的是，如果较小矩形的最大和最小尺寸可以通过参数进行控制。将矩形划分为更小的网格的算法？

例如

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

较小的形状应该是4面，下面是不好：

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

谢谢！

附录：（矩形为白痴的讨论）

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

来源

2010-07-08 ohho

对于如何构造较小的矩形有任何限制吗？ – andand 2010-07-08 02:29:42

我不用C语言编写代码，但在我看来，递归地将矩形分成2个矩形可以完成这项工作。 – Mathias 2010-07-08 02:31:39

@and并且较小矩形的大小应受限于上限和下限参数，即不小于x轴中父矩形的百分比，不大于x轴中父矩形的百分比，不小于％的Y轴中的父矩形，不大于Y轴中父矩形的％ – ohho 2010-07-08 03:20:17

斯普利特矩形一分为二。递归。

来源

2010-07-08 02:29:57

+1精美简洁。 – 2010-07-08 02:31:18

-1：您将耗尽内存。 1/2 ** inf！= 0 – amphetamachine 2010-07-08 02:39:29

@amphetamachine：这里的最终条件非常明显，它并不需要拼写出来 - 毕竟，如果不将'1'分成'0'或者不能用整数表示的东西。 – 2010-07-08 02:43:25

在一个边上选择一个随机点p，然后用一条线将矩形划分到另一边。然后，您可以在两边进行递归，随机或按指定的限制停止递归。

来源

2010-07-08 02:35:14 Mandelbrot

问这个问题有点奇怪，没有指定在什么条件下矩形被拆分。

但是，我怀疑你要找的是一棵kd树。 kd-tree是一个二叉树，其中根据条件将节点与生成的两个子节点分开。 http://en.wikipedia.org/wiki/Kd-tree

还有一个四叉树可以稍微简单一些。它涉及将节点分成4个同等大小的孩子。每个孩子以这种方式递归地分割，直到停止条件。 http://en.wikipedia.org/wiki/Quadtree

[编辑：更新响应运算的编辑] 对于你在做什么，它可能是简单的开始将长方形连成一片电网，并决定合并哪些元素？基本上是一种自下而上的方法：简单地选择一个，并开始随机合并相邻单元。不要对已经遍历的单元执行此操作，并且合并的结构应该具有宽度和高度，以便扩展2x1单元网格将扩展到2x2或3x1以确保您始终保持4边的矩形形状合并节点。

如果你想要一个更好的方法，你可以像kd-tree一样从上到下构建它，但是当你根据随机条件进行分割时需要合并整个子树，min /最大宽度/高度参数。

来源

2010-07-08 03:02:14 stinky472

+1对于kd-trees – 2010-07-08 09:54:45

kd-trees与接受的解决方案具有相同的问题。考虑根节点。如果你在x上分割，你有一条垂直线划分矩形。如果你在y上分割，你有一条水平线划分矩形。事实上，这个解决方案与接受的解决方案没有多大区别。 – 2010-07-08 13:38:01

@Moron我不明白这个解决方案的问题在哪里。请用建议/接受的解决方案发布描述问题的答案，并提供您自己的答案，省略问题。我没有看到问题，因为考虑到这个问题，我认为这个问题永远不会创造出与你所描述的情况类似的东西。所以kd-trees就足够用于他的目的。 – 2010-07-08 13:46:29

将矩形划分为更小的网格的算法？

回答

相关问题