Triangular mesh topology

I've got a triangular mesh class which contains a list of nodes (2d in my case but that shouldn't matter) and a list of faces. Each face is a triangle and it only contains the indices into the node array. The mesh comes out of a Delaunay algorithm so it's very clean.

For every node in the mesh I need to find which nodes are connected to it with a single edge. What would be a fast way to construct and search this topology database?

Much obliged, David Rutten

Solution

There are two somewhat-standard data structs that facilitate mesh topology-queries. One is Winged Edges (commonly referred to also as half-edge), and the other is Directed Edges. Google around and you'd get kajillions of details, and various-level intros into each one.

Don't know enough about your scenario to recommend one of them. E.g., directed edges is storage-optimized, and best suited for very large meshes. Winged edges is considered a 'classic', and is a good starting point for more advanced flavours.

Actually if you're certain that's the only query you'd need, then both are an overkill and you'd do just fine with a single hash. If, however, you find yourself in need of efficient answers to queries like -

Which faces use this vertex?
Which edges use this vertex?
Which faces border this edge?
Which edges border this face?
Which faces are adjacent to this face?

You should consider diving into one of them.