I am trying to write a script that would return the neighbouring vertices of a mesh like so:
This would actually be a part of a larger script that outputs a Vector2 array that I would feed into a polygon collider 2D.
The trivial method would be to iterate through all triangles in a mesh, and add the other two members of each triangle containing the vertex to the set of neighbors.
There are a few caveats:
- Meshes may have duplicate vertices, which implies that one vertex may have multiple indices in the vertex array. You will have to take all those duplicates into account to avoid duplicate neighbors and to avoid missing neighbors.
- Meshes may have duplicate triangles which use duplicate vertices.
I would go about this by first building a vertex duplicate map (dictionary) that maps (the indices of) all duplicates of a vertex to the (index of the) duplicate with the least index. This step needs to be done only once for any number of input vertices. Then, iterate through all triangles in the mesh and for each triangle first resolve the duplicates and check if any one vertex in the triangle is one of the input vertices. If it is, add the other two resolved vertices to the neighbor set.
The easiest way I can think of is by searching the triangle index. The pattern is always the same, always 3 indices define a vertex. since you know the index of your vertex, you can just search the triangle array and return the other two of any triangle, which will give you all vertices within the range of the desired one.
There has been several similar questions in the past. Are you sure you searched before posting a question?. A general solution is quite complicated and it highly depends on how your mesh topography looks like.
You can build the corresponding graph by employing an adjacency list and then query that list,
this will be O(|V|+|E|) and thus might be not good for densely connected graphs, i.e. |E|=|V|^2.