eightnoteight's blog

Bug in this convex hull implementation.
By eightnoteight, 10 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why did you use atan2 for polar sorting?
you can just use ccw to do it. a < b <=> ccw(a0, a, b) == RIGHT
and it is better to return {-1, 0, 1}, not bool

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply