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\$
3
  • 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, 2020 at 15:47
  • \$\begingroup\$ Edited my answer to be a little clearer. \$\endgroup\$
    – Engineer
    Jul 15, 2020 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, 2020 at 20:56

2 Answers 2

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.

\$\endgroup\$
1
  • \$\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, 2020 at 20:33
0
\$\begingroup\$

You can try the Quad-Edge data structure introduced by Guibas & Stolfi (1985). It puts all adjacencies in groups of 4 directed edges - 2 for each dual versions of the graph, or in other words the directed edges which connect 2 vertices and those that connect the corresponding 2 faces.

I found it hard to grok; especially the code that works with it. But it leads to dense code and quite normalised data structures, and other approaches might be even harder to follow.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .