3
$\begingroup$

Given a 2D triangle mesh with $n$ vertices, I was wondering if there is an expression that would allow to compute the total number of edges present in the mesh.

For example, the following mesh has 6 vertices and a total of 11 edges:

mesh

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I think the question is not clear. Will you give some example of a 2D triangle mesh and number of its segments? $\endgroup$ – Mohsen Shahriari Nov 23 '15 at 3:40
  • $\begingroup$ I have added an example for clarity. $\endgroup$ – codeaviator Nov 23 '15 at 11:25
  • $\begingroup$ For connected planar graphs, Euler's formula gives us $n-m+f=2$ where $n$ is the number of vertices, $m$ the number of edges, and $f$ the number of faces (including the infinite one). For your example, $n=6, f=7$ which gives $m=11$. $\endgroup$ – Kelvin Soh Nov 23 '15 at 12:14
  • $\begingroup$ This seems - to some extent - related: math.stackexchange.com/questions/425968/… $\endgroup$ – Martin Sleziak Nov 23 '15 at 12:44
5
$\begingroup$

The number of vertices alone is not sufficient to determine the number of edges

From Euler's formula we know that $$v-e+f=2,$$ where $v$ is the number of vertices, $e$ is number of edges and $f$ is number of faces (including the outer one).

Now you now additionally, that boundaries of faces have three edges. However, there is one exception, which is the outer face. Let $b$ denote the number of vertices on its boundary (i.e. on the boundary of your mesh). Then you have $$2e=3(f-1)+b.$$ (We count $3$ edges for each inner face, and $b$ edges for the outer face.)

So if you know both $v$ and $b$, you can calculate the number of edges as $$e=3v-3-b.$$

Some examples $$ \begin{array}{|c|c|c|c|} \hline \text{graph} & e & v & b \\\hline \text{triangle} & 3 & 3 & 3 \\\hline K_4 & 6 & 4 & 3 \\\hline \text{diamond} & 5 & 4 & 4 \\\hline \text{your mesh} & 11 & 6 & 4 \\\hline \end{array} $$

$K_4$ is this graph (complete graph on four vertices):

K4

Diamond is this graph:

diamond

The pictures are taken from list of small graphs.

| cite | improve this answer | | | | |
$\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.