从图中获取所有单个区域的算法

Question

作为输入，我们只有一组段，这是一个例子:

[AB] = [(0, 0), (0, 4)]    ;    [BC] = [(0, 4), (2, 6)]

[CD] = [(2, 6), (4, 0)]    ;    [DA] = [(4, 0), (0, 0)]

[CE] = [(2, 6), (5, 6)]    ;    [EF] = [(5, 6), (5, 3)]

[FG] = [(5, 3), (3, 3)]    ;    [HI] = [(2, 1), (4, 5)]

[JK] = [(1, 3), (2, 3)]    ;    [KL] = [(2, 3), (1, 1)]

[LJ] = [(1, 1), (1, 3)]

(对不起，我尽力了，但我的图像有点模糊)

我需要找到所有单独的区域。从上图中我将有 3 个不同的区域，JKL、CEFG 和 {ABCD、JKL}:

请注意，不构成任何区域的段将被忽略(例如[HI])，并且区域不能被段分割，例如:

我可以使用一些完全没有效率的意大利面条代码轻松完成，但在开始之前，您是否知道我可以开始研究的算法？我正在寻找尽可能高效的东西......

Answer 1

想法:尝试从连接最少的节点创建最小的环。不断缩小问题规模。

1. 删除所有只有一个段的节点，因为它们不能属于任何区域。
2. 在段数之后按升序对节点进行排序(您需要 O(n log log n) 或更少的算法)
3. 选择分段最少的节点
4. flood fill沿着线段，直到一个潜在的目标已经被填满(不要倒退)
5. ...(这里可能有 2 个加环)
6. 通过删除连接到所选节点的 2 个分段节点获利
7. 更新剩余的节点段。

ToDo:如果连接最少的节点是 3 或更高...