graph-theory - 确定双向连接边列表 (DCEL) 的面的子集是否形成简单连接区域

Question

我试图使增量凸包算法的玩具实现更加健壮，并且在某些退化的情况下，有许多几乎共面的点，可见区域包含“洞”。

有没有办法检查标记为可见的面是否形成一个简单的连接区域？

我正在考虑某种 BFS，给定一个特定的起点，但我无法完全掌握它。

Answer 1

I'm assuming that you have easy ways to traverse your mesh. If not, then another algorithm might be more suitable.

Keep a set of edge indices that are border edges.

• Iterate through every face in the selection.
• For each face, look at all it's edges.
• If the face on the other side of the edge is also a selected face, then continue to the next edge on the face.
• Otherwise, the edge is a border edge.
  
  • Do a floodfill along the border for border edges. This will either form a complete loop, or go off the edge of the mesh.
  • If it goes off the edge of the mesh then you'll need to keep searching along the border of the mesh until you hit an edge that is a border of the selection, and follow up through there, until you are able to form a complete loop.
  • Add that loop to the set of border edges for quick lookup.

As you continue looping through all faces' edges looking for border edges, check each border edge against the set of border edges you got from your first loop. If the new border edge is not in the set of border edges then it forms a second loop, meaning that your selection isn't compact.