Crash when two polygons share the same vertex

[reinterpretcat]

Triangle lib seems to crash when two polygons share the same vertex, e.g.:
{ { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } }
{ { 10, 10 }, { 15, 10 }, { 15, 15 }, { 10, 15 } }

I used the following params: pzB

However, .NET port is working in this case.

[wo80]

Triangle ignores duplicate input vertices. This will cause a problem, if you reference such a vertex in the segmentlist.

The .NET version is doing the same thing. It doesn't crash because the segments reference the vertex instances directly and not by an index array. Still, one of the segments that share the duplicate vertex will reference the ignored vertex, that is not part of the mesh (that means: it's not connected to any triangle and will have vertex type = UndeadVertex). Though this will work fine most of the time, it might lead to subtle bugs and should be documented somewhere, so thanks for bringing up the issue :-)

[reinterpretcat]

Thanks for information.
Is there any way to fix the crash and have behavior similar to .NET port? It is much better than crash. Sometimes it is not possible to avoid duplicates by data preprocessing

[wo80]

It's actually not what I thought. The original Triangle executable works fine with the following poly file:

8 2 0 1
1   0  0 1
2  10  0 1
3  10 10 1
4   0 10 1
5  10 10 2
6  15 10 2
7  15 15 2
8  10 15 2
8 1
1 1 2 1
2 2 3 1
3 3 4 1
4 4 1 1
5 5 6 2
6 6 7 2
7 7 8 2
8 8 5 2
0

So, the problem is in the insertsegment method:

checkvertex = (vertex) NULL;
encodedtri = vertex2tri(endpoint1);
if (encodedtri != (triangle) NULL) {
    decode(encodedtri, searchtri1);
    org(searchtri1, checkvertex);
}

if (checkvertex != endpoint1) {
    ...
}

For the duplicate vertex, you'd expect encodedtri to be NULL, but you get 0xcdcdcdcd.

Don't know when I get some time to look into this. The first thing to do would be:

• Check if the original Triangle code compiled as DLL fails.
• If it doesn't fail, find the first commit of this project that fails and compare.

[reinterpretcat]

According to https://en.wikipedia.org/wiki/Magic_number_(programming), 0xcdcdcdcd is uninitialized heap memory. Just checked: looks like compiling in Win32 release helped, but not in x64.

[reinterpretcat]

In x64 release, I was able to fix it with additional check:
if (encodedtri != (triangle)NULL && vertextype(endpoint1) != UNDEADVERTEX)

[wo80]

Well, it's not really a fix, just a workaround. I think to fix the issue, you should look where UNDEADVERTEX gets set (by setvertextype), and then add

if (b->poly) setvertex2tri(vertex, NULL);

I'm not an expert at C, so please help me to understand:
we're getting no crash in release mode just by coincident, the pointer to the triangle could just as well be non-NULL and make insertvertex fail, right?

Anyway, I'll re-open the issue for now.

[reinterpretcat]

I'm not expert in C too.
I've just checked your solution and it seems to work too:

f (!b->quiet) {
        printf(
"Warning:  A duplicate vertex at (%.12g, %.12g) appeared and was ignored.\n",
               sortarray[j][0], sortarray[j][1]);
      }
      setvertextype(sortarray[j], UNDEADVERTEX);
      if (b->poly) setvertex2tri(sortarray[j], NULL);
      m->undeads++;

in divconqdelaunay function