首先我不知道哪些关键字用于此，我想我可能使用了错误的人，以google一下吧，所以如果有人能给我会非常感激的任何提示。
我的问题是这样的：我需要找到一个房子的计划里面的“房间”。例如采取这种几何形状：
所需的算法会告诉我哪个顶点约束每个房间。因此，对于本例中是：
我有个顶点和边缘作为输入数据。编辑：边缘数据如下（边缘8,1，2）：
X Y
47 196
47 85
258 85
它是在像素坐标。
图论并没有真正帮助我，因为我已经断开共享信息的循环。例如，[1 2 9 10 3 4 5 8 1]和[11 12 14 13 11]。所以，最后我终于实现了一个图像填充，扩展填充1个像素的寄宿生和做boolen操作来找出哪些顶点是填充图像内部时。
这是planar graph。它为V的顶点，E边缘和F = E - V + 2面（包括外表面）。我们必须确定所有面的边列表。每个边缘将这些列表中（在向前和向后方向）上被使用两次。
创建主电弧列表中，添加所有弧（即1-2无向边添加两者1-2和2-1向弧）
找到最低的顶点。如果有一些这样的点，选择最左边的一（7日在这里）。旅行在CCW方向外表面（轮廓）（选择在每个顶点最右边的输出弧）：7-6-5-4-3-2-1-7。从主列表中删除访问弧线。
获得从主列表中的任何弧线，旅游之内面，按照右手法则（即7-8-5-6-7），删除访问弧线。
重复，直到主列表是空的。
重复所有的程序组件断开（11-12-13-14）
一个可能的解决方案是让每一个输入边缘是一些三角形的边缘，以三角测量该区域。然后分裂成三角形连接套，找到自己的边界。
有几种算法三角：耳裁剪，德劳内，...