1 /****************************************************************************** 2 * 3 * File: delaunay.h 4 * 5 * Created: 04/08/2000 6 * 7 * Author: Pavel Sakov 8 * CSIRO Marine Research 9 * 10 * Purpose: Header for delaunay triangulation wrapper 11 * 12 * Description: None 13 * 14 * Revisions: 30/10/2007 PS: Added fields nflags, nflagsallocated and 15 * flagids for flag accounting, to make it possible to reset 16 * only engaged flags rather than the whole array. 17 * 18 *****************************************************************************/ 19 20 #if !defined(_DELAUNAY_H) 21 #define _DELAUNAY_H 22 23 #include "nn.h" 24 25 typedef struct { 26 int vids[3]; 27 } triangle; 28 29 typedef struct { 30 int tids[3]; 31 } triangle_neighbours; 32 33 typedef struct { 34 double x; 35 double y; 36 double r; 37 } circle; 38 39 #if !defined(_ISTACK_STRUCT) 40 #define _ISTACK_STRUCT 41 struct istack; 42 typedef struct istack istack; 43 #endif 44 45 #if !defined(_DELAUNAY_STRUCT) 46 #define _DELAUNAY_STRUCT 47 struct delaunay; 48 typedef struct delaunay delaunay; 49 #endif 50 51 /** Structure to perform the Delaunay triangulation of a given array of points. 52 * 53 * Contains a deep copy of the input array of points. 54 * Contains triangles, circles and edges resulted from the triangulation. 55 * Contains neighbour triangles for each triangle. 56 * Contains point to triangle map. 57 */ 58 struct delaunay { 59 int npoints; 60 point* points; 61 double xmin; 62 double xmax; 63 double ymin; 64 double ymax; 65 66 int ntriangles; 67 triangle* triangles; 68 circle* circles; 69 triangle_neighbours* neighbours; /* for delaunay_xytoi() */ 70 71 int* n_point_triangles; /* n_point_triangles[i] is number of 72 * triangles i-th point belongs to */ 73 int** point_triangles; /* point_triangles[i][j] is index of j-th 74 * triangle i-th point belongs to */ 75 76 int nedges; 77 int* edges; /* n-th edge is formed by points[edges[n*2]] 78 * and points[edges[n*2+1]] */ 79 80 /* 81 * Work data for delaunay_circles_find(). Placed here for efficiency 82 * reasons. Should be moved to the procedure if parallelizable code 83 * needed. 84 */ 85 int* flags; 86 int first_id; /* last search result, used in start up of a 87 * new search */ 88 istack* t_in; 89 istack* t_out; 90 91 /* 92 * to keep track of flags set to 1 in the case of very large data sets 93 */ 94 int nflags; 95 int nflagsallocated; 96 int* flagids; 97 }; 98 99 /* 100 * delaunay_build() and delaunay_destroy() belong to "nn.h" 101 */ 102 void delaunay_circles_find(delaunay* d, point* p, int* n, int** out); 103 int delaunay_xytoi(delaunay* d, point* p, int seed); 104 105 #endif 106