单独区域算法

Question

我们给出了一个N×M的矩形区域，其中有K条线。每行有（x0，y0） - （x1，y1），起始和结束坐标。是否有一些众所周知的算法或资源可以帮助我编写一个程序来查找这些线条在矩形区域中形成了多少个独立区域？

如果是这样的原始矩形区域：http://prntscr.com/6p9m2c 再就是4个分离的区域：http://prntscr.com/6p9mo5

Answer 1

带有交点的所有段形成planar graph。你必须彻底计数顶点和这个图的边，然后应用Euler's formula

F = E - V + 2 

其中
V是顶点计数 - 交叉数量（见角，并免费区段末端）
E是边数 - 数分段，形成后交叉点
F是方面的数量。
您需要的区域数为

R = F - 1 

因为˚F考虑到外面。

对于示例 - 有16个顶点，10个水平边和纵9，所以

R = 10 + 9 - 16 + 2 - 1 = 4 

请注意，可以任一计数与1,2-度顶点（角部和自由端部），或忽略它们一起与一个邻居段（简化图） - 这不影响结果。

Answer 2

想象一下，NxM网格是一个图形，每个'。'是一个顶点，如果它们并排（上面，下面，侧面），则两个顶点通过边相连。现在每个单独的区域对应于图形的连接组件，并且您可以使用BFS或DFS算法计算O（N * M）中连接组件的数量。