Passing in a mesh with 30000 coplanar vertices causes a very long hang

[epitaque]

This is quite the edge case, but there is a quadruple-for loop in FindInitialHullIndices each vertex that can cause programs to stall. It's a O(n^4) algorithm.

[OskarSigvardsson]

It's been a couple of years since i wrote this code, and the details are a bit fuzzy. But I've been thinking about your comment, and the ONLY time it would take O(n^4) is if literally all points are coplanar, in which case the 3D convex hull is not really defined (and indeed the code throws in that case). What I think you're looking for in that case is the 2D convex hull, which you should find a specific algorithm/library for. I wrote a different library for calculating 2D Delaunay triangulations which you could use to to get the convex hull (just project your points onto a 2D plane, calculate the Delaunay triangulation and extract the boundary), but even that is overkill. There are specific algorithms for finding the 2D convex hull that are much faster.

I've been thinking about your comment for a bit, and I think that there is literally only one case where the algorithm is O(n^4), and that is if all points are coplanar, otherwise it's O(n). So it's a very degenerate case.

I have two suggestions: if you don't wanna change my code (and I'm a little bit hesitant to myself, given that it's been a couple of years), you can make a function that first checks if all your points are coplanar, and then just not pass them into the algorithm. You can use my AreCoplanar function for that if you want.

However, the better solution (I think) is to simply error out much sooner: if the innermost loop fails to find the fourth point, then i think that means that all points are coplanar, so there's no point trying anything further. So if you move the throw from line 492 to just after line 487, that would error out in O(n). If you make that change and test it some, I'd be happy to merge the PR.

Also: I don't think there's ever any reason to loop the first point. I think the outermost loop can be removed entirely.

[OskarSigvardsson]

To be clear: if all points are coplanar, there's nothing sensible to do. The best case is to just error out earlier, which is what the change i suggested will do.