我们得到了一个N x M的矩形区域，其中有K条线。每条线都有（x0，y0）-（x1，y1），开始和结束坐标。有没有一些众所周知的算法或资源可以帮助我编写一个程序，找出这些线在矩形区域中形成的独立区域？
如果这是原始矩形区域：http://prntscr.com/6p9m2c然后有4个独立的区域：http://prntscr.com/6p9mo5
所有具有交集的线段都形成平面图。你必须彻底计算这个图的顶点和边，然后应用欧拉公式
F = E - V + 2
其中
V是垂直计数-交叉点（以及拐角和自由段末端）的数量
E是边计数-线段的数量，在相交后形成
F是刻面的数量
您需要的区域计数是
R = F - 1
因为F考虑了外表面。
例如，有16个顶点，10个水平边和9个垂直边，所以
R = 10 + 9 - 16 + 2 - 1 = 4
请注意，您可以计算阶数为1,2的顶点（角和自由端），也可以将它们与一个相邻线段一起忽略（简化图）-这不会影响结果。
假设NxM网格是一个每个"."是一个顶点，如果两个顶点并排（在上面、下面、侧面），则它们通过边连接。现在，每个单独的区域对应于图的一个连接组件，您可以使用BFS或DFS算法计算O（N*M）中连接组件的数量。