34 void Swap(t_point point,
int i,
int j)
40 SWAP(ltemp, point[i].vnum, point[j].vnum);
41 SWAP(ftemp, point[i].v[X], point[j].v[X]);
42 SWAP(ftemp, point[i].v[Y], point[j].v[Y]);
43 SWAP(btemp, point[i].del, point[j].del);
46 void Copy(t_point point,
int i,
int j)
48 point[j].v[X] = point[i].v[X];
49 point[j].v[Y] = point[i].v[Y];
50 point[j].vnum = point[i].vnum;
51 point[j].del = point[i].del;
54 void Delete(t_point point,
int i)
67 int Compare(
const void *tpi,
const void *tpj)
76 a = AreaSign(pi->p0, pi->v, pj->v);
82 x = abs( pi->v[X] - pi->p0[X] ) - abs( pj->v[X] - pi->p0[X] );
83 y = abs( pi->v[Y] - pi->p0[Y] ) - abs( pj->v[Y] - pi->p0[Y] );
87 if ((x < 0) || (y < 0)) {
91 else if ((x > 0) || (y > 0)) {
96 if (pi->vnum > pj->vnum)
108 t_stack Graham(t_H2D h2)
116 top = Push (&h2.point[0], top);
117 top = Push (&h2.point[1], top);
122 while (i < h2.nb_point) {
129 if (Left(p1->v , p2->v, h2.point[i].v)) {
130 top = Push(&h2.point[i], top);
133 else top = Pop( top );
142 t_stack Pop(t_stack s)
155 t_stack Push(t_point p, t_stack top)
173 return AreaSign( a, b, c ) > 0;
180 area2 = ( b[0] - a[0] ) * ( c[1] - a[1] ) -
181 ( c[0] - a[0] ) * ( b[1] - a[1] );
187 if (area2 > 0)
return 1;
188 else if (area2 < 0)
return -1;
double t_xy[2]
Data structures to store a 2 dimensional convex hull.
Compute convex hulls in 2 dimensions.
#define NEW(p, type)
Macros.