算法从图中得到的所有个别地区

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 n）的以下算法）
3. 直到潜在的目标是选择具有最少段
4. flood fill沿段的节点已经填满（不留后路）
5. ...（有可能是在这里完成2个加环）
6. 利润通过去除连接到所选择的节点
7. 更新剩余节点段2级的节点。

TODO：如果至少连接节点是3或更高的...