sorting of 2d coordinates

[Oldchatterman]

Hello,

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!

Mark

 

[Attila Feher]

Hello,

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!

Pseudo code:

somefunc() {
struct point {
integer x,y;
};

std::vector<point> pattern;

while (there are points) {
pattern.push_back(read_a_point());
}

std::sort( pattern.begin(), pattern.end(), pointbyxtheny);

// Pattern is what you wanted (as far as I understand)

}

result pointbyxtheny( point p1, point p2) {
if x1<x2 return p1_is_smaller;
if x2<x1 return p2_is_smaller;
// x-es are equal
if y1<y2 return p1_is_smaller;
return p2_is_smaller;
}

Something along this lines. They might be full of errors and I have left
out the step 1. If you need the data from step 1 you will need to use
stable_sort to make it.

Without a good C++ introductory book such as Accelerated C++ (where a very
similar issue is solved) you won't get far. Unless someone else takes the
bait and works instead of you. I really suggest reading that book: IMHO it
contains all you need to know to make this work.

 

[Oldchatterman]

The std::sort algorithm takes a sorting "functor" as one of its
parameters. Just provide one functor for ordering of the elements
in the way you see fit:

struct Point
{
int x;
int y;
};

struct Ordering_Functor
{
bool operator()(const Point& a, const Point& b)
{
if (a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
};

vector<Point> points;

// Sort the points
std::sort(points.begin(), points.end(), Ordering_Functor());

Thank you Thomas, this is exactly what I needed. I already managed to
make it work in my application!

Mark Hermans