Velocity Reviews > How to use qsort function of C library ?

# How to use qsort function of C library ?

Guest
Posts: n/a

 04-09-2008
pereges wrote:
> On Apr 9, 9:53 am, Richard Heathfield <(E-Mail Removed)> wrote:
>
>> Well, actually you can, provided that you can define an ordering
>> relationship between two vertices. For example, let us say that we want to
>> order by x first, by y if x1==x2, and by z if x1==x2 and y1==y2. We do it
>> like this:

>
> What is this ordering relationship ? Why should we sort along y if x1
> == x2 or z if x1 == x2 and
> y1 ==y2 ?

The ordering Richard specified was an example of what could be done. The
point is that you can define whatever ordering you want to use for sorting.

--

pereges
Guest
Posts: n/a

 04-09-2008
What I am actually doing is for my kdtree program. I have an object
which I want to divide spatially using kdtrees. There is bounding box
for an entire object. I also built a bounding sphere for every
triangle and then based on the centers of these bounding spheres, I
will calculate a median. At this point the box must be split into left
and right child boxes. Now, the splitting axis which is used to
subdivide a bounding box will depend on depth.
axis = depth % 3

suppose axis ==0 then the box will be split along x axis and the
median center is taken as the split point. If axis == 1 then split
along y axis, if axis == 2 then split along z axis. To cacluate
median, I need to sort the list of bounding spheres within a
particular kd tree node/box. I will sort this list (along x, y ,
z)depending upon value of axis.

In the below a triangle is

typedef struct triangle_struct
{
int v0, v1, v2; /* 3 indices into vertex list that identify a
triangle */
}triangle;

typedef vector vertex; /* vertex is a vector of doubles */

Object is

typedef struct object_struct
{
int ntri, nvert; /* number of triangles and no of vertices
respectively */
triangle *tri; /* list of triangles */
vertex *vert; /* vertex list */
} object;

kdtree.h
----------------------------------------

#ifndef kd_tree
#define kd_tree

#include "common.h"

typedef struct bounding_sphere_struct
{
vector cen; /*center of bounding sphere */
int tid; /* id of triangle inside this sphere */
triangle tr; /* triangle in this sphere */

}bsphere;

typedef struct kdnode_struct
{
vector maxB, minB; /* maximum bound of the kdnode/box , minimum bound
*/
vector split; /* point along which this box will be split */
struct kdnode_struct *left, *right; /* left child right child */
bsphere* bhead; /* list of bounding spheres inside this box */
int maxspheres; /* Maximum number of spheres in this box */

}kdnode;

int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector
c);
kdnode* init_kdtree(object *, kdnode *);
void build_kdtree(kdnode *kd, int depth);
#endif

kdtree.c
--------------------------------------------

#include "kdtree.h"

int axis = 0;

/* this function runs correctly, as i have checked it */
int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector c)
{
double dotABAB, dotABAC, dotACAC, d,s ,t ;
vector tp, temp1, temp2;

vector_sub(&b, &a, &temp1);
dotABAB = vector_dot( &temp1, &temp1);
vector_sub(&c, &a, &temp2);
dotABAC = vector_dot(&temp1, &temp2);
dotACAC = vector_dot(&temp2, &temp2);
d = 2.0 *(dotABAB*dotACAC - dotABAC*dotABAC);

if (fabs(d) <= 0)
return FAILURE;
s = (dotABAB*dotACAC - dotACAC*dotABAC) / d;
t = (dotACAC*dotABAB - dotABAB*dotABAC) / d;
tp = c;
/* s controls height over AC, t over AB, (1-s-t) over BC */
if (s <= 0.0)
{
bs->cen.x = 0.5*(a.x + c.x);
bs->cen.y = 0.5* (a.y + c.y);
bs->cen.z = 0.5* (a.z + c.z);
}
else
if (t <= 0.0)
{
bs->cen.x = 0.5 *(a.x + b.x);
bs->cen.y = 0.5 * (a.y + b.y);
bs->cen.z = 0.5* (a.z + b.z);
}
else
if (s + t >= 1.0)
{
bs->cen.x = 0.5*(b.x + c.x);
bs->cen.y = 0.5 * (b.y + c.y);
bs->cen.z = 0.5*(b.z + c.z);

}
else
{
bs->cen.x = a.x + s*(b.x - a.x) + t*(c.x - a.x);
bs->cen.y = a.y + s*(b.y - a.y)+ t*(c.y - a.y);
bs->cen.z = a.z + s* (b.z - a.z)+t*(c.z - a.z);
}
vector_sub(&(bs->cen), &tp, &temp1);
bs->r = sqrt( vector_dot(&temp1, &temp1));
return SUCCESS;
}

