Jamoma API  0.6.0.a19
hull2D.h
Go to the documentation of this file.
1 /**
2  @file
3 
4  @ingroup implementationMaxExternals
5 
6  @brief Compute convex hulls in 2 dimensions.
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.
11 
12  Input: 2n integer coordinates of points in the plane.
13  Output: the convex hull, cw, in PostScript; other output precedes the PS.
14 
15  NB: The original array storing the points is overwritten.
16 
17  Compile: gcc -o graham graham.c (or simply: make)
18 
19  Written by Joseph O'Rourke.
20  Last modified: October 1997
21  Questions to orourke@cs.smith.edu.
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 <stdio.h>
33 #include <math.h>
34 #include <stdlib.h>
35 
36 /** Macros */
37 #define NEW(p,type) if ((p=(type *) malloc (sizeof(type))) == NULL) {exit(EXIT_FAILURE);}
38 #define FREE(p) if (p) {free ((void *) p); p = NULL;}
39 #define SWAP(t,x,y) {t = x; x = y; y = t;}
40 
41 #define X 0
42 #define Y 1
43 
44 /** Data structures to store a 2 dimensional convex hull */
45 
46 /*--------- Point(s) Structure ---------*/
47 typedef double t_xy[2]; /* Type float point */
48 
49 typedef struct _structPoint t_structPoint;
50 typedef t_structPoint *t_point;
51 struct _structPoint {
52  t_xy v;
53  long vnum;
54  bool del;
55  t_xy p0;
56 };
57 
58 /*--------- Stack Structure ------------*/
59 typedef struct _cell t_cell;
60 typedef t_cell *t_stack;
61 struct _cell {
62  t_point p;
63  t_stack next;
64 };
65 
66 /*--------- Hull2D Structure ------------*/
67 typedef struct _H2D {
68  t_stack stack; ///< pointer to the top of the stack
69  t_structPoint point[64]; ///< TODO : a dynamic array
70  int nb_point; ///< Actual # of points (!!! init to 0 in new)
71  int nb_delete; ///< # deleted points (!!! init to 0 in new)
72 }t_H2D; ///< Convex hull in 2 dimension
73 
74 /*----------Function Prototypes-------------*/
75 void Swap(t_point point, int i, int j);
76 void Copy(t_point point, int i, int j);
77 void Delete(t_point point,int i);
78 int Compare(const void *tpi, const void *tpj);
79 int AreaSign(t_xy a, t_xy b, t_xy c);
80 t_stack Graham(t_H2D);
81 t_stack Pop(t_stack s);
82 t_stack Push(t_point point, t_stack top);
83 bool Left(t_xy a, t_xy b, t_xy c);
84 
85 
86 
87 
88 
89 
90 
91 
92 
93 
94 
95 
96 
t_xy
double t_xy[2]
Data structures to store a 2 dimensional convex hull.
Definition: hull2D.h:47