Handling degeneracies

[ramcdona]

Thanks for all your work and for making this convex hull library available. I am evaluating it for use in my program.

My data sets will often contain a bunch of co-planar points. In my first tests with your tool, these cause if ( !qh.check() ) to fail. In your example, this test is accompanied with the comment // resulted structure is not convex (generally due to precision errors).

If I go ahead and try to make use of the resulting mesh, I get something messy like the following:

Is convhull expected to work in cases like this? Does convhull use robust geometric predicates for things like the 3D orientation test?

I have attached a points file corresponding to this test case.

test.txt

[tomilov]

No, currently it is not expected the code to work in cases like yours. Stable, robust calculations are difficult for the whole algorithm to maintain.