# How to generate a face list from vertices?

I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $$x_{\min}$$, $$x_{\max}$$, $$y_{\min}$$, $$y_{\max}$$, and the number of points in $$x$$ and $$y$$ to calculate $$\Delta x$$ and $$\Delta y$$. Then, I compute cell centers and assemble a 1D array of cells. To perform field operations, I loop over this array of cells, storing items at node centers and interpolating to faces as necessary.

In researching more advanced projects, I see that a face-based data structure is advantageous in terms of conservation, flexibility, and application of boundary conditions.

My question: For a Cartesian 2D domain, how does one generate a list of faces from arrays of vertex coordinates? These faces should compose quadrilateral cells. Can this be done explicitly?

Obviously, I could create an extremely simple 2D Cartesian mesh in something like Gmsh, but then I'd have to read in a mesh and parse the file. I can write this functionality eventually, but for my own edification, I want to quickly explore a face-based code.

• Are you assuming your cells are quadrilaterals, or something more generic? – origimbo Jan 29 '19 at 13:59
• @origimbo, Thanks for the reply. Yes--I'm thinking the cells should be quadrilaterals (just because that agrees with my rudimentary understanding at the moment). Thanks! – coffeecake Jan 29 '19 at 14:17
• Do you have a routine that takes an index of a cell and gives you indicies of vertices belonging to this cell? – 56th Jan 30 '19 at 10:13
• @56th, Thanks for the note. I don't currently, but I could add that fairly quickly. I see now that I could construct a list of four faces associated with each Cartesian cell based on the corner vertices. In my mind, I know which vertices should be connected, but is there an algorithm to determine this without a priori knowledge of the grid spacing? Also, What algorithm does one employ to remove duplicate faces? Thank you for your constructive help. – coffeecake Jan 30 '19 at 13:10
• @coffeecake You can simply return vertices in e.g. counterclockwise order. In order to avoid duplicates, you may use an associative container based on a hash table (in C++ it would be std::unordered_set or std::unordered_map; using the unordered_map you can use indicies of vertices as a key and e.g. array of indicies of neighboring cells as a value if you need this info). Insertion of an element to these containers will cost you $O(1)$ on average which is optimal. – 56th Jan 30 '19 at 17:30

1. Build a mapping $$K$$ from vertices/nodes to cells/elements, by sweeping through your cell list once.
2. For cell $$m$$, work around the edges in order.
3. For each edge, identify both vertices, $$p_1$$ and $$p_2$$.
4. For each cell in $$K$$ that $$p_1$$ belongs to, check if $$p_2$$ also belongs to it. The first one you find which isn't $$m$$ is the neighbour . If $$m$$<$$n$$, then this is the first time you've found that face.