ScienceGuy's blog

Sorting by polar angle
By ScienceGuy, history, 6 years ago, In English

I am trying to sort vector of points (pairs of integers) by the polar angle in counter-clockwise order around the first entry of the vector. I get wrong output, but can't find the problem in the code. I will appreciate it if you point out what I'm doing wrong. Here is my code: https://pastebin.com/mn6jZgyF

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

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

The comparison function has to be a strict weak ordering. Yours isn't. You keep the point at index 0 in the array you are sorting, and according to your comparison function this point is equivalent ("equal") to any other point because the cross product is always zero.

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

Use this compare:


comp(a,b)
{
if(quarter(a)==quarter(b))
return cross(a,b)>0;//or cross(a,b)<0
else
return quarter(a)<quarter(b);

}
→ Reply