/* this is incomplete */
void sort_x(kdnode *kd)
{
int i, j;
for(i=0; i < kd->maxspheres; i++)
for(j=0; j<

}

/* this is incomplete */
void sort_y(kdnode *kd)
{

}

/* this is incomplete */

void sort_z(kdnode *kd)
{

}

/* this is incomplete as well but i will make it a recursive function
probably
void build_kdtree(kdnode *kd, int depth)
{
int median;
if(kd->maxspheres <= MINSPHERES || depth < DEPTHLIMIT)
{
kd->left = kd->right = NULL;
return;
}

else
{

if(axis == 0) /* sort kdnode->bhead along x axis, find the
median and use it to split */
{
}

if(axis == 1)/* sort kdnode->bhead along x axis, find the
median and use it to split */
{
}

if(axis == 2)/* sort kdnode->bhead along x axis, find the
median and use it to split */
{

}

build_kdtree(kdnode->left, depth+1);
build_kdtree(kdnode->right, depth+1);

}

/* Initializes the root node of the kdtree */
kdnode* init_kdtree(object *o, kdnode *kdroot)
{
int i,flag;
flag = FAILURE;
kdroot = malloc(sizeof(kdnode));
kdroot->left = kdroot->right = NULL;
kdroot->maxB.x = kdroot->maxB.y = kdroot->maxB.z = -DBL_MAX;
kdroot->minB.x = kdroot->minB.y = kdroot->minB.z = DBL_MAX;
for(i = 0; i<o->nvert; i++)
{
if(o->vert[i].x <kdroot-> minB.x)
kdroot->minB.x = o->vert[i].x;
if(o->vert[i].x > kdroot->maxB.x)
kdroot->maxB.x = o->vert[i].x;
if(o->vert[i].y < kdroot->minB.y)
kdroot->minB.y = o->vert[i].y;
if(o->vert[i].y > kdroot->maxB.y)
kdroot->maxB.y = o->vert[i].y;
if(o->vert[i].z < kdroot->minB.z)
kdroot->minB.z = o->vert[i].z;
if(o->vert[i].z > kdroot->maxB.z)
kdroot->maxB.z = o->vert[i].z;
}

/*printf("MAXB: %f %f %f MINB: %f %f %f \n", kdroot-
>maxB.x, kdroot->maxB.y, kdroot->maxB.z, kdroot->minB.x, kdroot-
>minB.y, kdroot->minB.z); */

kdroot->maxspheres = o->ntri;
for(i=0; i<o->ntri; i++)
{
>vert[o->tri[i].v0], o->vert[o->tri[i].v1], o->vert[o->tri[i].v2]);

if(flag == FAILURE)
{
printf("Error in calculation of bounding spheres\n");
exit(FAILURE);
}
/*printf("Flag:%d Center:%f %f %f radius: %f\n",flag, kdroot-

}
build_kdtree(kdroot, 0);
return kdroot;

}

pereges
Guest
Posts: n/a

 04-09-2008
What I am actually doing is for my kdtree program. I have an object
which I want to divide spatially using kdtrees. There is bounding box
for an entire object. I also built a bounding sphere for every
triangle and then based on the centers of these bounding spheres, I
will calculate a median. At this point the box must be split into left
and right child boxes. Now, the splitting axis which is used to
subdivide a bounding box will depend on depth.
axis = depth % 3

suppose axis ==0 then the box will be split along x axis and the
median center is taken as the split point. If axis == 1 then split
along y axis, if axis == 2 then split along z axis. To cacluate
median, I need to sort the list of bounding spheres within a
particular kd tree node/box. I will sort this list (along x, y ,
z)depending upon value of axis.

My code -

In the below a triangle is

typedef struct triangle_struct
{
int v0, v1, v2; /* 3 indices into vertex list that identify a
triangle */

}triangle;

