从边界切割矩形
Cut rectangles from boundary
从边界提取矩形的好方法是什么？
我已经有一些东西可以工作了，但它有一些错误，有些东西的处理比要求的更高级，所以我想重新开始。
这是我想要的：
请注意，在右侧，边界被切割成多种形状。
我的边界是 float[][]，如 [nOfPoints][xy]。
例如：
[0][0] = 10;
[0][1] = 10;
[1][0] = 100;
[1][1] = 10;
[2][0] = 100;
[2][1] = 100;
[3][0] = 10;
[3][1] = 100;
[4][0] = 10;
[4][1] = 10;
会形成一个矩形。如果任何其他格式更合适，那么我可以更改它。无论如何，我对抽象的方法比对它的详细描述更感兴趣。
请帮忙。
具有轴对齐的矩形会使一些细节更容易，但不会影响一般算法，因此我不会对轴对齐做进一步的假设。
减去简单多边形的方法与描述 here 寻找多边形交集的方法相同，只是稍作改动。此外，该答案假设多边形是凸面的（实际上是矩形），因此相交最多只能产生一个多边形。在当前情况下，可能会产生多个多边形。然而，找到多个多边形并不难，请参阅下面的评论。
在相交问题中，多边形都是逆时针方向，这是一种指定（按照惯例）线的哪一侧在多边形内的方法。如果我们把要减去的矩形的方向倒过来，那么按照惯例，平面的所有都是"inside"多边形，除了边缘右边的一小块区域.所以多边形的减法实际上是多边形的交集，就是把要减去的多边形倒过来！
评论：
- 从非凸多边形中减去凸多边形可能会产生多个多边形。找到哪个多边形取决于起始交点。如果在追踪一个结果多边形的同时跟踪消耗的交点，则可以对未消耗的交点重复该过程，每次找到更多的结果。
- 如果十字路口发生在拐角处，事情就会变得混乱。一种方式是在逻辑上将交集分解为多个逻辑交集，每个逻辑交集代表一次合法遍历。
- 两个多边形的线段可能是并发的，尤其是在 OP 的情况下。这些片段可以作为预处理的一部分被剔除。如果它们在相反的方向上，它们代表一个被外部包围的无限薄的内部部件，如果它们在相同的方向上，它们代表无限薄的外部被内部包围。无论哪种方式，它们都可能被丢弃。
- 前面的评论可能看起来很奇怪，因为在丢弃重叠线段后，布尔值不再位于多边形之间，但该算法只要求实体正确定向。因此，这种通用方法可用于用曲线对多边形进行切片，将切片保持在一侧或另一侧。
- 减去多边形可能导致对象不是简单的多边形。如果被减去的多边形完全在另一个多边形内部，则结果可能是一个有洞的区域。如果担心这一点，您可以考虑使用稍微复杂一些的结构来表示使用多个循环来定义边界的区域。一个区域的外圈应该是逆时针方向，内圈应该是顺时针方向。
从边界提取矩形的好方法是什么？ 我已经有一些东西可以工作了，但它有一些错误，有些东西的处理比要求的更高级，所以我想重新开始。
这是我想要的：
请注意，在右侧，边界被切割成多种形状。
我的边界是 float[][]，如 [nOfPoints][xy]。
例如：
[0][0] = 10;
[0][1] = 10;
[1][0] = 100;
[1][1] = 10;
[2][0] = 100;
[2][1] = 100;
[3][0] = 10;
[3][1] = 100;
[4][0] = 10;
[4][1] = 10;
会形成一个矩形。如果任何其他格式更合适，那么我可以更改它。无论如何，我对抽象的方法比对它的详细描述更感兴趣。
请帮忙。
具有轴对齐的矩形会使一些细节更容易，但不会影响一般算法，因此我不会对轴对齐做进一步的假设。
减去简单多边形的方法与描述 here 寻找多边形交集的方法相同，只是稍作改动。此外，该答案假设多边形是凸面的（实际上是矩形），因此相交最多只能产生一个多边形。在当前情况下，可能会产生多个多边形。然而，找到多个多边形并不难，请参阅下面的评论。
在相交问题中，多边形都是逆时针方向，这是一种指定（按照惯例）线的哪一侧在多边形内的方法。如果我们把要减去的矩形的方向倒过来，那么按照惯例，平面的所有都是"inside"多边形，除了边缘右边的一小块区域.所以多边形的减法实际上是多边形的交集，就是把要减去的多边形倒过来！
评论：
- 从非凸多边形中减去凸多边形可能会产生多个多边形。找到哪个多边形取决于起始交点。如果在追踪一个结果多边形的同时跟踪消耗的交点，则可以对未消耗的交点重复该过程，每次找到更多的结果。
- 如果十字路口发生在拐角处，事情就会变得混乱。一种方式是在逻辑上将交集分解为多个逻辑交集，每个逻辑交集代表一次合法遍历。
- 两个多边形的线段可能是并发的，尤其是在 OP 的情况下。这些片段可以作为预处理的一部分被剔除。如果它们在相反的方向上，它们代表一个被外部包围的无限薄的内部部件，如果它们在相同的方向上，它们代表无限薄的外部被内部包围。无论哪种方式，它们都可能被丢弃。
- 前面的评论可能看起来很奇怪，因为在丢弃重叠线段后，布尔值不再位于多边形之间，但该算法只要求实体正确定向。因此，这种通用方法可用于用曲线对多边形进行切片，将切片保持在一侧或另一侧。
- 减去多边形可能导致对象不是简单的多边形。如果被减去的多边形完全在另一个多边形内部，则结果可能是一个有洞的区域。如果担心这一点，您可以考虑使用稍微复杂一些的结构来表示使用多个循环来定义边界的区域。一个区域的外圈应该是逆时针方向，内圈应该是顺时针方向。