1
$\begingroup$

Given a triangulation (geometry), are there known algorithm in finding common side of triangles, that is O(N) or better?

enter image description here

Improve this question
$\endgroup$
2
$\begingroup$

If you know the number of edges and triangles, you could raster through a list of your triangles and create a triangle-to-edge map $(\mathcal{O}(N_{tri}))$ and simultaneously create the inverse map, which will give you the two triangles that share an edge. A naive search of that list for the right triangle-pair will be $\mathcal{O}(N_{edge})$, where $N_{edge}$ will at worst be $3 \cdot N_{tri}$. Of course, this all assumes you have a method for computing a unique ID for each edge in the graph.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Assuming you don't have a very large mesh (twice the number of vertices $2N_v < $ max unsigned long int value), since each edge is identified by two vertices $v_1, v_2$, a unique edge ID can be given by $v_1 + v_2 N_v$. $\endgroup$ – Jesse Chan Jun 21 '15 at 14:44
  • 2
    $\begingroup$ In fact, the unordered tuple $(v_1,v_2)$ is also a unique ID, without the restriction on the size of the integers. $\endgroup$ – Wolfgang Bangerth Jun 21 '15 at 16:07
  • $\begingroup$ Good point. You could then sort the tuples $(v_1,v_2)$ (using std::sort and a comparison operator). If you attach an element ID to each tuple, matching elements will come up as sequential pairs of tuples in this list. $\endgroup$ – Jesse Chan Jun 21 '15 at 20:40

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.