Convert undirected graph to grid

Question

Statement:

I am creating a program that allows users to lay out their own undirected graph (nodes and edges). When they press a specific button, I want to create a triangulated grid from each “space” in the chart. Here are two images that should give you an idea of ​​what I need:

There are a few caveats:

• Since users have full control, I can get 3, 4, 5 ... n one-way spaces.
• User can create either convex or concave shapes
• Application runs in Unity with C #

My own attempts up to this point have been very inefficient and may fail in very unusual graphic layouts. My overall plan was to capture one node and follow the sharpest corner around the loop until I get back to the first node. This works partially, but I don’t know if I got all the space. In addition, I can get two identical cells that span the same space (albeit with a different node order).

I would appreciate any help you can give me with this drummer. To help you with this, I am already familiar with convex algorithms and case triangulation.

Update:

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

The nodes have a position (vector 3, but y is always 0) and a list of connected edges.

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

I want to create a Mesh object for each space. This mesh object has a static array of vertices (3s vector) and a static array of triangles (which are int and refer to vertex indices).

Answer 1

Your approach is good. There are a few points to clarify.

Suppose that the graph is flat (if it is not so difficult to determine the face) and that there are no vertices with degree one. Vertices with degree one are not a problem, but it is easier to describe a solution without them :-)

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

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. 

The same approach works for graphs with vertices of the first degree, but the face will have a “cut” (edge ​​in one direction than in the opposite direction).

If you do not need an external face, than not "double" the outer edges, but make only one edge in a positive direction from each outer edge.

Update

Since each edge of the polygon and the polygon is transmitted only once, I think this is a fairly optimal solution. Just a few possibilities.

The main step in the algorithm is to select the next edge from the last visited node. A simple implementation is to calculate the angles of the outer edges and do the following. Calculation of angles can be done once, and not every time an edge visits a node, and even an in-edge → out-edge mapping can be performed for a node.

There is no need to create a new oriented graph; it is enough to store direction data for each edge. Two boolean variables are sufficient, one for each direction. With this first step, choosing an unvisited edge to launch a new polygon becomes more complex. This can be covered if the top corner calculation is used, removing visited corners from the map and marking node as visible if there are no more corners on the map.