求基于Minimal Cycle Basis的图房间分割及特定边最小多边形低成本解法

• 面遍历+固定规则提取循环：先把图转成平面嵌入结构（看你的场景应该是室内平面图，属于平面图范畴），从每条未访问的边出发，严格遵循左手定则遍历：走到节点时，选当前边的下一条邻边（提前按顺时针给每个节点的邻边排好序），直到回到起点形成循环。这种方法不用复杂的最短路径计算，成本极低，而且不管从哪条边反向起始，只要规则固定，就能稳定提取出每个房间的边界——毕竟左手定则是绝对方向规则，不会因为起始边反向就乱套。

• 基于包含关系的循环筛选：如果不需要严格的Minimal Cycle Basis，只是分割房间，先提取所有简单循环，再用点-in-多边形射线法判断循环的包含关系：保留不被其他循环完全包含的外层循环，被包含的就是内部房间。这个判断逻辑简单，计算量小，适合中小规模的图。

• 对偶图快速定位房间：把原始图的每个面（也就是房间）作为对偶图的节点，原始图的边作为对偶图的边。遍历对偶图的连通分量，每个分量对应一个房间。构建对偶图可以和面遍历同步做：遍历每个面时给对偶图加节点，遇到共享边就给对偶图连边，整个过程是线性时间，效率拉满。

注意：如果你的图不是严格平面图，先做个简单预处理——把交叉边移除，或者把交叉点拆成节点，不然面遍历会出问题。另外，邻边的角度排序只需要做一次，后续遍历直接用就行，额外成本可以忽略。

内容的提问来源于stack exchange，提问作者Blastom