EternalFire's blog

By EternalFire, history, 6 years ago, In English

How to sort points in clockwise/counter-clockwise order efficiently? I use atan2 to get angle created by Ox axis and point but it seems slow and sometimes it causes precision error. Appreciate for any help.

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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Check and compare the quadrants first, then do a CCW calculation only if two points are in the same quadrant.

»
6 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

You can use cross product. For example this is the solution for URI 2541.

Code

The indexes of points are sorted here.