Initially I tried to make gift wrapping handle collinear points better. Conclusion: gift wrapping is a bad algorithm.
So I removed gift wrapping and implemented quickhull. I also added code to explicitly remove collinear points. This turns out to be quite easy once you have a convex hull.
I ran over 200 million randomized tests successfully with test data that is very likely to have collinear points with small numerical deviations. All the tests passed and algorithm correctly rejects very close points and fully collinear points.
I also tested performance at around 150 milliseconds per million hulls.
I split out the convex hull code into a separate function b2ComputeHull. This lets people build hulls offline and check for hull validity before using them in b2PolygonShape.
Initially I tried to make gift wrapping handle collinear points better. Conclusion: gift wrapping is a bad algorithm. So I removed gift wrapping and implemented quickhull. I also added code to explicitly remove collinear points. This turns out to be quite easy once you have a convex hull.
I ran over 200 million randomized tests successfully with test data that is very likely to have collinear points with small numerical deviations. All the tests passed and algorithm correctly rejects very close points and fully collinear points.
I also tested performance at around 150 milliseconds per million hulls.
I split out the convex hull code into a separate function
b2ComputeHull. This lets people build hulls offline and check for hull validity before using them inb2PolygonShape.This video is a good reference for the 2D quickhull algorithm (my implementation is different): https://www.youtube.com/watch?v=2EKIZrimeuk
Fixes: #671 #728