正如您现在可能已经注意到的那样，我不断地回到这个问题。部分原因是我喜欢解决这类问题，但也因为我找不到一个看起来如此简单的优雅算法，这让我有点恼火。
好吧，不要被愚弄了，这不是一个可以通过一些简单的点操作来解决的小问题，尽管看起来确实是这样。造成这种情况的部分原因是，尽管您认为您只是在处理点，但您隐含地也在操作线段和由它们包围的区域，它们也有自己的约束（即线段应该始终形成一个或更闭合的链，并且除了在我们定义它们的顶点之外不能相交）。
此外，您的算法必须适用于您提供的任何类型的输入。也就是说，不允许仅仅因为您输入的多边形以您的算法不喜欢的方式定向而产生没有答案或错误答案。
但是，您可以做的是限制算法接受的输入类型。因此，要求输入多边形仅包含轴对齐的线段是完全有效的。
（“以错误的方式定向”和“仅轴对齐的段”之间的区别在于，第一个是一个模糊的标准，如果不对算法进行测试就无法确定 - 而第二个要求可以）。
概括地说，我们正在寻找一种将任何直线多边形（即仅由轴对齐的线段组成）水平划分为矩形的方法。
直线多边形示例
这是计划：
- 选择我们的积木
- 允许额外的顶点
- 在网格上对齐。
- 使用大小不等的网格单元。
- 哪些单元格在您的多边形内？
- 构造矩形。
选择我们的积木
尽管这些是实现细节，但提前弄清楚这一点可能会帮助您更好地了解算法的工作原理。
在代码中，我们将使用以下类型的对象作为基本构建块来表示我们的多边形：
此外，我们将使用网格，它可以建模为二维数组。
允许额外的顶点。
您说“必须使用在现有坐标上开始和结束的相交线来形成矩形。 ”。但是，请注意，仅使用现有顶点无法将大多数直线多边形划分为矩形 - 请参阅上面的示例（以及您之前提供的大篷车示例）。
因此，这个约束将不得不消失——即使我们实际上不会显式地创建新顶点。
在网格上对齐。
思想实验：如果您的多边形仅存在长度为 10、20、30 或 40...（即 10 的倍数）的（轴对齐）段，该怎么办？然后我们可以将多边形投影到网格上，并使用位于多边形内部的网格单元来组成矩形。此外，确定这些矩形的尺寸是一件轻而易举的事：只需计算位于多边形内的水平连续单元的数量并乘以 10；那是你的宽度。
网格对齐的多边形
好主意，除了：
- 多边形不仅包含相同或多个长度的段
- 我们如何确定哪些网格单元位于多边形内？
接下来我们将解决这些问题。
使用大小不等的网格单元。
如果您考虑一下，没有真正的理由让所有网格单元具有相同的宽度和高度。因此，我们可以设计一个网格，以使我们的多边形完美对齐的方式间隔开。
要获取网格水平轴的宽度：
- 收集组成多边形的顶点的所有 x 坐标。
- 对它们进行重复数据删除和排序，以增加价值。
- 然后两个后续值之间的差异定义了该列的宽度。
网格与多边形对齐
显然，单元格的高度可以用相同的方式确定。您应该确定这些宽度和高度，并将它们分别存储到两个名为gridWidths和gridHeights的数组中。
现在我们知道了单元格的数量及其尺寸，我们可以开始对网格内容进行建模。
哪些单元格在您的多边形内？
请记住，我们的多边形存储为线段链。要确定网格单元是否位于该多边形内，我们可以使用奇偶规则：从多边形外部*到我们要测试的单元的中心构造一条线段，并计算该线段与多边形的段（即使用Line2D.Double 的 intersectsLine()方法）。如果数字是偶数，它位于多边形之外，如果它是奇数，它在多边形内。
*-最好只在单元格中心之间构建水平线段（如示例所示），这样您就不会冒险与线段端点相交 - 这可能算作 0 或 2 个交叉点，从而弄乱了您的总数.
因此，我们将把这个网格建模为grid一个二维布尔数组。以这种方式处理网格的每个单元格，并将相应的点标记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 坐标，因此可以被视为一个矩形。如果你愿意，你可以实现一个额外的通道来合并这些类型的矩形。
结论
通过将直线多边形映射到网格上，我们可以轻松地将其水平划分为矩形，而无需求助于更高级的几何数据结构。
请注意，可以进行一些优化以使该算法运行得更快，但我认为这对于当前输入大小并不重要，并且会使实现更加困难。