typedef vector vertex; /* vertex is a vector of doubles */

Object is

typedef struct object_struct
{
int ntri, nvert; /* number of triangles and no of vertices
respectively */
triangle *tri; /* list of triangles */
vertex *vert; /* vertex list */

} object;

kdtree.h
----------------------------------------

#ifndef kd_tree
#define kd_tree

#include "common.h"

typedef struct bounding_sphere_struct
{
vector cen; /*center of bounding sphere */
int tid; /* id of triangle inside this sphere */
triangle tr; /* triangle in this sphere */

}bsphere;

typedef struct kdnode_struct
{
vector maxB, minB; /* maximum bound of the kdnode/box ,
minimum bound*/
vector split; /* point along which this box will be split */
struct kdnode_struct *left, *right; /* left child right child
*/
bsphere* bhead; /* list of bounding spheres inside this box */
int maxspheres; /* Maximum number of spheres in this box */

}kdnode;

int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector
c);
kdnode* init_kdtree(object *, kdnode *);
void build_kdtree(kdnode *kd, int depth);

#endif

kdtree.c
--------------------------------------------

#include "kdtree.h"

int axis = 0;

/* this function runs correctly, as i have checked it */
int compute_bounding_sphere(bsphere *bs, vector a, vector b, vector c)
{
double dotABAB, dotABAC, dotACAC, d,s ,t ;
vector tp, temp1, temp2;

vector_sub(&b, &a, &temp1);
dotABAB = vector_dot( &temp1, &temp1);
vector_sub(&c, &a, &temp2);
dotABAC = vector_dot(&temp1, &temp2);
dotACAC = vector_dot(&temp2, &temp2);
d = 2.0 *(dotABAB*dotACAC - dotABAC*dotABAC);

if(fabs(d) <= 0)
return FAILURE;
s = (dotABAB*dotACAC - dotACAC*dotABAC) / d;
t = (dotACAC*dotABAB - dotABAB*dotABAC) / d;
tp = c;
/* s controls height over AC, t over AB, (1-s-t) over BC */
if (s <= 0.0)
{
bs->cen.x = 0.5*(a.x + c.x);
bs->cen.y = 0.5* (a.y + c.y);
bs->cen.z = 0.5* (a.z + c.z);
}
else
if (t <= 0.0)
{
bs->cen.x = 0.5 *(a.x + b.x);
bs->cen.y = 0.5 * (a.y + b.y);
bs->cen.z = 0.5* (a.z + b.z);
}
else
if (s + t >= 1.0)
{
bs->cen.x = 0.5*(b.x + c.x);
bs->cen.y = 0.5 * (b.y + c.y);
bs->cen.z = 0.5*(b.z + c.z);

}
else
{
bs->cen.x = a.x + s*(b.x - a.x) + t*(c.x - a.x);
bs->cen.y = a.y + s*(b.y - a.y)+ t*(c.y - a.y);
bs->cen.z = a.z + s* (b.z - a.z)+t*(c.z - a.z);
}
vector_sub(&(bs->cen), &tp, &temp1);
bs->r = sqrt( vector_dot(&temp1, &temp1));
return SUCCESS;
}

