6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you just scale your numbers up? $\endgroup$ – Quantum_Oli Jul 13 '16 at 7:34
  • $\begingroup$ 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... $\endgroup$ – DPF Jul 13 '16 at 7:35
  • 1
    $\begingroup$ 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... $\endgroup$ – Quantum_Oli Jul 13 '16 at 7:39
  • $\begingroup$ 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} $\endgroup$ – DPF Jul 13 '16 at 9:12
  • 1
    $\begingroup$ @DPF Do you have any other examples not including zero where this problem appears? It seem that in the case of the original example Region`Mesh`DeleteDuplicateCoordinates 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. $\endgroup$ – Mr.Wizard Jul 13 '16 at 12:41
6
$\begingroup$

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 Region`Mesh`DeleteDuplicateCoordinates

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 = Region`Mesh`DeleteDuplicateCoordinates[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 TriangleLink`TriangleDelaunay and trouble ensues:

TriangleLink`TriangleDelaunay @ expr2[[1]]

TriangleLink`TriangleDelaunay::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:

TriangleLink`Private`iTriangleFun[{TriangleLink`TriangleDelaunay, 
  "-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 @ TriangleLink`Private`iTriangleFun

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, TriangleLink`Private`pack[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[
    TriangleLink`Private`iTriangleFun[{TriangleLink`TriangleDelaunay, 
       "-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.

$\endgroup$
  • $\begingroup$ Wow, you're digging deeply :). Even though scaling just solves my problem, this behaviour is not quite intuitive. $\endgroup$ – DPF Jul 13 '16 at 10:15
  • $\begingroup$ @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." $\endgroup$ – Mr.Wizard Jul 13 '16 at 11:15
  • $\begingroup$ @DPF Now I have an answer that I think will be of general interest. Please see my addendum. $\endgroup$ – Mr.Wizard Jul 13 '16 at 11:41
  • 1
    $\begingroup$ @DPF I might be about to look very foolish as I can't seem to reproduce my results now. :-O More work needed! $\endgroup$ – Mr.Wizard Jul 13 '16 at 12:03
  • 2
    $\begingroup$ @Mr.Wizard a delaunay triangulation can have a certain amount of randomness in the algorithm. Maybe that's the cause. Great work so far. $\endgroup$ – user21 Jul 13 '16 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.