algorithm - 涉及穿过矩形的正交线的几何问题的算法

Question

我被这个编程问题困了一段时间，真的不知道该怎么做。

我们得到一个大矩形，以及大矩形内的一系列较小的非重叠矩形。

您如何设计一种算法来找到使用正交线将大矩形划分为的最大分区数，因为 1）每个分区必须至少有一个较小的矩形，并且 2）每当绘制一条线时，分区的数量必须至少增加 1。

标签： algorithmgeometry

Answer 1

规则 (2) 意味着您的切割线永远不会交叉 - 每一条都将现有分区切割成 2 块。

规则 (1) 意味着您实际上只是想找到可以使用水平或垂直切割将小矩形划分为的组数。很多时候，答案将与小矩形的数量相同，但有时您无法将它们全部划分。例如，如果不将其中至少一个一分为二，就无法切割以这种方式排列的一组矩形：

   AAAAAAAA  BBB
   AAAAAAAA  BBB
             BBB
   CCC       BBB
   CCC       BBB
   CCC
   CCC  DDDDDDDD
   CCC  DDDDDDDD

要创建尽可能多的组，您可以遵循一个简单的递归过程：

1. 尽可能多地进行垂直切割
2. 在每个生成的分区中，尽可能多地进行水平切割
3. 在每个生成的分区中，返回 (1) 直到您不能进行任何新的切割

要确定您可以在分区中进行的最大切割次数，您只需考虑另一个方向上每个矩形的结束坐标（例如，如果您正在垂直切割，则查看每个矩形最大 X）。如果通过该坐标的线不与任何其他矩形相交，则在此处剪切。