inconsistent triangulation for 3 points

[maweigert]

Hi,

First, thanks a lot for this useful implementation!

I was playing around with a simple example of a unconstrained triangulation of 3 points (that should always give a single triangle) but found it to yield inconsistent results for specific inputs and when called several times:

#include <iostream> 
#include "CDT.h"

int main(int argc, char *argv[])
{

  std::vector<CDT::V2d<float> > points;  
  points.push_back(CDT::V2d<float>::make(  1. , 0.   ));
  points.push_back(CDT::V2d<float>::make(  0 , 0.251 ));
  points.push_back(CDT::V2d<float>::make( -1. , 0.   )); 

  for (int i=0 ; i < 4; ++i) {

    CDT::Triangulation<float> cdt;  
    cdt.insertVertices(points);
    cdt.eraseSuperTriangle();

    std::cout << "found " << cdt.triangles.size() << " triangles" << std::endl;
  }

  return 0;
}

with the output

found 1 triangles
found 0 triangles
found 0 triangles
found 1 triangles

Is there something fundamentally wrong with how I am using CDT? Note that changing the y value of the second point from 0.251 to something larger eg 0.252 yields the expected result:

found 1 triangles
found 1 triangles
found 1 triangles
found 1 triangles

[artem-ogre]

Hi Martin,

Thank you for reporting this issue. I am away from the keyboard, but I will get to it as soon as I am back next week.

At a quick glance your example should always produce exactly one triangle indeed.

Potential reason for different results could be the recently introduced randomized order of vertex insertion. Pseudo-random number generator is only seeded once so invoking insertVertices many times sequentially can produce different orders of inserting vertices. Fix for this is currently in progress: seeding generator with the same seed inside insertVertices. Of course, final result should not depend on the vertices’ order of insertion, so maybe randomized vertex insertion exposes a bug elsewhere in the implementation.

Meanwhile, can I ask you to do few more tests? What happens if CDT is constructed with VertexInsertionOrder::AsProvided? Does the result become deterministic? If yes, what happens when manually inserting vertices into the vector in different order (three possible combinations) while still using VertexInsertionOrder::AsProvided? If some particular combination produces wrong result this narrows down the problem significantly.

Also if VertexInsertionOrder::AsProvided works for your inputs it could be used as a temporary work-around.

[maweigert]

Hi Artem,

thanks a lot for the fast response!

Meanwhile, can I ask you to do few more tests?

Indeed, with VertexInsertionOrder::AsProvided the number of triangles is consistent, however it is now consistently 0 :)

If some particular combination produces wrong result this narrows down the problem significantly.

Yes, it is indeed depending on the permutation. Here's the output for all 6 permutations of the original 3 points:

points:
-1 0
0 0.251
1 0
----> 1 triangles

points:
-1 0
1 0
0 0.251
----> 0 triangles

points:
0 0.251
-1 0
1 0
----> 0 triangles

points:
0 0.251
1 0
-1 0
----> 0 triangles

points:
1 0
-1 0
0 0.251
----> 1 triangles

points:
1 0
0 0.251
-1 0
----> 0 triangles

[artem-ogre]

Indeed, with VertexInsertionOrder::AsProvided the number of triangles is consistent, however it is now consistently 0 :)

Ouch! :) I will do my best to fix this promptly.

Could you pick one of the configurations producing wrong result and print triangles before calling eraseSuperTriangle()?

[maweigert]

Could you pick one of the configurations producing wrong result and print triangles before calling eraseSuperTriangle()?

Sure:

points:
1 0
0 0.251
-1 0

triangles (before erase):
0 1 4
1 2 3
2 0 5
3 4 1
3 2 4
0 4 5
4 2 5

number of triangles (after erase)
0

[IslamOmar-360Imaging]

Hi, By moving super triangle points far away, so that CDT would prefer triangles with the inserted points. Kindly check that PR resolves this issue.

[artem-ogre]

Thank you very much @IslamOmar-360Imaging

Yes, the problem is in the edge-flip test which produces wrong edges. So fixing super-triangle vertices is a kludge that can be used as a temporarily workaround for now. I will fix edge-flip test ASAP (next week).

[artem-ogre]

Of course you may look into the edge-flip test yourself ;) But I will only be able to merge any PRs when I am back to the keyboard.

[maweigert]

Thanks a lot for the super fast reply!

Kindly check that PR resolves this issue.

Ok, this fixes the problem with the original set of points. However for the following set of 3 points, the issue persists:

std::vector<CDT::V2d<float> > points
points.push_back(CDT::V2d<float>::make( -0.3 , -0.2 )); 
points.push_back(CDT::V2d<float>::make( -0.9 ,  0.9 ));
points.push_back(CDT::V2d<float>::make(  0.6 , -1.0 ));

[Islam0mar]

Kindly recheck this PR.

Žalik et. al [1] wasn't explicit when you have non-shared vertex and shared vertex both belong to the super triangle.

Let us construct a line through the triangle non-artificial vertices (i and j for example).

[1] Borut Žalik and Ivana Kolingerová, An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm,International Journal of Geographical Information Science,Volume 17,Issue 2,Pages119-138,2003,DOI 10.1080/713811749.

[maweigert]

Kindly recheck this PR.

Looks like that fixed it! Thanks a lot! :)

[artem-ogre]

@maweigert

67 was merged to master. I am closing the issue, thank you guys for your help.