Большие проблемы сортировки набора данных - PullRequest
Новая
       5

Большие проблемы сортировки набора данных

0 голосов
/ 26 апреля 2011

У меня есть двумерный массив, представляющий координаты x и y сетки точек, составляющих прямоугольник.Используемые наборы данных обычно очень большие.Я хочу отсортировать точки, начиная с верхнего левого угла и двигаясь параллельно диагональным линиям до нижнего правого угла.Для этого я использую функцию Arrays.sort и следующий компаратор: 

public int compare(Object o1, Object o2) {
  double[] a1 = (double[])o1;
  double[] a2 = (double[])o2;

  if (a1[0]+a1[1] > a2[0]+a2[1]) return 1;
  else if (a1[0]+a1[1] < a2[0]+a2[1]) return -1;
  else {
    if (a1[0] > a2[0]) return 1;    
    else if (a1[0] < a2[0]) return -1;
    else return 0;
  }  
}

Код работает по какой-то причине, когда координаты x и y каждой точки разнесены на две цифры, но естьошибки в сортировке, если они разнесены только на одну цифру.

Пример оригинального порядка можно найти здесь: http://www.mediafire.com/?slq73v3zn2zs98l

И пример того, что результирующий отсортированный списоквнешний вид можно найти здесь: http://www.mediafire.com/?x8f08q0qoof398w

Почему сортировка не работает?Любая помощь будет очень признательна!

1 Ответ

0 голосов
/ 26 апреля 2011

Глядя на картинку, с которой вы связались, я думаю, что вы хотите сделать Double.compare() на расстоянии L1 точки от верхнего левого угла.

Это означает, что для заданных 2d точек a и b и «начала координат» Origin (в данном случае верхней левой точки) вы хотите сравнить: 

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
return Double.compare(distance_a,distance_b);

и сортируйте, сравнивая эти расстояния. Вы могли бы обернуть это в разумный компаратор, который использует Double.compare().

Обновление: теперь я понимаю дополнительные критерии сортировки после вашего последнего комментария. Возможно, вы захотите учесть точность проблем при сравнении двойных значений (кто-то другой сможет посоветовать вам лучше), однако вам нужно что-то вроде: 

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
if distance_a is not equal to distance_b // check how you should perform the comparison
    return Double.compare(distance_a,distance_b);
else
    return Double.compare(a.x,b.x);
...