ConvexHullMesh fails with small numbers

When I try to get the ConvexHullMesh of a List of points that are "small scale", I get errors:

ConvexHullMesh[{{5.2041704279304214*^-23,-2.0816681711721686*^-23}, {-2.999999999999993*^-8,-5.196152422706634*^-8}, {3.000000000000005*^-8, 5.19615242270663*^-8}, {6.245004513516506*^-23,-2.0816681711721686*^-23}}]


"A Delaunay triangulation could not be found from the points"

and

"The function ConvexHullMesh is not implemented for".

Is that due to some precision issues? How can I have the Algorithm give me a correct solution?

• Can you just scale your numbers up? Jul 13, 2016 at 7:34
• Yes. When I do that, the error is gone, Thank you! :) But I'm still wondering, why ConvexHullMesh[{{0,0},{-60,0},{60,0}}] seems to fail...
– DPF
Jul 13, 2016 at 7:35
• It appears to be because they are colinear and therefore essentially 1D. Note that ConvexHullMesh[{{0}, {-60}, {60}}] does work, as will your 2D case provided the points actually span a 2D space. Why this should be the case though... Jul 13, 2016 at 7:39
• Mhmm, I have a large list of point-collections, and want to get the convex hull for each of them (some seem to be colinear). Unfortunately, this error stops the further execution of the code... What I'd like to have from the algorithm in the above case is a line from {-60,0} to {60,0}
– DPF
Jul 13, 2016 at 9:12
• @DPF Do you have any other examples not including zero where this problem appears? It seem that in the case of the original example RegionMeshDeleteDuplicateCoordinates outputs slightly changed values, and it is these specific values that later trigger a sensitive bug. I am trying to figure out what else does this, and if there is more than one issue here or if they are all related. Incidentally I won't have more time to work on this today. Jul 13, 2016 at 12:41

Skip to the last section unless you have historical interest in my digging.

A quick Trace suggests a little of what may be going on.

The first step in the process is to call RegionMeshDeleteDuplicateCoordinates

expr = {{5.2041704279304214*^-23, -2.0816681711721686*^-23}, \
{-2.999999999999993*^-8, -5.196152422706634*^-8}, {3.000000000000005*^-8,
5.19615242270663*^-8}, {6.245004513516506*^-23, -2.0816681711721686*^-23}};

expr2 = RegionMeshDeleteDuplicateCoordinates[expr]

{{{5.9557*10^-23, -1.98523*10^-23}, {-3.*10^-8, -5.19615*10^-8},
{3.*10^-8, 5.19615*10^-8}}, {1, 2, 3, 1}}


Almost immediately the first part of this is passed to DelaunayMesh which hands off to TriangleLinkTriangleDelaunay and trouble ensues:

TriangleLinkTriangleDelaunay @ expr2[[1]]


TriangleLinkTriangleDelaunay::trifc: A Delaunay triangulation could not be found from the points {{5.9557*10^-23,-1.98523*10^-23},{-3.*10^-8,-5.19615*10^-8},{3.*10^-8,5.19615*10^-8}}. >>

$Failed  Digging into that reveals a yet inner call: TriangleLinkPrivateiTriangleFun[{TriangleLinkTriangleDelaunay, "-Q "}, {{5.955700410381799*^-23, -1.9852334701272664*^-23}, \ {-2.999999999999993*^-8, -5.196152422706634*^-8}, {3.000000000000005*^-8, 5.19615242270663*^-8}}]  This has a definition which can be read with: Needs["GeneralUtilities"] PrintDefinitions @ TriangleLinkPrivateiTriangleFun  I lost interest at this point, not finding any simple solution, but that might be a good place to start for anyone who cares to carry the baton. Location of the error Okay, I couldn't keep from wondering what happened next, which leads to this self contained example that returns a library error. Since I am not a low-level programmer I'll have to leave that to someone else, even if the library is readable. Needs["TriangleLink"] pts = {{5.9557*10^-23, -1.98523*10^-23}, {-3.*10^-8, -5.19615*10^-8}, { 3.*10^-8, 5.19615*10^-8}}; inInst = TriangleCreate[]; TriangleSetPoints[inInst, TriangleLinkPrivatepack[N[pts]]]; outInst = TriangleTriangulate[inInst, "-Q "]; TriangleGetSegments[outInst]  LibraryFunctionError["LIBRARY_FUNCTION_ERROR", 6]  Domain of the error Although I could not probe deeper into a Trace I wondered what would come from exploring the domain of the error, meaning what values actually case an error and which do not. Following Quantum_Oli's comment I wanted to see what scaling did. Working with the inner function found above: Needs["TriangleLink"] pts = {{5.955700410381799*^-23, -1.9852334701272664*^-23}, \ {-2.999999999999993*^-8, -5.196152422706634*^-8}, {3.000000000000005*^-8, 5.19615242270663*^-8}}; goodQ = Quiet[ TriangleLinkPrivateiTriangleFun[{TriangleLinkTriangleDelaunay, "-Q "}, #] =!=$Failed] &;


And simple scaling by multiplying by the first twenty natural numbers:

r1 = Table[goodQ[i*pts], {i, 20}]

{False, False, True, False, True, True, True, False,
True, True, True, True, True, True, True, False, True, True, True, True}


See the pattern? Let's make it obvious:

Position[r1, False]

{{1}, {2}, {4}, {8}, {16}}


Well that's funny indeed. Does it continue?

Or @@ Table[goodQ[ 2^i * pts ], {i, 500}]

False


Clearly scale is totally irrelevant; this has nothing to do with "small numbers" but instead is a pathological case that affects these particular numbers, and it is extremely sensitive!

goodQ[2^50.0000000000001*pts]
goodQ[2^50.0*pts]
goodQ[2^49.9999999999999*pts]

True

False

True


I am now confident enough to assert that there is a bug here. However I cannot yet see why this inner function is highly sensitive yet the original example with ConvexHullMesh` is not. I also question whether the "Location of the error" example is even correct as I truncated the inputs when I copied it to post here, yet the error message still occurs.

• Wow, you're digging deeply :). Even though scaling just solves my problem, this behaviour is not quite intuitive.
– DPF
Jul 13, 2016 at 10:15
• @DPF Sorry that I didn't find anything useful. At this point all I can say is that it might be a library problem or the library might be being used incorrectly. In either case it seems like something that I hope the developers can improve, even if it is just to give a more meaningful error message like "values too small for reliable TriangleLink library operation." Jul 13, 2016 at 11:15
• @DPF Now I have an answer that I think will be of general interest. Please see my addendum. Jul 13, 2016 at 11:41
• @DPF I might be about to look very foolish as I can't seem to reproduce my results now. :-O More work needed! Jul 13, 2016 at 12:03
• @Mr.Wizard a delaunay triangulation can have a certain amount of randomness in the algorithm. Maybe that's the cause. Great work so far. Jul 13, 2016 at 12:48