How to mathematically describe a whether an edge belongs to a geometric face

Question

No, it is not a human face. But rather, how can we mathematically describe if an edge, belongs to a face of a piece of geometry?

For example, let's say that you have a square within a square:

How would you be able to describe that the edges displayed belong to the outer square instead of the inner square?

Edit: This problem is assuming that the inner square is a hole.

Also, I am only dealing in 2D space.

This is only a simplification of an overall problem. I am currently working on an alvorithm that will be able to take a list of lines, nodes (or vertices), and arcs and convert them into a data structure that is recognizable to GMSH. I have my own line, arc, and node list and I need to convert it into a GModel (for those who are famalier with gmsh, I am essentially creating a .geo file using the c++ source directly).

The format is that I need to specify all of the nodes in the gmodel. The gmsh equilivant to a node is a Gvertex. Then, to create the lines, I need to specify which Gvertex is associated with the gline. This part will be relatively easy.

The hard part is specifing the GFace. Basically, a GFace is a collection of Glines. But the challenge is is how to specify or how to know which Gline belongs to which face.

For example, say we have 2 squares, how can you identify line 1 belongs to square 1 or square 2?

In this example, how can you identify that the outer square is the actual face verses the inner square which is a hole? And how can you know that the edges belong to that face?

Again, this is a simplification. The answer would need to apply to any geometry.

Here is a link to a picture with a more complicated geometry. I think that the example that I gave was an over simplification:

https://i.stack.imgur.com/pga7k.jpg

Edit 2:

Please forgive me. I am still developing my math terms and language. I am mostly a programmer. I will do my best to communicate my ideas to the users on the forum. Please though, if there is additional data that I need to clarify or need to say, let me know and I will happily edit this thread.

My geometry is composed of vertices which is a double of real numbers (x, y). This is only in 2-D. I am not doing anything with imaginary numbers or utilizing other graphs. This is 2-D Euclidean space. These vertices are stored in an array (or list or vector or whatever). There is no particular order to how the vertices are stored.

An edge is a pair of indices that is obtained from the vertex list. Ex. (2, 5) means that an edge is created between the 2nd and 5th node. For this, I consider arcs the same as edges but with information such as the arc angle, radius, and center of the arc.

Also, the edge list is in no particular order.

Basically, I need to generate a list of faces. A face will be defined by line loops which are an array of the edges that compose the face. The 0th index will be the outer most line. If there are any holes in the domain, then the proceeding indices in the array will be the holes. For the example of the square: lineLoop[0] = {1, 2, 3, 4}. The 1 is the first edge and the 2 is the second edge. (I didn't label the edges wih numbers but the numbering of the edges can start from any point as long as it is a counter clockwise direction). And lineLoop[1] = {5, 6, 7, 8}. At this point, lineLoop is able to describe the face effectively.

Answer 1

OK. Here's a solution, as far as one is possible. It makes two assumptions:

1. For each edge $ (a, b) $, there's exactly one other edge whose start or end point is $a$; that other edge's other endpoint is not $b$. So if you have edge $(2, 5)$, then there's an edge like $(2, 4)$ or $(17, 2)$ as well. The same goes for the vertex $b$.

2. The number of edges is finite.

OK, here goes.

STEP 1.

TL; DR: under the equivalence relation defined by "neighbor", find all equivalence classes, and organize each into a chain using "other".

We're going to form a list of chains (a "chain" being a sequence of (edge, vertex) pairs, where the vertex is one of the two vertices of the edge). I'll use the function $other$ which consumes an edge and a vertex of that edge, and returns the other vertex of the edge, so that $other( (2, 5), 2) = 5$ and $other((2, 5), 5) = 2$. I'll also use $neighbor( (a, b), b)$, which returns the unique edge $(b, c)$ or $(c, b)$ that shares vertex $b$ but for which $c \ne a$. Both "other" and "neighbor" can be implemented by a hashdictionary, for instance, using a single pass through the data.

Init: make the chain list empty; set $i$ to $0$.

While edge list is not empty: Create a new empty chain $C$. Remove from the edge list the first edge, call it $(a, b)$. Set done = false. Place $( (a, b), b)$ into the chain $C$.

while not done:

• Let $(e, v)$ be the last item in $C$, and let $e' = neighbor(e, v)$. Let $d = other(e', v)$.

• If d = a, then set done = true, and insert $C$ into the chain list.

---

When you're done, you'll have a list $L$ of chains. For each chain, you can ignore the edges and just read off the vertices, and these will be the "faces" that you're looking for.

STEP 2:

Now you have to decide which are "faces" and which are "holes".

Unfortunately, from the data given, this cannot be determined. For instance, in the following diagram , there are three chains, which form concentric squares. On the left, the innermost chain bounds an orange square and the outer two together bound a blue ring-shaped face. But on the right, the outer one bounds a blue square, while the inner two bound a ring-shaped orange face. (The blue outer square shows through the hole in the inner ring).

Perhaps you meant to include some constraint on whether faces can overlap (as they do in the right-hand example). But without that information (which is not part of the input or output you described), it's hopeless, as this example shows.

Answer 2

There is no intrinsic difference between the edges. What I mean is that the answer completely depends on the ambient space where this manifold with boundary lies.

For example, if this space lies in $\mathbb R^2$ (what you probably had in mind), then yes, you can tell which square is "inner" and which is "outer" since the whole shape will divide the plane in two connected components, "inner" and "outer", and we can decide which is which since the "inner" component is simply connected, while the "outer" is not.

On the other side, we might not be in $\mathbb R^2$, for example this space might be embedded in sphere $S^2$. You can easily imagine something like equatorial belt, there is absolutely no way to decide what is "in" and what is "out", because the two connected components are identical.

Perhaps even more transparent way to see this is if we embed this space in $\mathbb R^3$ as a strip. Then there is only "outside" of the strip, i.e. only one connected component. You can easily imagine continuous transformation of this strip inside $\mathbb R^3$ which switches the edges (like turning socks inside out, just this sock is with a hole in it).

The point is, if you want me to give an answer, first tell me how this shape is embedded in some ambient space and depending on that, I will tell you what is in and what is out.