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