Solved

# Sorting points by polar angle

Posted on 2005-04-19
3,563 Views
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.
0
Question by:AlexFM

LVL 26

Expert Comment

If you are willing to presort them into quadrant groups, you can sort each group with just a division.
0

LVL 26

Accepted Solution

Quadrant I is positive x, positive y.

The polar angle of the point (x,y) is arctan(y/x).  But you don't have to calculate the arctan because it is monotonic increasing for points in the first quadrant.
--------------------------------------------
Quadrant II is negative x, positive y.

The polar angle of the point (x,y) is arctan(y/x).  The sign of arctan switches at x=0, but it is still monotonic increasing for the second quadrant.
--------------------------------------------

In fact it works for all four quadrants.

0

LVL 31

Expert Comment

This immediately comes to mind

(1) Firstly subtract p0 from each p1, p2... pn so you have the coords relative to the origin.

(2) Take those with a positive y component  and sort into decreasing order on the x cord

(3) Take those with a negative y component  and sort into increasing order on the x cord

(4) concatenate the 2 lists to give them sorted on increasing angle
0

LVL 26

Expert Comment

I don't think you can avoid a floating point division.

Your cross product idea has potential in theory.
But to make it work, you would have to normalize, and theat means square roots and divisions, more floating point operations.
0

LVL 31

Assisted Solution

...mine needs some more work, just looked it over again. you must divide each x cord by the distance from p0 before sorting, this has floating point unfortuantely.

(1) Firstly subtract p0 from each p1, p2... pn so you have the coords relative to the origin p0., then normalise each vector. (need only divide x coord by distance from p0)

(2) Take those with a positive y component  and sort into decreasing order on the x coord

(3) Take those with a negative y component  and sort into increasing order on the x coord

(4) Concatenate the 2 lists to give them sorted on increasing angle

0

LVL 48

Author Comment

Thanks, I understand both ideas. I will keep this question opened for some time hoping that somebody has pure integer solution.
0

LVL 6

Expert Comment

pure integer solution below, but first:

I think you are wrongly forced to use integer, not because of the software/memory limitations, but because you are dealing with pixels.

to reduce the error of your coordination while moving from kartezian to polarian presentation, you should do ALL calculations with real numbers (not integer) .
EVEN the sorting should be done on real numbers.
else, you will get JUMPY counterclockwise.

==================

you can do something like EXTRAPOLATION:
assume xi,yi ranges from 0-1000 and p0(x0,y0) is somewere, ie (200,500)

new p0 = 500000,500000
foreach pi : = new_x1 = (xi-x0)*500+new_x0 , new_yi = (yi-y0)*500+new_y0

by doing this you achieve:
1) extracting your points array, now deviding integers is much more accurate.
2) keeping the original relative positions of all points.

add this to the obvious steps as Gwyn wrote above, and there you go,

tal

0

LVL 48

Author Comment

I think about keeping of (yi-y0)/(xi-x0) results as pairs of integers instead of floating numbers, and comparing between them:
{y1, x1} compare with {y2, x2}
is the same as:
(y1*x2 - x1*y2) compare with 0 (assuming that x1*x2 > 0).

Having y/x pair and comparing operation defined as y1*x2 - x1*y2 I can implement sorting by this criteria. Algorithm should handle properly xi=0 case and overflowing issues.
Does this make sence?
0

LVL 6

Expert Comment

it make sense , but not accurate - that was my prev commnet.
about xi=0: boundaries are always need special testing to check division-by-zero or other math-violations

in the extrapolation finction I posted above, I choosed 500000,500000 i purpose, and extrapolation coefficient = 500, to avoid the new position to be outside new boundaries.
0

LVL 6

Expert Comment

you should check the 4 quarters seperated.
foreach quarter, the rule about {x1,x2,y1.y2} lightly change.

1) sort x<0,y>0 => sort only points from that region,
2) x<0,y<0
3) x>0,y<0
4) x>0,y>0
0

LVL 48

Author Comment

From my question: p0 is most bottom-left point.
This means, there is only one quater.

I don't understand your extrapolation algorithm.

>> it make sense , but not accurate.
Why? For example, for p0 = (0,0), p1=(1,1) and p2=(2,2) comparing between p1 and p2 gives 0 (equal). Floating-point operation may give > or < than 0.
0

LVL 6

Assisted Solution

got you,
your scop is x>0,y>0 => if (y1x1-x1y2 >0) => p2 before p1

and YES, your function work perfect, just for p = p0, you need to musk such point since sorting will always give zero.
=======================
about 2 points with the same aspect ratio : define what is the order (close or far)
0

LVL 48

Author Comment

Thanks, I implemented pure integer approach.
One implementation problem I have it that it is imposible to use standard sort algorithms (like stl.sort or ArrayList.Sort from .NET) because they don't compare every member with each other. Instead of this I add every new point manually comparing it with all previous points. By the way I remove duplicate points and points with the same angle.
0

LVL 31

Expert Comment

oh dear, I missed the continuation of this over night as I could formulate a pure integer solution fairly easily, I was not sure what you were looking for.
0

LVL 31

Expert Comment

...ps. Thanks for the points. :-)
0

LVL 26

Expert Comment

Hello AlexFM

Thanks for the points.

I also didn't fully understand what you are trying to do until just now.   {I was thinking vector cross product, not ratio cross product.}

But maybe I can still help.

When you do a ratio cross product to compare  5/8 and 4/7    and get    5*7=35  is greater than  4*8=32   and so    5/8  >  4/7

What you are really doing is finding a common denominator by multiplying both sides by 8*7.

You don't have to find the least common denominator to do a valid comparison.

So what you you could do is look at all the points in a quadrant:  (x1, y1)  (x2, y2)  ...  (xn, yn)

And look at all the arctans:      y1/x1    y2/x2   ...   yn/xn

And multiply them all by    (x1*x2* ... *xn)  to find a common denominator.

This would let you use a canned sort function.

You can eliminate multiple factors (if x1=x5=7 you only have to include one of them), but you don't have to.

The only problem is if you have too many points and your common denominator overflows.
0

## Featured Post

### Suggested Solutions

How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I gu…
This is a research brief on the potential colonization of humans on Mars.
This video is in connection to the article "The case of a missing mobile phone (https://www.experts-exchange.com/articles/28474/The-Case-of-a-Missing-Mobile-Phone.html)". It will help one to understand clearly the steps to track a lost android phone.
In this sixth video of the Xpdf series, we discuss and demonstrate the PDFtoPNG utility, which converts a multi-page PDF file to separate color, grayscale, or monochrome PNG files, creating one PNG file for each page in the PDF. It does this via a c…