Convex Hull Bug (and odd copy/paste behaviour)

[AndersDeleuran]

Hi @DavidRutten/Grasshopper Devs,

I’ve been implementing MIConvexHull.dll for computing 2D convex hulls. And it’s been super reliable, but I am trying to drop this dependency in favour of Grasshopper.Kernel.Geometry.ConvexHull (for issuing concerns). This method will however occasionally return wrong/unpredictable results and is thus less reliable (assuming I’m using it as intended).

Here’s a minimal example using the compiled Grasshopper component, where I’ve isolated a set of points that produces a bad hull. Yet it will work as expected if one copy/pastes the points. Maybe some floating point rounding error is at play:

210520_ConvexHullDebug_Source_00.gh (3.1 KB)

Best,

Anders

Update: Inspecting the copied points does in fact reveal a slight decimal difference. Which explains the copy/paste mystery. Why the original points fail to produce a good hull is still a mystery (to me) though:

210520_ConvexHullDebug_Source_01.gh (8.0 KB)

[DanielPiker]

Not sure what’s going on with the standard convex hull component here, but perhaps one workaround if you want to stick with native GH methods could be to use the Delaunay solver (Grasshopper.Kernel.Geometry.Delaunay.Solver.Solve_Mesh), which doesn’t seem to have this bug, and take the external edges of this mesh.

[AndersDeleuran]

Ah yes, that’s a clever workaround. Cheers Daniel.

From a quick test (I’m computing ~50000 hulls for a noise analysis pipeline, implementing the ISO 9613-2 standard) rounding the components of the input points appears to “solve” this bug. I think I’m going to just go with this that for now. And keep using MIConvexHull.dll if I start seeing more oddities.

I’m sure you guys already are well aware, but MIConvexHull seems to be pretty great. And is written in C# under the MIT license. It might be worth considering adding it to RhinoCommon (or look to it for developing e.g. stable 3D hulls etc.).