/* this is incomplete */
void sort_x(kdnode *kd)
{

}

/* this is incomplete */
void sort_y(kdnode *kd)
{

}

/* this is incomplete */

void sort_z(kdnode *kd)
{

}

/* this is incomplete as well but i will make it a recursive function
probably
void build_kdtree(kdnode *kd, int depth)
{
int median;
if(kd->maxspheres <= MINSPHERES || depth < DEPTHLIMIT)
{
kd->left = kd->right = NULL;
return;
}

else
{

if(axis == 0) /* sort kdnode->bhead along x axis, find the
median and use it to split */
{

}

if(axis == 1)/* sort kdnode->bhead along x axis, find the
median and use it to split */
{

}

if(axis == 2)/* sort kdnode->bhead along x axis, find the
median and use it to split */
{

}

build_kdtree(kdnode->left, depth+1);
build_kdtree(kdnode->right, depth+1);

}

/* Initializes the root node of the kdtree */
kdnode* init_kdtree(object *o, kdnode *kdroot)
{
int i,flag;
flag = FAILURE;
kdroot = malloc(sizeof(kdnode));
kdroot->left = kdroot->right = NULL;
kdroot->maxB.x = kdroot->maxB.y = kdroot->maxB.z = -DBL_MAX;
kdroot->minB.x = kdroot->minB.y = kdroot->minB.z = DBL_MAX;
for(i = 0; i<o->nvert; i++)
{
if(o->vert[i].x <kdroot-> minB.x)
kdroot->minB.x = o->vert[i].x;
if(o->vert[i].x > kdroot->maxB.x)
kdroot->maxB.x = o->vert[i].x;
if(o->vert[i].y < kdroot->minB.y)
kdroot->minB.y = o->vert[i].y;
if(o->vert[i].y > kdroot->maxB.y)
kdroot->maxB.y = o->vert[i].y;
if(o->vert[i].z < kdroot->minB.z)
kdroot->minB.z = o->vert[i].z;
if(o->vert[i].z > kdroot->maxB.z)
kdroot->maxB.z = o->vert[i].z;
}

/*printf("MAXB: %f %f %f MINB: %f %f %f \n", kdroot-
>maxB.x, kdroot->maxB.y, kdroot->maxB.z, kdroot->minB.x, kdroot-
>minB.y, kdroot->minB.z); */

kdroot->maxspheres = o->ntri;
for(i=0; i<o->ntri; i++)
{
>vert[o->tri[i].v0], o->vert[o->tri[i].v1], o->vert[o->tri[i].v2]);

if(flag == FAILURE)
{
printf("Error in calculation of bounding
spheres\n");
exit(FAILURE);
}
/*printf("Flag:%d Center:%f %f %f radius: %f\n",flag,

}

build_kdtree(kdroot, 0);
return kdroot;

}

pereges
Guest
Posts: n/a

 04-09-2008
This is too complicated. I have to sort the array of structures given
by kd->bhead pointer according to the x coordinate of center. kd-
>bhead[i].cen.x. I wonder if something like below would work -

void cmpcenter_x(const void *cpa, const void *cpb)
{
const bsphere *ca = cpa;
const bsphere *cb = cpb;

return(ca->cen.x - cb.cen.x);
}

...................
...................

Walter Roberson
Guest
Posts: n/a

 04-09-2008
In article <(E-Mail Removed)>,
pereges <(E-Mail Removed)> wrote:
>This is too complicated. I have to sort the array of structures given
>by kd->bhead pointer according to the x coordinate of center. kd-
>>bhead[i].cen.x. I wonder if something like below would work -

>void cmpcenter_x(const void *cpa, const void *cpb)
>{
> const bsphere *ca = cpa;
> const bsphere *cb = cpb;
>
> return(ca->cen.x - cb.cen.x);
> }

You probably meant cb->cen.x

You don't -need- to assign the pointers. It might not make any
difference with a good optimizer, but it might:

return ((const bsphere *)ca)->cen.x - ((const bsphere *)cb)->cen.x;

--
"They called it golf because all the other four letter words
were taken." -- Walter Hagen

Keith Thompson
Guest
Posts: n/a

 04-09-2008
pereges <(E-Mail Removed)> writes:
> This is too complicated. I have to sort the array of structures given
> by kd->bhead pointer according to the x coordinate of center. kd-
>>bhead[i].cen.x. I wonder if something like below would work -

>
> void cmpcenter_x(const void *cpa, const void *cpb)
> {
> const bsphere *ca = cpa;
> const bsphere *cb = cpb;
>
> return(ca->cen.x - cb.cen.x);
> }
>
> ..................
> ..................
>

Using a subtraction like that:

return ca->cen.x - cb->cen.x;

is a cute trick, but you should avoid it unless you're *certain* that
it can't overflow (or wrap around if x is unsigned).

A more straightforward test is:

if (ca->cen.x < cb->cen.x) {
return -1;
}
else if (ca->cen.x > cb->cen.x) {
return 1;
}
else {
return 0;
}

Or, if you like terseness:

return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;

(This takes advantage of the fact that ">" yields 0 or 1.)

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

pereges
Guest
Posts: n/a

 04-09-2008
On Apr 9, 12:59 pm, Keith Thompson <(E-Mail Removed)> wrote:
> Using a subtraction like that:
>
> return ca->cen.x - cb->cen.x;
>
> is a cute trick, but you should avoid it unless you're *certain* that
> it can't overflow (or wrap around if x is unsigned).
>
> A more straightforward test is:
>
> if (ca->cen.x < cb->cen.x) {
> return -1;
> }
> else if (ca->cen.x > cb->cen.x) {
> return 1;
> }
> else {
> return 0;
> }
>
> Or, if you like terseness:
>
> return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;
>
> (This takes advantage of the fact that ">" yields 0 or 1.)
>

I don't think it will work with kdnode->bhead[i].cen.x

You are trying to sort an array bhead[0..maxspheres] according to x of
center element. Probably, qsort will not give results with comparison
functions like the one above.

Barry Schwarz
Guest
Posts: n/a

 04-09-2008
On Wed, 9 Apr 2008 01:39:55 -0700 (PDT), pereges <(E-Mail Removed)>
wrote:

>On Apr 9, 12:59 pm, Keith Thompson <(E-Mail Removed)> wrote:
>> Using a subtraction like that:
>>
>> return ca->cen.x - cb->cen.x;
>>
>> is a cute trick, but you should avoid it unless you're *certain* that
>> it can't overflow (or wrap around if x is unsigned).
>>
>> A more straightforward test is:
>>
>> if (ca->cen.x < cb->cen.x) {
>> return -1;
>> }
>> else if (ca->cen.x > cb->cen.x) {
>> return 1;
>> }
>> else {
>> return 0;
>> }
>>
>> Or, if you like terseness:
>>
>> return ca->cen.x < cb->cen.x ? -1 : ca->cen.x > cb->cen.x;
>>
>> (This takes advantage of the fact that ">" yields 0 or 1.)
>>

>
>I don't think it will work with kdnode->bhead[i].cen.x
>
>You are trying to sort an array bhead[0..maxspheres] according to x of
>center element. Probably, qsort will not give results with comparison
>functions like the one above.
>

YOU need to examine the code. By the time your comparison function
gets called, you only have two elements to compare and it doesn't
matter how qsort decided which two.

You originally started with
return(ca->cen.x - cb.cen.x);
Assuming integer values, this will return a negative value when the
first term is less than the second, a positive value when the first is
greater, and zero when both are the same.

Both Keith's and Richard's suggestions do the SAME but eliminate the
floating point values that differ by less than one due to truncation
when the floating point result is converted to an integer as the
return type. Since you are talking about coordinates, this may be
significant.

Remove del for email