Navid Koochooloo - 1 month ago 8
Java Question

# Sorting points by their polar angle in Java

I'm using Graham scan algorithm to find the convex-hull of set of points
I'm trying to sort the points by their polar angle but I have no idea how to do it (I've already sorted the set of points by their Y coordinates).

What I've already wrote is like this:

``````public double angle(Coord o, Coord a)
{
return Math.atan((double)(a.y - o.y) / (double)(a.x - o.x));
}
``````

where
`Coord`
is the class where I have X and Y coordinates as
`double`
.

I also looked at one of the similar posts in Stack Overflow where someone had tried to implement this angle with C++, but I don't understand
`qsqrt`
. Do we have something like this in Java?

``````qreal Interpolation::dp(QPointF pt1, QPointF pt2)
{
return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
}
``````

I'll be glad if anyone can help me.

In other words, you can just sort by `- (x - x1) / (y - y1)` (where (x1, y1) are the coordinates of your starting point), which will be faster to calculate. First you'll need to separate points where `y == y1`, of course, and add them to the top or bottom of the list depending on the sign of (x - x1)`, but they're easy to identify, since you've already sorted by y to find your starting point.