# Border of a Mesh

This topic is 3337 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, i´m trying to find an efficient algorithm for finding the border-vertices(segments) of a Mesh in 2D. The information i have: - muuuuuuch vertices with their ID an Coordinates - a list of the triangles of the mesh ( with the 3 vertex-ID´s) The idea is to loop the triangles and search for another triangle with 2 same Vertices. So i have to do this for Vertice 1 and 2, 2 and 3, 1 and 3. If there is a second triangle it is not an edge of the mesh, otherwise i add those two vertices to my border-vertice-list. But i think this is not very efficient. Maybe anyone already has a solution for c# ?

##### Share on other sites
This seems like a very easy problem to solve if you can use an associative container. I don't know any C#, but if you still can't figure it out I'll try to give you some sample code (probably in C++).

##### Share on other sites
I'm not entirely clear on what you are trying to do, but is this a convex hull problem?

##### Share on other sites
No, i´m not searching for the convex hull, i´m searching for the edge(vertice)s of a mesh.

@alvaro: jeah i think you are right. I will try it with hash arrays.

##### Share on other sites
In pseudo-code (assuming your triangles are oriented, it works for any dimension):
for each edge (v1, v2) {  if (v1<v2)    count[v1][v2]++;  else    count[v2][v1]--;}for each index i in count {  for each index j in count {    if (count[j]!=0) {      border_vertices.insert(i);    }  }}

##### Share on other sites
this is my current code and it works:
            ArrayList al_border = new ArrayList();            Hashtable ht_Triangle = new Hashtable();            foreach (Triangle item in this.Triangles)            {                ht_Triangle.Add(" " + item.ID_1 + " " + item.ID_2 + " ", item);                ht_Triangle.Add(" " + item.ID_2 + " " + item.ID_3 + " ", item);                ht_Triangle.Add(" " + item.ID_3 + " " + item.ID_1 + " ", item);            }            foreach (Triangle item in this.Triangles)            {                String key1 = " " + item.ID_2.ToString() + " " + item.ID_1.ToString()+ " ";                String key2 = " " + item.ID_3.ToString() + " " + item.ID_2.ToString() + " ";                String key3 = " " + item.ID_1.ToString() + " " + item.ID_3.ToString() + " ";                if (!ht_Triangle.ContainsKey(key1))                    al_border.Add(new Segment(item.ID_1, item.ID_2));                if (!ht_Triangle.ContainsKey(key2))                    al_border.Add(new Segment(item.ID_2, item.ID_3));                if (!ht_Triangle.ContainsKey(key3))                    al_border.Add(new Segment(item.ID_1, item.ID_3));            }

But would be nice if someone could find an optimization for this problem.

##### Share on other sites
On little note: if your mesh is texture mapped, there is a chance that there are vertices with same position but different texture co-ordinates, so you need to adapt the above to handle when two different vertex ID's refer to the same geometric position.

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633742
• Total Posts
3013633
×