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

Question

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

给定一个大矩形，以及大矩形内的一系列较小的非重叠矩形。

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

Answer 1

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

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

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

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

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

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