How do you polar sort?

Revision en2, by Alpha_Q, 2020-01-04 23:00:16

Say yo want a set of points sorted in some counterclockwise order. What is the best (fast, precise, short) way to do it? The atan2l function is precise and short but way too slow. I do it like this (tested on 68208420).

sort(v.begin(), v.end(), [] (point a, point b) {
  bool x = a.y >= 0, y = b.y >= 0;
  return x == y ? a.x * b.y > a.y * b.x : x < y;
});

Just wondering if there's something even shorter.

Update: the above code works only for set of points with no three collinear. The following version (way longer) seems to work for all inputs.

inline int quad (point p) {
  if (p.x < 0 and p.y < 0) return 0;
  if (p.x >= 0 and p.y < 0) return 1;
  if (p.x >= 0 and p.y >= 0) return 2;
  if (p.x < 0 and p.y >= 0) return 3;
  assert(69 == 420);
}

sort(v.begin(), v.end(), [] (point a, point b) {
  return quad(a) == quad(b) ? a.x * b.y > a.y * b.x : quad(a) < quad(b);
});
Tags geometry, godblessamerica

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English Alpha_Q 2020-01-05 00:33:03 62
en10 English Alpha_Q 2020-01-05 00:21:53 237 Reverted to en7
en9 English Alpha_Q 2020-01-05 00:18:40 37 Tiny change: '});\n~~~~~' -> '});\n~~~~~\n\nReference: [submission:68213997].'
en8 English Alpha_Q 2020-01-05 00:16:42 200
en7 English Alpha_Q 2020-01-04 23:59:16 539 Tiny change: ' too slow. \n\n**Upda' -> ' too slow.\n\n**Upda'
en6 English Alpha_Q 2020-01-04 23:27:29 8
en5 English Alpha_Q 2020-01-04 23:25:59 41
en4 English Alpha_Q 2020-01-04 23:23:45 13 Tiny change: 'g version (way longer) seems to ' -> 'g version seems to '
en3 English Alpha_Q 2020-01-04 23:22:23 291
en2 English Alpha_Q 2020-01-04 23:00:16 504 Tiny change: '});\n~~~~~' -> '});\n~~~~~\n'
en1 English Alpha_Q 2020-01-04 21:38:47 467 Initial revision (published)