作为你们可能已经注意到的，我一直在处理这个问题。部分原因是因为我喜欢解决这种问题，但也因为我无法找到一个优雅的算法来解决这个看似简单的问题而感到有些恼火。
不要被骗了，这不是一个可以通过简单的点操作来解决的琐碎问题，尽管它看起来确实如此。其中一个原因是，尽管你认为你只是在处理点，但你隐含地也在操作线段和由它们所包围的区域，这些区域也有自己的限制（即线段应始终形成一个或多个封闭链，除非它们在我们定义它们的顶点处相交）。
另外，你的算法必须适用于任何你输入的数据。也就是说，它不能因为你输入的多边形朝向不合适而产生错误答案或没有答案。
然而，你可以限制算法接受的输入类型。要求输入多边形仅包含轴对齐线段是完全有效的。
（“朝向不正确”和“仅轴对齐线段”之间的区别在于前者是一个模糊的标准，除非在算法上进行测试，否则无法确定——而第二个要求则可以）。
总之，我们正在寻找一种方法将任何直角多边形（即仅由轴对齐线段组成的多边形）水平分割成矩形。
以下是计划：
1. 选择我们的构建块
2. 允许额外的顶点
3. 对齐网格。
4. 处理不等大小的网格单元。
5. 哪些单元格在你的多边形内？
6. 构造矩形。
选择我们的构建块
尽管这些是实现细节，但在前期搞清楚这些可能有助于您更好地了解算法的工作原理。
在代码中，我们将使用以下类型的对象作为基本构建块来表示我们的多边形：
此外，我们将使用网格，可以将其建模为二维数组。
允许额外的顶点。
您说过“矩形必须是由开始和结束于现有坐标上的相交线段组成的。”。然而，请注意，大多数直角多边形无法仅使用现有顶点分割成矩形 - 请参见上面的示例（以及您之前提供的房车示例）。
因此，这个限制条件将不得不消失 - 即使我们实际上并不会显式地创建新的顶点。
在网格上对齐。
思路实验：如果您的多边形仅由长度为10、20、30或40的（轴对齐）线段组成，即10的倍数？然后，我们可以将多边形投影到网格上，并使用位于多边形内部的网格单元格来组成矩形。此外，确定这些矩形的尺寸将是一件轻而易举的事情：只需计算水平连续单元格的数量，该单元格位于多边形内部并乘以10；那就是你的宽度。
好主意，但问题是：
多边形不仅由相同或多个长度的线段组成
我们如何确定哪些网格单元格位于多边形内？
我们将解决这些问题中的每一个。
处理大小不均的网格单元格。
如果您考虑一下，没有必要让所有网格单元具有相同的宽度和高度。因此，我们可以设计一种网格，使其间隔排列，以便我们的多边形完全对齐到它上面。
为了获得网格水平轴的宽度：
- 收集组成多边形的顶点的所有x坐标。
- 对它们进行去重并按递增值排序。
- 两个相邻值之间的差异确定该列的宽度。
显然，单元格的高度可以用同样的方式确定。您应该确定这些宽度和高度，并将它们分别存储在名为
gridWidths和
gridHeights的两个数组中。
现在我们知道了单元格的数量和它们的尺寸，我们可以开始建模网格内容。
哪些单元格在您的多边形内？
记住，我们的多边形被存储为一系列线段。为确定一个网格单元是否在该多边形内部，我们可以使用
奇偶规则：从多边形外部*构造一条线段到我们要测试的单元格中心，并计算这条线段与多边形线段的交点数（即使用
Line2D.Double的intersectsLine()方法）。如果交点数是偶数，则它在多边形外部，如果是奇数，则在多边形内部。
*-最好只在单元格中心之间构造水平线段（如示例所示），以免冒险相交于线段端点-这可能会计为0或2个交点，从而破坏您的计数总数。
因此，我们将把这个网格建模为
grid，一个二维布尔数组。以这种方式处理网格的每个单元，并将相应的位置标记为true（多边形内部）或false（多边形外部）。
根据奇偶规则判断内部(T)或外部(F)
构建矩形。
现在，我们有了多边形的网格表示，以及每个单元的实际宽度和高度，我们可以开始构建矩形。我假设您只对每个矩形的宽度和高度感兴趣，而不是形成矩形的实际顶点坐标（尽管这也很容易）。
Foreach row in grid
run_start = null
Foreach cell C in row
if C is marked as true and run_start = null
//Found the start of a new run
run_start = C
else if C is marked as false and run_start != null
//Found the end of a run
The cells [run_start...C] form a horizontal rectangle.
Use the gridWidths and gridHeights arrays to determine the
dimensions, and report this rectangle as a result
//Prepare for the next run
run_start = null
多边形被分割成矩形。
请注意，左上角的两个矩形具有相同的起始和结束x坐标，因此可以视为一个矩形。如果需要，可以实现一个额外的步骤合并这些类型的矩形。
结论
通过将直角多边形映射到网格上，在不需要使用更高级的几何数据结构的情况下，我们可以轻松地将其水平划分为矩形。
请注意，有一些优化可以使该算法运行得更快，但我认为它对于当前的输入大小并不重要，而且会使实现变得更加困难。
