Sorting C ++ coordinate points

Question

in the application I measure a lot of 2d-coordinates (x, y) pattern. This pattern consists of a set of points on a fixed resin grid in the x and y directions. All these coordinates are rated for quality and sorted by this account. I want to sort these coordinates first by x and define groups (areas) of x-coordinates that belong to each other. After this step, I want to sort the different x-areas in y-areas.

After that, I can mark the coordinates with the corresponding template (grid).

Example: measured coordinates (2,1), (2,1), (1,1), (3,2), (3), (2), (3), 3), (3, 1)

after step 1: (2.1), (2.3), (2.1) (3.2), (3.3)), (3.1)

after step 2: (2,1), (2,2), (2,3), (3,1), (3), (3,1), 2), (3, 3)

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

Can someone give me some tips, I'm not an experienced C ++ programmer, but maybe with some tips I can do the job!

Answer 1

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

Answer 2

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

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

For instance:
to: (x, y) = (2,2), (2,3), (1,2), (1,3), (2,1), (1,1), (3,2), (3.3), (3.1)
(2,1), (1,1), (3,1), (2,2), (1,2), (3,2), (2,3)), (1,3), ( 3.3)
(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< , for example:

 #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 do not want the “quality” to be preserved in the structure, you can always call some function to calculate it directly in operator< , for example:

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