Ordering coordinates problem

Question

Have been scatching my head about this - and I reckon it's simple but my geometry/algebra is pretty rubbish, and I can't remember how to do this stuff from my school days!

EDITED: I have a list of coordinates with people stood by them - I need an algorithm to order people from top left to bottom right in a list (array), and the second criteria demands that coordinates that are closer towards the top left origin take prescendance over all others - how would you do this?

The code should show the order as:

1. Tom
2. Harry
3. Bob
4. Dave

See diagram below:

Answer 1

From your ordering, it looks like you are putting y position at a higher priority than x position, so something like this would work when comparing two people:

if (a.y > b.y)
// a is before b
else if (a.x < b.x)
// a is before b
else
// b is before a

edit for update This comparison still works with your new criteria. Y position is still has precedence over the X position. If the Y values are equal, the point closest to the top left corner would be the one with the smaller X value. If you want to make your object a comparator, implementing this as your comparator function would allow you to do ArrayList.sort() where negative means the first person is before the second:

public int compareTo(person a, person b) {
    if (a.y == b.y)
       return a.x-b.x
    else
       return b.y-a.y
}

//compareTo(Tom, Harry) == -50 (tom is before harry)
//compareTo(Tom, Bob) == -25 (tom is before bob)
//compareTo(Dave, Bob) == 30 (dave is after bob)

Answer 2

Order them based on their distance from the top-left corner of your 2D-Space, in this case (0, 100).

EDIT:

Obviously this will mean that you will have cases where 2 people are equidistant from the top left corner, and yet they are nowhere near each other.

In this case, you need to specify how you want such people to be ordered. If you want to pick people who are higher up, you can order by y-coord first. Similarly you can choose some other criterion.

All other sorting algorithms will have the same problem, of what to do when 2 items have the same sort key. By definition then, they are considered identical until you come up with a secondary sorting criterion.

Answer 3

I'd say:

orderValue = x+(100-y)

Then sort based on the smallest orderValue being the "closest" (according to distance projected on to the line y=100-x) to the top-left.

Answer 4

If you know max order of magnitude of X, sort by (for your given example) 100 * (100 - Y) + X.

Answer 5

The comparator looks like this:

int d = o2.y - o1.y;
if (d == 0)
    d = o1.x - o2.x;
return d;

This will first sort by Y, then by X (for all objects which have the same Y).

[EDIT] Fixed Y sort order.

Answer 6

May be you could look into the Haversine formula which is used in navigation to calculate proximity from two points. However, that mostly applies to points on a sphere. http://en.wikipedia.org/wiki/Haversine_formula