Re: sorting by comparing two nodes

> angle the line segment P(0) - P(i) makes with the x-axis. So the angle is dependent
> on the reference point, not the quadrant.

sorry I meant "quadrant" after moving the reference point to the origin.
if your points (after subtracting the reference point coordinates) are
(a,b) and (c,d) are all positive (ie in the first quadrant) you don't
need to compare points pairwise you can just work out the tangent y/x
and sort on that. So that combined with some tests on the sign of the
coordinates is all you need.


> sorry, perhaps I missed your point. My english is not the best.
> What do you mean by transitive? 

P>Q and Q>R implies P>R

> Given a set of points the comparison
> function of course determines just one possible sorting. 

as written I think not, if your points are (1,1) and (-1,-1) then your
formula comes to 0 whichever way you compare the two points, so it is
unspecified which order the points should be in.
So you need to consider each quadrant separately, then as I say above
you can just consider one point at a time, if you know all coordinates
are positive the test p1x*p2y > p2x*p1y is equivalent to the test
p1x/p1y > p2x/p2y so you can sort on x/y for each point separately.

David

________________________________________________________________________
This e-mail has been scanned for all viruses by Star. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________