Given a triangulation (geometry), are there known algorithm in finding common side of triangles, that is O(N) or better?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
3
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.
-
$\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$ 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$ 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$ Jun 21 '15 at 20:40