Sorting Coordinate Points c++

Question

in an application I measure a lot of 2d coordinates (x,y) of a pattern. This pattern consists of a set of points on grid with fixed pitches in x and y direction. These coordinates all have a score for quality and are sorted on this score. What I want to do is to sort these coordinates first on x and define groups (regions) of x-coordinates that belong together. After this step I want to sort the different x-regions in y-regions.

After this I am able to label the coordinates to the corresponding pattern (grid) label.

Example: Measured coordinates (x,y)= (2,2),(2,3),(1,2),(1,3),(2,1),(1,1),(3,2),(3,3),(3 ,1)

after step 1: (x,y)= (1,2),(1,3),(1,1) (2,2),(2,3),(2,1) (3,2),(3,3),(3,1)

after step 2: (x,y)= (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3 ,3)

Is there a sort routine that already performs this task? The routine should also work if some coordinates of the pattern are not measured.

Can somebody give me some clues, I'm not an experienced c++ programmer, but maybe with some hints I can do the job!

Answer 1

If you know the range of you numbers you could multiply the X by some large number and then add y to that number. Now you can simply just sort that single number or you can use stl library to do it as others have described.

Answer 2

You need a stable sort algorithm (witch does not change order of equal elements). First make sorting by y coordinate and next sort by x to get desired result:

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

For example:
before: (x,y)= (2,2),(2,3),(1,2),(1,3),(2,1),(1,1),(3,2),(3,3),(3,1)
sorted by y: (x,y)= (2,1),(1,1),(3,1),(2,2),(1,2),(3,2),(2,3),(1,3),(3,3)
sorted by x: (x,y)= (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)

Answer 3

You can do this using std::sort and a custom operator<, e.g.:

#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());
}

If you don't want the 'quality' to be stored in the structure you can always call some function to compute it in operator< directly, e.g.:

double quality(const coord& c);

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