2
\$\begingroup\$

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...

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Jul 15 at 15:47
  • \$\begingroup\$ Edited my answer to be a little clearer. \$\endgroup\$ – Engineer Jul 15 at 19:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Nairou Jul 15 at 20:56
2
\$\begingroup\$

You should be encapsulating in functions / methods as much as possible such that repetition is ultimately minimal (seek and extract common factors, ad nauseam). But that goes without saying.

The other way to view this is that you need some independent, reactive component that does the necessary things automatically, each time you modify the set, by "watching" when the set container changes. This at least takes the management logic out of your main body of code.

You could write a module that represents the collection of nodes (and edges, if these are distinct in your implementation) which, every time a node / edge is added to or removed from the set, calls one of its own helper functions to perform the necessary auxiliary updates. Access this module from your primary (cleaner) code, via the appropriate functions, to avoid excess management.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ While I completely agree, I was more wondering if there way a way to reduce the work being done (perhaps by a method other than adjacency tracking), rather than only encapsulating what I'm currently doing. \$\endgroup\$ – Nairou Jul 15 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.