# Reducing adjacency bookkeeping work in constrained Delaunay triangulation

I'm using the Sloan algorithm for constraining a generated Delaunay triangulation. This primarily consists of edge flipping for the edges that overlap the constrained edges.

In order to flip an edge, I have to know what two triangles contain that edge, and so for every edge I currently maintain an index (into the triangle array) of the current and opposite triangles for that edge. This gets built from the triangle array, where each triangle maintains indices for all adjacent triangles.

While this works, I've found that the vast bulk of my code is dealing with the maintenance of these triangle adjacencies. Every time an edge gets flipped, I not only have to update the two triangles that share the edge, but also update all of the other neighboring triangles that may have adjacency to one of those triangles, as well as go through and update any adjacency indexes within my list of edges to be flipped.

And then again, after the edges are flipped and you get a list of final "good" edges to use, you have to go through them and make sure they still satisfy Delaunay circumcenter rules, and if not, flip them again. Which means repeating all of the same work to maintain adjacency indexes.

Is there an algorithm for efficiently maintaining triangle/edge adjacency without all of this work? Or, better, is there an efficient method of determining neighboring triangles that share a common edge without the need to maintain these links?

I feel like I'm doing more adjacency maintenance than actual triangulation...

• I've heard this issue raised with multiple different mesh adjacency approaches. There's some discussion of the problem and some alternatives here, though I can't say whether they're any improvement for your use case. Jul 15, 2020 at 15:47
• Edited my answer to be a little clearer. Jul 15, 2020 at 19:10
• @DMGregory That actually does help. The article suggests tracking not only the adjacent triangles, but also the index of the shared edge on the other side, which would eliminate multiple loops where I try to determine which vertices contain an edge. Jul 15, 2020 at 20:56