ConvexHullGenerationException for simple square about miconvexhull HOT 7 OPEN

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.

from miconvexhull.

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

from miconvexhull.

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

from miconvexhull.

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.

from miconvexhull.

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

from miconvexhull.

Hello,

I seem to have found additional weirdness with simple squares. Using d5f3a77 (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 (241b117) 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!

from miconvexhull.

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

from miconvexhull.