Sorting points by polar angle
Posted on 2005-04-19
Having point p0(x0, y0) and list of points p1, p2... pn I want to sort this list by polar angle in counterclockwise order around p0. p0 is most bottom-left point. This is first step of Graham's scan algorithm of convex hull problem.
All point coordinates are integer values. I need to count some criteria for each point p1...pn which allows to sort them. I can find the angle for each point using trigonometric functions, but I see two problems of this approach: performance and precision. Is there a way to do this using only integer calculations?
I can find cross-products between vectors p0(x0, y0) -> p(x0 + a, y0) and p0(x0, y0) -> pi (i=1...n, a is some integer value). This is pure integer calculation, but value of cross-product is affected both by vectors direction and length, and I need the value affected only by direction.