Jamoma API  0.6.0.a19
hull2D.cpp
Go to the documentation of this file.
1 /**
2  @file
3 
4  @ingroup implementationMaxExternals
5 
6  @brief 2D implementation on convex hull.
7 
8  @details This code is described in "Computational Geometry in C" (Second Edition),
9  Chapter 3. It is not written to be comprehensible without the
10  explanation in that book. @n
11  @n
12  Input: 2n integer coordinates of points in the plane. @n
13  Output: the convex hull, cw, in PostScript; other output precedes the PS. @n
14  @n
15  NB: The original array storing the points is overwritten. @n
16 
17  Compile: gcc -o graham graham.c (or simply: make) @n
18 
19  Written by Joseph O'Rourke. @n
20  Last modified: October 1997 @n
21  Questions to orourke@cs.smith.edu. @n
22 
23  @author Joseph O'Rourke
24 
25  @copyright -------------------------------------------------------------------- @n
26  This code is Copyright 1998 by Joseph O'Rourke. It may be freely @n
27  redistributed in its entirety provided that this copyright notice is @n
28  not removed. @n
29  --------------------------------------------------------------------
30 */
31 
32 #include "hull2D.h"
33 
34 void Swap(t_point point,int i, int j)
35 {
36  long ltemp;
37  bool btemp;
38  double ftemp;
39  /* Uses swap macro. */
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);
44 }
45 
46 void Copy(t_point point,int i, int j)
47 {
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;
52 }
53 
54 void Delete(t_point point,int i)
55 {
56  point[i].v[X] = 0.;
57  point[i].v[Y] = 0.;
58  point[i].vnum = -1;
59  point[i].del = true;
60 }
61 
62 /*---------------------------------------------------------------------
63 Compare: returns -1,0,+1 if p1 < p2, =, or > respectively;
64 here "<" means smaller angle. Follows the conventions of qsort_s
65 (with a pointer to contextual hull data).
66 ---------------------------------------------------------------------*/
67 int Compare(const void *tpi, const void *tpj)
68 {
69  int a; // area sign
70  double x, y; // projections of ri & rj in 1st quadrant
71  t_point pi, pj; // data to compare
72 
73  pi = (t_point)tpi;
74  pj = (t_point)tpj;
75 
76  a = AreaSign(pi->p0, pi->v, pj->v);
77  if (a > 0)
78  return -1;
79  else if (a < 0)
80  return 1;
81  else { /* Collinear with P[0] (stored in each pi->p0 because we use qsort instead of qsort_s) */
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] );
84 
85  //h2->nb_delete++; // Now it's done after the sorting
86 
87  if ((x < 0) || (y < 0)) {
88  pi->del = true;
89  return -1;
90  }
91  else if ((x > 0) || (y > 0)) {
92  pj->del = true;
93  return 1;
94  }
95  else { /* points are coincident */
96  if (pi->vnum > pj->vnum)
97  pj->del = true;
98  else
99  pi->del = true;
100  return 0;
101  }
102  }
103 }
104 
105 /*---------------------------------------------------------------------
106 Performs the Graham scan on an array of angularly sorted points P.
107 ---------------------------------------------------------------------*/
108 t_stack Graham(t_H2D h2)
109 {
110  t_stack top;
111  int i;
112  t_point p1, p2; /* Top two points on stack. */
113 
114  /* Initialize stack. */
115  top = NULL;
116  top = Push (&h2.point[0], top);
117  top = Push (&h2.point[1], top);
118 
119  /* Bottom two elements will never be removed. */
120  i = 2;
121 
122  while (i < h2.nb_point) {
123  //post("Stack at top of while loop, i = %d, vnum = %d :", i, P[i].vnum);
124  //PrintStack( top );
125  if (!top->next)
126  return NULL; // Failure
127  p1 = top->next->p;
128  p2 = top->p;
129  if (Left(p1->v , p2->v, h2.point[i].v)) {
130  top = Push(&h2.point[i], top);
131  i++;
132  }
133  else top = Pop( top );
134  //PrintStack(top);
135  }
136  return top;
137 }
138 
139 /*---------------------------------------------------------------------
140 Pops off top elment of stack s, frees up the cell, and returns new top.
141 ---------------------------------------------------------------------*/
142 t_stack Pop(t_stack s)
143 {
144  t_stack top;
145 
146  top = s->next;
147  FREE( s );
148  return top;
149 }
150 
151 /*---------------------------------------------------------------------
152 Get a new cell, fill it with p, and push it onto the stack.
153 Return pointer to new stack top.
154 ---------------------------------------------------------------------*/
155 t_stack Push(t_point p, t_stack top)
156 {
157  t_stack s;
158 
159  /* Get new cell and fill it with point. */
160  NEW(s, t_cell);
161  s->p = p;
162  s->next = top;
163  return s;
164 }
165 
166 /*---------------------------------------------------------------------
167 Returns true if c is strictly to the left of the directed
168 line through a to b.
169 ---------------------------------------------------------------------*/
170 bool Left(t_xy a, t_xy b, t_xy c)
171 {
172  /*return Area2( a, b, c ) > 0;*/
173  return AreaSign( a, b, c ) > 0;
174 }
175 
176 int AreaSign(t_xy a, t_xy b, t_xy c)
177 {
178  double area2;
179 
180  area2 = ( b[0] - a[0] ) * ( c[1] - a[1] ) -
181  ( c[0] - a[0] ) * ( b[1] - a[1] );
182 
183  /* The area should be an integer. */
184  /*if (area2 > 0.5) return 1;
185  else if (area2 < -0.5) return -1;
186  else return 0;*/
187  if (area2 > 0) return 1;
188  else if (area2 < 0) return -1;
189  else return 0;
190 }
double t_xy[2]
Data structures to store a 2 dimensional convex hull.
Definition: hull2D.h:47
Compute convex hulls in 2 dimensions.
#define NEW(p, type)
Macros.
Definition: hull2D.h:37