Extendending from the previous post what would a quick sort of vertex3D look like ..
Code:/*-COORD_TYPE---------------------------------------------------------------- Units your 3d vertex points are in typically shorts, ints, or doubles. ---------------------------------------------------------------------------*/ typedef double COORD_TYPE; // For our example we are using doubles /*-VERTEX3D------------------------------------------------------------------ 3D vertix record structure defined ---------------------------------------------------------------------------*/ typedef struct Vertex3D { COORD_TYPE x; // Vertex x co-ord COORD_TYPE y; // Vertex y co-ord COORD_TYPE z; // Vertex z co-ord } VERTEX3D, *PVERTEX3D; /*-Vswap3D--------------------------------------------------------------------- Swaps the two given 3D vertexes around v1 and v2 ----------------------------------------------------------------------------*/ static void Vswap3D (PVERTEX3D* v1, PVERTEX3D *v2){ PVERTEX3D Temp; Temp = *v1; // Hold current v1 vertex *v1 = *v2; // Transfer v2 to v1 *v2 = Temp; // Set v2 to the held old v1 value }; /*-partition3D_with_random------------------------------------------------------ Partitions the 3D vertex array with randomness ----------------------------------------------------------------------------*/ static short partition3D_with_random(PVERTEX3D list[], short l, short h){ short i; short p; /* pivot element index */ short firsthigh; /* divider position for pivot element */ p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point Vswap3D(&list[p], &list[h]); // Swap the values firsthigh = l; // Hold first high value for (i = l; i < h; i++) // This is what we are sorting based on // .. the following line we are sorting based on vertex x value if(list[i]->x < list[h]->x) { // Value at i is less than h Vswap3D(&list[i], &list[firsthigh]); // So swap the value firsthigh++; // Incement first high } Vswap3D(&list[h], &list[firsthigh]); // Swap h and first high values return(firsthigh); // Return first high } /*-quicksort3D_random--------------------------------------------------------- Quick sort 3D veretex with random partition ----------------------------------------------------------------------------*/ static void quicksort3D_random(PVERTEX3D list[], short l, short h){ short p; /* index of partition */ if ((h - l) > 0) { p = partition3D_with_random(list, l, h); // Partition list quicksort3D_random(list, l, p - 1); // Sort lower partion quicksort3D_random(list, p + 1, h); // Sort upper partition }; };
The code itself is remarkable simple it partitions a list and sorts by calling iteself over and over.
The key two the code is we have a swap routine that swaps two vertex points.
The key to what we are sorting is given by the one line
// This is what we are sorting based on
// .. the following line we are sorting based on vertex x value
if(list[i]->x < list[h]->x)
As you can see the simple test above is based on just the x value of two vertexes so the sort will be done so the vertexes in the array will come out smallest x to largest x
You could have sorted on a euclidean distance for example based on some distance from point (P)
What we will get is a sort of the array of vertexes based upon that which is closest to point PCode:/*-Distance3D---------------------------------------------------------------- Return euclidian distance between the two vertex3D points -------------------------------------------------------------------------------*/ double Distance3D(PVERTEX3D v1, PVERTEX3D v2){ double dx, dy, dz; dx = v2->x - v1->x; // Diff x dy = v2->y - v1->y; // Diff y dz = v2->z - v1->z; // Diff z if ((dx == 0.0) && (dy == 0.0) && (dz==0.0)) // If diff's are zero return (0.0); // Distance is zero return (sqrt(dx*dx + dy*dy + dz*dz)); // Calculate the 3D distance }; // Now if we change the sort equality test to if( Distance3D(list[i], P) < Distance3D(list[h], P))
Is that the sort of thing you are looking for?
Reply With Quote
