ConvexHullGenerationException for simple square

[Jordan181]

I believe I have found a very simple case for which a delaunay triangulation cannot be calculated. The points used are: (-1, -1), (-1, 1), (1, -1), (1, 1)

I believe any square across (0, 0) will cause a ConvexHullGenerationException to be thrown when calling DelaunayTriangulation<...>.Create(..);

[micampbell]

Yes, this is a special case that David and I talked about years ago. I think there is a solution, but I think the code will need to be cleaned up first to discover the best place to put it. One solution was to add noise to the points which give the system robustness since equal and opposite coordinates seem to cause issue.

[Jordan181]

Hi Matt, thank you for your reply. Are there any plans to patch this soon?

[mc0re]

I stumbled on another similar example: (-1, 0), (0, 1), (1, 0), (0, -1) Throws an exception in FindInitialPoints().

[Jordan181]

I've since discovered that this extends to any regular polygon centered on (0,0) for which the points can be represented exactly.

Also, perhaps this is a related issue but a different case, these points: (0,0) (0,50) (5000,0) (5000,50) Do not throw an exception, but return a triangulation with 0 triangles.

[spaaaaam]

Hello,

stumbled upon the same problem while upgrading from nuget 1.1.19.504 to 1.1.19.1019.

Will revert to the previous version for now, but would happily test any fix.

Cheers

[TysonCodes]

Hello,

I seem to have found additional weirdness with simple squares. Using d5f3a77489f7f6c29ad954b29bfeaf8e4f4b646b (Oct 19, 2019) I get a similar exception about it being degenerate using these points: (100, 100) (100, 395.03999999999996) (438, 100) (438, 395.03999999999996) This seems to be in ConvexHullAlgorithm.FindInitialPoints() where it detects a negligible volume.

Interestingly enough, if I instead use the following (just use MakeGrid(2, vs) instead of (10, vs) in Project 4) it generates an invalid triangulation (3 triangles where one overlaps the other 2): (0, 0) (0, 495.03999999999996) (538, 0) (538, 495.03999999999996)

Also, if I update to the newest version (241b1179e63d12e80ea689436bc37045553a53eb) from July 12, 2020 then the first set of points no longer give an exception and instead generate 2 triangles but they are still invalid as they half-way overlap. The second set of numbers continue to generate 3 triangles that overlap. Not sure if any of that helps narrow down the issue.

Thanks so much for this useful library!

[mc0re]

The following 2D points also generate ConvexHullGenerationException exception in Triangulation.CreateDelaunay:

(0, 0),
(0, -2),
(-0.71, -1.5),
(-0.71, -0.5)

MIConvexHull version 1.1.19.1019