Skip to content

Instantly share code, notes, and snippets.

@gylns
Created June 24, 2016 11:15
Show Gist options
  • Save gylns/638fdadea747d35534cb8b1b8e8a2688 to your computer and use it in GitHub Desktop.
Save gylns/638fdadea747d35534cb8b1b8e8a2688 to your computer and use it in GitHub Desktop.
//sorting points by clockwise using cross product
//see <http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order>
bool less(point a, point b)
{
if (a.x - center.x >= 0 && b.x - center.x < 0)
return true;
if (a.x - center.x < 0 && b.x - center.x >= 0)
return false;
if (a.x - center.x == 0 && b.x - center.x == 0) {
if (a.y - center.y >= 0 || b.y - center.y >= 0)
return a.y > b.y;
return b.y > a.y;
}
// compute the cross product of vectors (center -> a) x (center -> b)
int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
if (det < 0)
return true;
if (det > 0)
return false;
// points a and b are on the same line from the center
// check which point is closer to the center
int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 > d2;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment