I wrote this convex hull implementation after reading some material on it.
https://gist.github.com/4ab7ef53421fafc12608
output:
but when i change the ccw function from
return ((b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])) > 0
into
return ((b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])) >= 0
I am getting incorrect results. output:
I'm changing it to remove collinear points on the convex hull. please help me, thanks in advance.
why did you use atan2 for polar sorting?
you can just use ccw to do it.
a < b <=> ccw(a0, a, b) == RIGHTand it is better to return {-1, 0, 1}, not bool
actually i'm using the polar angle in radians with respect to the minimum y-coordinate point as the key function to sort the points.
I understood what you do. It was just advise to make all computations in integers.
Your modification of algo doesn't work because your sort doesn't properly align points on one line. It can swap it and ccw return true but shouldn't. For example points [(10, 0), (8, 2), (7, 3), (10, 3)]. Sort can return [(10, 0), (7, 3), (8, 2), (10, 3)] and point (8, 2) will be thrown away