Sorting by angle?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Sorting by angle?

Post by Larry »

Is there an efficienct way to sort radially about a point in general positions without using double? (If all the inputs are integer?)

Can we ignore using arccos( dotproduct )?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

I think that's possible, when coordinates of point, which is centre of sort are integers too. You may use fractions to sort (remember nominator and denominator as two numbers). Of course if I don't make any mistake in this thoughts ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

mafattah
New poster
Posts: 23
Joined: Fri Apr 26, 2002 1:00 am
Location: Cairo, Egypt

Post by mafattah »

Can we ignore using arccos( dotproduct )?
It is not dot product that you should use, but cross product. If you make a cross product of the two vectors coming out of the center point to the two points you are comparing, the sign of the product will do the job, and the value of the product is an integer if the coordinates are integers.


However, there is another point that confuses me. How can you sort elements that have a circular relation?? (i.e. there is no 'smallest' or 'largest' element. However, there is an well-known order any rotations of which will do.)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Nod, of course I know the cross product approach to determine if a point is left of another line, but it's not a true order in the sense that there's no absolute min.. since you can keep going around in a circle.. and really don't want to use an O(n^2) sort, because that kills the point..

ANy other hints/clues?

mafattah
New poster
Posts: 23
Joined: Fri Apr 26, 2002 1:00 am
Location: Cairo, Egypt

Post by mafattah »

There is a solution that I just thought about. Why do not you take an arbitrary point of them, and divide the points into two halves one above and one below the line connecting the point taken and the center point. Now you can order the two parts independently (and they will have no circular relation this time), then concatenate the two sorted parts into the final result.

I just invented this, and I do not know if it will work, but I think it should. Any special cases you can think of?

One other question: Are there other situations when we try to sort a set of objects where there is such a circular relation other than in sorting a set of points? Please tell me if you have any examples.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Translate the entire coordinate system such that the rotation point is now 0,0. Then, you can label each point to be in Quadrants I, II, III, or IV depending on the sign of the x,y values. If the points are in the same quadrant, use some kind of fractional comparator, where the fractions are the dy/dx slopes of the two points with respect to the origin.

Assuming you use LCM to determine which numerator is bigger, this should have a running time of approximately n log n log n using quicksort. You can of course use integer division first to make sure you really need to use any fraction comparisons to drop the runtime further.

This, to the best of my knowledge, avoids any use of doubles.

I'm sure there's can be a more efficient way of doing it though.

Post Reply

Return to “Algorithms”