Assertion failures in constrained Delaunay triangulation with GTS

StackOverflow https://stackoverflow.com/questions/6387846

  •  29-10-2019
  •  | 
  •  

Question

I'm getting some intermittent assertion failures when doing constrained Delaunay trianguation with the GNU Triangulated Surface Library. I've seen each of the following at different times:

Gts:ERROR:cdt.c:974:remove_intersected_vertex: code should not be reached Gts:ERROR:cdt.c:896:remove_intersected_edge: assertion failed: (next) Gts:ERROR:cdt.c:887:remove_intersected_edge: assertion failed: (o2 == 0.)

I've looked at cdt.c but all I've been able to figure out is that they're coming from calls to gts_delaunay_add_constraint.

Could someone explain what might be the problem with the constraints, that would cause these assertions to fail?

The assertion failures are happening when I try to do triangulation on a set of random vertices. It only happens, unfortunately, for large numbers of vertices and constraints, so it's hard to figure out a pattern for the failing inputs. The code that's using GTS needs to not crash even for bad input, so it would be nice to prevent these assertion failures, otherwise I'll have to disable the assertions.

Edit: Tried removing all intersecting constraints (stored in edges): 

int numPossEdges = gts_fifo_size(edges);
GtsEdge **possEdges = malloc(numPossEdges * sizeof(GtsEdge *));
for (int i = 0; i < numPossEdges; ++i)
    possEdges[i] = gts_fifo_pop(edges);
for (int i = 0; i < numPossEdges; ++i)
    for (int j = 0; j < i && possEdges[i] != NULL; ++j)
        if (possEdges[j] != NULL && GTS_IN == gts_segments_are_intersecting(&(possEdges[i]->segment), &(possEdges[j]->segment)))
            possEdges[i] = NULL;
for (int i = 0; i < numPossEdges; ++i)
    if (possEdges[i] != NULL)
        gts_fifo_push(edges, possEdges[i]);

Still getting the same assertion failures.

Was it helpful?

Solution 2

The code that's using GTS needs to not crash even for bad input, so it would be nice to prevent these assertion failures, otherwise I'll have to disable the assertions.

I ended up writing a patch that causes GTS to (basically) throw an exception instead of halting when it hits an assertion failure. The patch is here.

OTHER TIPS

If you're creating vertices and constraints completely randomly, I imagine you might be supplying constraint edges that intersect each other. In which case I would certainly expect the triangulation routines to complain.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top