[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Sorting points by polar angle

Posted on 2005-04-19
16
Medium Priority
?
4,551 Views
Last Modified: 2012-06-27
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
Comment
Question by:AlexFM
  • 4
  • 4
  • 4
  • +1
16 Comments
 
LVL 27

Expert Comment

by:d-glitch
ID: 13816236
If you are willing to presort them into quadrant groups, you can sort each group with just a division.
0
 
LVL 27

Accepted Solution

by:
d-glitch earned 800 total points
ID: 13816285
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

by:GwynforWeb
ID: 13816286
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 27

Expert Comment

by:d-glitch
ID: 13816351
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

by:GwynforWeb
GwynforWeb earned 600 total points
ID: 13816610
...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

by:AlexFM
ID: 13821773
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

by:Talmash
ID: 13822738
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.

about pure integer solution:
==================

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

by:AlexFM
ID: 13822952
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

by:Talmash
ID: 13823019
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

by:Talmash
ID: 13823060
about y1x2 - x1y2 :

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

by:AlexFM
ID: 13823165
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

by:Talmash
Talmash earned 600 total points
ID: 13823242
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

by:AlexFM
ID: 13824590
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

by:GwynforWeb
ID: 13824840
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

by:GwynforWeb
ID: 13825496
...ps. Thanks for the points. :-)
0
 
LVL 27

Expert Comment

by:d-glitch
ID: 13825855
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

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question