Convex Hull fails to create for co-linear points

[radumg]

Hi, first off, many thanks for the great work in this library! We've been using it in an open-source library called RefineryToolkits and have found an issue that we wanted to discuss.

It seems that ConvexHull fails to be created when the input points are co-linear. Specifically, this line of code does not throw, but returns a null when points are co-linear.

            var convexHull = MIConvexHull.ConvexHull.Create(vertices);

Example

Below is a list of points with the coordinates that highlighted the failure during a recent hackathon :

X 260 Y 600
X 285 Y 600
X 310 Y 600
X 335 Y 600

To solve this in short-term, we are adding a co-linearity check in our library and handle that case separately, but was wondering if it's something that you'd like to address in the MIConvexHull library itself so everyone has access to the fix ?

Let us know 👍

[micampbell]

Yes, I would like to see it. The 2D version of the code is a special case and was the last thing that I added. It is meant to be fast but this is important to check. However, if someone is doing 1000+ points, then I wouldn't want this to slow things down especially since the probability that they would all be co-linear would be highly unlikely. So, if the check doesn't add much additional overhead, I would like to include it in the package. Now that you have brought it to my attention, I'm thinking of a way to do it by checking the 2D cross-product of the vectors points until one is found that is not too close to zero. Is that what you did?

[radumg]

Yep, that's what we're adding, checking pairs of vectors against the first pair and bailing at the first non-equal result.

For clarity, I'm in the process of writing it for our lib which uses its own vertex, points etc definitions, so not sure where this would sit within the MIConvexHull, but if it helps, happy to share once it works.

[micampbell]

Well, I found an easy place to fix this. There was already a function called "FindIntermediatePointsForLongSkinny" which I was able to make a small modification to so that it would return the two extrema along the line instead of crashing. For the general case, this adds no extra time. thanks for catching this!

[radumg]

Nice one 👏 !

Does that mean the will be a point release that will support making convex hulls from co-linear points ? I've just finished our code 🙈 , but happy to remove it if it's no longer necessary.

[micampbell]

yes, the nuget is updated (https://www.nuget.org/packages/MIConvexHull/) and the details of the commit are here: https://github.com/DesignEngrLab/MIConvexHull/commit/915cdb730594f388b475a0a39fff2fa4d9dd5400

[radumg]

Hi @micampbell ,

Just tried the updated NuGet package and had 2 things to report back :

• the MIConvexHull.ConvexHull.Create() method still returns null (used with dataset posted above)
• the assembly version is still reporting 1.1.19.504 whereas the NuGet is version 1.1.19.730

[micampbell]

The second is easy to fix. The first is because the inputs are all over the place for this project. If your Vertex can inherit from MIConvexHull.IVertex2D instead of MIConvexHull.IVertex or double[], then it should work. I'm trying to get it get the API straightened out so that the other two inputs will works as well for 2D.