1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#ifndef GEOMETRY_H
#define GEOMETRY_H
#include <stdbool.h>
struct point_t {
double x, y;
void *data;
};
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* quadtree
*
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
struct quad_region_t {
struct point_t center;
double half_dim;
};
struct quadtree_node_t {
struct quad_region_t region;
int id;
/* children */
struct quadtree_node_t *nw, *ne, *sw, *se;
};
/* check if a region contains a point */
bool quad_contains_point(struct quad_region_t region,
struct point_t pt);
/* initialize a quadtree node */
struct quadtree_node_t quadtree_new_node(struct point_t center,
double half_dim);
/* subdivide a quadtree node
*
* if the node already contains a point, it will be moved into
* the appropriate child node
*/
void quadtree_subdivide(struct quadtree_node_t *node,
struct point_t *points);
/* insert a point into a quadtree */
bool quadtree_insert(struct quadtree_node_t *node,
struct point_t *points, int id);
/* get the closest point to a particular point in
* a quadtree
*/
int quadtree_get_closest(struct quadtree_node_t *root,
struct point_t *points,
struct point_t pt);
/* free a quadtree structure
*
* note that this will *NOT* free any point userdata!
*/
void quadtree_free(struct quadtree_node_t *root);
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* mesh
*
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
struct triangle_t {
struct point_t p1, p2, p3;
};
struct triangle_array_t {
int n_triangles;
struct triangle_t *triangles;
};
#endif
|
