algorithm - 在给定矩形页面上的分割线段的情况下获取网格信息(数量和边缘)？

Question

我遇到了一个问题，在给定矩形页面上的分割线段的情况下查找网格信息(数字和边)。以下图为例，所有分割线段的两端点都用红色圆圈表示，这里的数字为7，如图中标注。7。

假设:

1. 线段形成矩形页面的有效分割。
2. 所有最终网格都是四边形。
3. 没有交叉线段(即认为在交叉点上有一个额外的端点)。
4. 没有线段位于另一条线段内。

当前解决方案:

1. 在页面内随机选择一个点(之前没有标注)。

2. 遍历当前区域内的所有点，直到触及边界或分割线并标记它们。当前区域是一个有效的网格。

3. 循环步骤 1-2，直到所有点都被标记。

注意:这里我还假设整个页面可以离散到均匀的点(就像图像中的像素)。

问题与问题:

上述解决方案的问题是我必须遍历页面内的所有点才能获得所有网格。有没有更简单的解决方案？

Answer 1

我终于通过分而治之找到了一个简单的方法来做到这一点。

理论依据: 添加线段会将当前区域分割成两个网格。

根据以上，数字应该是非常直接的，即 number_line_segments+1。

---

为了确定每个网格的边缘，我们还需要知道添加新线段时分割了哪个区域。

那么，问题转化为:如何确定所有线段的有效相加顺序(不唯一)。这里，“有效”是指添加新的线段时，会将当前区域分割成两个网格。

要确定所有线段的有效添加顺序，我需要做的就是确定任意两个的顺序，可以按如下方式确定:

order_for_two_line_segments(LineSeg LineSeg_A, LineSeg LineSeg_B)
{
    if (one of LineSeg_A's end points is on LineSeg_B)
        LineSeg_B should come before LineSeg_A;
    else if (one of LineSeg_B's end points is on LineSeg_A)
        LineSeg_A should come before LineSeg_B;
    else // neither end points of them are on the other one
        they can be in any order;
}

例如，在下图中(所有行都标记为 L1-L6)，L1 应该在 L2 之前，因为其中一个L2 的终点在L1 上，没有它L2 就无法形成有效的拆分。并且 L2 和 L6 之间的任何顺序都是可能的，因为它们的端点都不在另一个端点上，这使得它们中的任何一个(没有另一个)仍然可以形成有效拆分。

一个有效的添加顺序可以是L3 > L1 > L2 > L5 > L4 > L6。

---

编辑:上述方法也适用于网格可以是任何形状的一般情况。