PDA

View Full Version : sort on x and y of 2d points



giuseppe500
12-10-2012, 03:38 AM
hello.
I would use a sort algorithm that works with multiple indices.
For example i would sort based on cx and cy a set of 2d point.
I think to x and y combined in a color and i wish extract the groups of 2d points that have a similar color.
Is the same thing as an ordering based on x and y?
thanks.

The Little Body
12-11-2012, 01:30 PM
No, this isn't the same thing

With x and y combined in a color and the extraction of 2D points that have a similar color, you only have the set of 2d points that are relatively near from the correspondant (x,y) point [combined to a color] that you have assigned to each group

What do you want exactly, really sort the (x,y) positions or only regroup nears (x,y) positions into groups ?

If this is only for to regroup nears positions, this can work
(but with a limited precision if you don't use float colors color because the Red ,Green ,Blue and Alpha components are only stored in bytes in the standard RGBA32 format)

For the other case [cf. a true sort of (x,y positions)] , the qsort() standard C function is relatively speed, but the computation is entirely make on the CPU



#include <stdio.h>
#include <stdlib.h>

typedef struct
{
float x;
float y;

} position_t;

#define NUM_POSITIONS 10
position_t positions[NUM_POSITIONS];

int sort_xy(void const *a, void const *b)
{
position_t *pa, *pb;

pa = (position_t *) a;
pb = (position_t *) b;

if( pa->x < pb->x) return -1;
if( pa->x > pb->x) return 1;

if( pa->y < pb->y) return -1;
if( pa->y > pb->y) return 1;

return 0;
}

int main( int argc, char **argv)
{
int i;

printf("\nInitials positions : \n");
for( i = 0 ; i < NUM_POSITIONS ; i++)
{
positions[i].x = (int)(random()) % 5;
positions[i].y = (int)(rand()) % 5;
printf(" x=%f y=%f \n", positions[i].x, positions[i].y );
}


qsort(positions, NUM_POSITIONS, sizeof(position_t), sort_xy);


printf("\n\nSorted positions : \n");
for( i = 0 ; i < NUM_POSITIONS ; i++)
{
printf(" x=%f y=%f \n", positions[i].x, positions[i].y);
}

return 0;
}


That give


Initials positions :
x=3.000000 y=1.000000
x=2.000000 y=0.000000
x=3.000000 y=0.000000
x=1.000000 y=2.000000
x=4.000000 y=1.000000
x=2.000000 y=2.000000
x=0.000000 y=4.000000
x=3.000000 y=1.000000
x=0.000000 y=1.000000
x=2.000000 y=1.000000


Sorted positions :
x=0.000000 y=1.000000
x=0.000000 y=4.000000
x=1.000000 y=2.000000
x=2.000000 y=0.000000
x=2.000000 y=1.000000
x=2.000000 y=2.000000
x=3.000000 y=0.000000
x=3.000000 y=1.000000
x=3.000000 y=1.000000
x=4.000000 y=1.000000

(this is sorted first by x coordinates and on second key [cf. when x coordinates are identics] by the y coordinate)