Converting a Non-Directional Graph to a Mesh

Question

Statement:

I'm creating a program that lets users lay out their own non-directional graph (nodes and edges). Once they press a specific button, I want to create a triangulated mesh out of each 'gap' in the graph. Here are two images that should give you an idea of what I'm after:

There are a few caveats:

• Since users have full control, I can get 3, 4, 5...n sided spaces
• A user can create either convex or concave shapes
• The application is being made in Unity with C#

My own attempts up to this point have been very inefficient and can fail in very unusual graph layouts. My general plan was to grab one node and follow the most acute angle around a cycle until I got back to the first node. This works in part, but I have no way of knowing if I've gotten every space. Additionally, I can end up with two identical meshes that cover the same space (albeit with a different node order).

I'd appreciate any help you can give me with this stumper. To help things along, I am already familiar with convex hull algorithms and triangulation.

Update:

I can't post any code because I'm under NDA for this project, but the data structures are pretty simple.

Nodes have a position (vector 3, but y is always 0) and a List of connected edges.

Edges have a first node, second node and a position (midpoint).

I want to generate a Mesh object for each gap. This mesh object has a static array of vertices (vector 3s) and a static array of triangles (which are ints and relate to vertex indices).

Answer 1

Your approach is good one. There are few points to refine.

Let assume that graph is planar (if not than it is hard to define a face) and that there are no vertices with degree one. Vertices with degree one are not a problem, but it is easier to describe solution without them :-)

Note that each edge will be in two faces. So, if you follow face by most acute angle than you are following these edges only on one side. Solution is to create directed graph with same nodes and for every edge create two edges in both directions. In general same graph as initial graph but edges are doubled. Algorithm is:

take one (directed) edge
follow it in same way by smallest angle
make faces of that cycle
remove face (directed) edges from graph
repeat procedure until there are edges.

Same approach works for graphs with vertices of degree one, but face will have a 'cut' (edge in one direction than in opposite direction.)

If you do not want outer face than do not 'double' outer edges but only make one positive direction edge from each outer edge.

Update

Since each polygon and polygon edge is passed only once I think this is quite optimal solution. Just few possibilities.

Main step in algorithm is to choose next edge from last visited node. Simple implementation is to calculate angles of out-edges and take next one. Angle calculation can be done once, not every time edge visits node, and even mapping in-edge -> out-edge can be done for a node.

It is not needed to create new directed graph, it is enough to store direction data for each edge. Two boolean variables are enough, one for each direction. With this first step, choosing not visited edge to start new polygon, gets more complex. That can be covered if upper angle calculation is used by removing visited angles from a map and flagging node as visible if there are no more angles in a map.