Проблема порядка координат

Question

Я ломал голову над этим - и я считаю, что это просто, но моя геометрия / алгебра довольно мусор, и я не могу вспомнить, как это делать со школьных лет!

Редакция: У меня есть список координат с людьми, стоящими рядом с ними - мне нужен алгоритм, чтобы упорядочить людей сверху слева направо в списке (массиве), и второй критерий требует, чтобы координаты, которые ближе к верхнему левому началу координат, имели приоритет над все остальные - как бы вы это сделали?

Код должен отображать заказ как:

1. Том
2. Harry
3. Bob
4. Dave

См. Схему ниже:

Answer 1

Из вашего заказа похоже, что вы ставите позицию y с более высоким приоритетом, чем позиция x, поэтому что-то подобное будет работать при сравнении двух людей:

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

редактировать для обновления Это сравнение по-прежнему работает с вашими новыми критериями. Позиция Y по-прежнему имеет приоритет над позицией X. Если значения Y равны, точка, ближайшая к верхнему левому углу, будет иметь точку с меньшим значением X. Если вы хотите сделать ваш объект компаратором, реализация этого как функции компаратора позволит вам выполнить ArrayList.sort (), где отрицательный означает, что первый человек находится перед вторым:

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

Заказывайте их, основываясь на расстоянии от верхнего левого угла вашего 2D-пространства, в данном случае (0, 100).

EDIT:

Очевидно, это будет означать, что у вас будут случаи, когда 2 человека находятся на равном расстоянии от верхнего левого угла, и все же они нигде не находятся рядом.

В этом случае вам нужно указать, как вы хотите, чтобы такие люди были заказаны. Если вы хотите выбрать людей, которые выше, вы можете сначала заказать по y-координатам. Точно так же вы можете выбрать другой критерий.

У всех других алгоритмов сортировки будет та же проблема, что и делать, когда 2 элемента имеют одинаковый ключ сортировки. Таким образом, по определению они считаются идентичными до тех пор, пока вы не примете вторичный критерий сортировки.

Answer 3

Я бы сказал:

orderValue = x+(100-y)

Затем выполните сортировку по наименьшему значению orderValue, являющемуся "ближайшим" (в соответствии с расстоянием, спроецированным на линию y = 100-x) до верхнего левого угла.

Answer 4

Если вы знаете максимальный порядок величины X, сортируйте по (для вашего данного примера) 100 * (100 - Y) + X.

Answer 5

Может быть, вы посмотрите на формулу Хаверсайна, которая используется в навигации для вычисления близости из двух точек. Однако это в основном относится к точкам на сфере. http://en.wikipedia.org/wiki/Haversine_formula

Answer 6

Компаратор выглядит так:

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

Сначала будет выполнена сортировка по Y, затем по X (для всех объектов, имеющих одинаковый Y).

[РЕДАКТИРОВАТЬ] Исправлен порядок сортировки Y.