Sorting Coordinate Points c++
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
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)