Проблема с заказом координат

StackOverflow https://stackoverflow.com/questions/916145

Вопрос

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

ОТРЕДАКТИРОВАНО:У меня есть список координат с людьми, стоящими рядом с ними. Мне нужен алгоритм, который упорядочивает людей сверху слева направо в списке (массиве), а второй критерий требует, чтобы координаты, которые ближе к верхнему левому началу, имели приоритет над все остальные - как бы вы это сделали?

Код должен отображать порядок следующим образом:

  1. Том
  2. Гарри
  3. Боб
  4. Дэйв

См. диаграмму ниже:

alt text

Это было полезно?

Решение

Судя по вашему порядку, похоже, что вы присваиваете позиции 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)

Другие советы

Упорядочите их по расстоянию от верхнего левого угла вашего 2D-пространства, в данном случае (0, 100).

РЕДАКТИРОВАТЬ:

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

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

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

Я бы сказал:

orderValue = x+(100-y)

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

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

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

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

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

[EDIT] Исправлен порядок сортировки Y.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top