0
$\begingroup$

I am working on mesh generation and optimization and encountered this problem. For example, in the figure below, we have the edge-vertex connectivity:

simple mesh 0-1

1-4

4-5

2-5

3-2

0-3

1-2

1-6

7-6

4-7

How to generate the faces in terms of face-vertex connectivity? For this case, the faces can be "generated" by visual inspection (they are 0-3-2-1, 1-2-5-4, and 1-4-7-6). But is there an algorithm to automate this?

$\endgroup$
  • 1
    $\begingroup$ I have no idea what your question is. What do you mean by "generate the faces..."? Looks to me like you just "generated" them by listing the vertices for each of the three faces. $\endgroup$ – Bill Greene Apr 13 '17 at 18:55
  • $\begingroup$ @BillGreene Hi, I just edit the question. The faces are given just as the desired answer. I am asking if there is an algorithm to automate face generation with computer. $\endgroup$ – Taozi Apr 13 '17 at 19:03
  • 2
    $\begingroup$ Are you sure this is even well-defined? For example, what happens if you take a graph that looks like a butterfly, like 0-1,1-2,2-0,0-3,3-4,4-0 (and maybe add an extra edge like 1-3 to make it rigid), then there are at least two different planar embeddings that generate different faces, if I understood your question correctly. This sounds like a potentially nontrivial, possibly ill-defined, computational geometry/graph theory question. $\endgroup$ – Kirill Apr 13 '17 at 19:15
4
$\begingroup$

As noted in the comments, your problem doesn't seem quite solvable as stated. However, if you include the assumption that each node has a 2D coordinate associated with it, then it is solvable. With the coordinates, the embedding has been chosen for you, so you don't have to worry about uniqueness.

The first thing to do is to name each edge and build the node-edge adjacency list:

Edge Names: \begin{align*} a=\{0,1\} && b=\{1,4\}\\ c=\{4,5\} && d = \{2,5\}\\ e=\{3,2\} && f = \{0,3\}\\ g=\{1,2\} && h = \{1,6\}\\ i=\{7,6\} && j = \{4,7\} \end{align*}

Node-edge adjacency sorted "clockwise": \begin{align*} 0 &= \{a,f\}\\ 1 &= \{b,g,a,h\}\\ 2 &= \{d,e,g\}\\ 3 &= \{e,f\}\\ 4 &= \{c,b,j\}\\ 5 &= \{c,d\}\\ 6 &= \{i,h\}\\ 7 &= \{j,i\}\\ \end{align*}

Note that I made no distinction about inbound vs outbound edges. You'll have to take care of this at some point, but you can decide where to do your bookkeeping.

Next, set up two arrays of booleans. The first array, $F$, indicates whether an edge has been touched in the "forward" direction (ie, in the direction listed above, like $0 \rightarrow 1$). A similar array, $B$, keeps track of the edges that you've used in the reverse direction.

Now the part that actually does some work: Pick an edge and do a depth-first search. When picking the next edge to visit, be sure to turn "left". (Pick the next edge in the clockwise adjacency list for the node that you're arriving at.) Mark each edge as "visited" in the direction that you are travelling. Once you encounter an edge that you have already used, pop everything off of your stack, and you have your cell.

Here is a worked example starting at edge $g$.

  1. Path $P = \{\}$

  2. Select edge: $g$ (forward). Push onto path: $P=\{g\}$. Mark $F[g] = visited$

  3. Arriving at node 2. Next edge after $g$ is edge $d$ (forward).

  4. Push $d$ into $P$. $P = \{g,d\}$. Mark $F[d]=visited$.

  5. Arriving at node 5. Next edge after $d$ is edge $c$ (backward).

  6. Push $-c$ into $P$. $P = \{g,d,-c\}$. Mark $B[c]=visited$.

  7. Arriving at node 4. Next edge after $c$ is edge $b$ (backward).

  8. Push $-b$ onto $P$. $P=\{g,d,-c,-b\}$. Mark $B[b]=visited$.

  9. Arriving at node 1. Next after $b$ is edge $g$ (forward). $F[g]$ is already visited, so stop.

  10. Record your path $P$ as it now holds the edges that comprise a face in your graph.

  11. Clear $P$, pick a new (unvisited) edge, and start again. Repeat this process until you have used every edge in both directions.

Note, this algorithm will terminate after every edge has been visited precisely once in each direction. This means that your "boundary" edges will all be linked together in a single "face", but this face will have all of its edges pointing with clockwise circulation, while the interior faces will have counterclockwise circulation. This can be useful for identifying which edges make up the boundary of your domain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.