问分割区算法

EN

所有具有交叉点的线束段都形成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的顶点(角和自由端)，也可以将它们与一个相邻线段一起忽略(简化图)-这不会影响结果。

想象一下，NxM网格是一个图形，其中每个“.”是一个顶点，如果两个顶点并排(上方、下方、侧面)，则它们由一条边连接。现在，每个单独的区域对应于图中的一个连接组件，您可以使用BFS或DFS算法计算O(N*M)中连接组件的数量。