AlexFM
asked on
Sorting points by polar angle
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.
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.
d-glitch
If you are willing to presort them into quadrant groups, you can sort each group with just a division.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
(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
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.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks, I understand both ideas. I will keep this question opened for some time hoping that somebody has pure integer solution.
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
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
ASKER
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?
{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?
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.
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.
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
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
ASKER
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.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
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.
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.
...ps. Thanks for the points. :-)
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.
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.