Сортировка координатных точек с ++ - PullRequest
Новая
       28

Сортировка координатных точек с ++

4 голосов
/ 27 августа 2011

в приложении я измеряю много 2D координат (х, у) шаблон. Этот шаблон состоит из набора точек на сетке с фиксированным качки в направлении х и у. Эти координаты имеют оценку для качество и отсортированы на этот счет. Что я хочу сделать, это отсортировать эти координаты сначала на х и определяют группы (регионы) Х-координаты, которые принадлежат друг другу. После этого шага я хочу отсортировать различные x-области в y-областях.

После этого я могу пометить координаты в соответствующие шаблон (сетка) этикетки.

Пример: измеренные координаты (x, y) = (2,2), (2,3), (1,2), (1,3), (2,1), (1,1), (3,2), (3 , 3), (3, 1)

после шага 1: (x, y) = (1,2), (1,3), (1,1) (2,2), (2,3), (2,1) (3,2), (3,3 ), (3,1)

после шага 2: (x, y) = (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3 , 2), (3, 3)

Есть ли процедура сортировки, которая уже выполняет эту задачу? Рутина также должен работать, если некоторые координаты шаблона не измерены.

Может кто-нибудь подсказать мне, я не опытный с ++ программист, но, может быть, с некоторыми советами я могу сделать работу!

Ответы [ 3 ]

8 голосов
/ 27 августа 2011

Вам нужен стабильный алгоритм сортировки (ведьма не меняет порядок равных элементов). Сначала выполните сортировку по y координатам, а затем сортируйте по x, чтобы получить желаемый результат: 

std::stable_sort(points.begin(), points.end(), yComparator());
std::stable_sort(points.begin(), points.end(), xComparator());

Например:
перед: (х, у) = (2,2), (2,3), (1,2), (1,3), (2,1), (1,1), (3,2), (3,3), (3,1)
отсортировано по y: (x, y) = (2,1), (1,1), (3,1), (2,2), (1,2), (3,2), (2,3 ), (1,3), (3,3)
отсортировано по x: (x, y) = (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1 ), (3,2), (3,3)

5 голосов
/ 27 августа 2011

Вы можете сделать это, используя std::sort и пользовательский operator<, например: 

#include <algorithm>
#include <vector>

struct coord {
  double x,y,quality;
};

bool operator<(const coord& a, const coord& b) {
  return a.quality < b.quality;
}

int main() {
  std::vector<coord> coords;
  std::sort(coords.begin(), coords.end());
}

Если вы не хотите, чтобы «качество» сохранялось в структуре, вы всегда можете вызвать некоторыефункция для вычисления в operator< напрямую, например: 

double quality(const coord& c);

bool operator<(const coord& a, const coord& b) {
  return quality(a) < quality(b);
}
3 голосов
/ 27 августа 2011

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

...