1 | //------------------------------------------------------------------------------ |
---|
2 | // quad_tree.h - Header for c implementation of the generic quad_tree. The |
---|
3 | // tree stores a set of triangles and then facilitates quickly |
---|
4 | // searching for a triangles in the list containing a given |
---|
5 | // point. |
---|
6 | // Tree has 'new' and 'delete' methods that should be called to |
---|
7 | // make sure memory is allocated and freed after use. |
---|
8 | // author: Padarn Wilson, date: 25/10/120 |
---|
9 | //------------------------------------------------------------------------------- |
---|
10 | #include <stdio.h> /* gets */ |
---|
11 | #include <stdlib.h> /* atoi, malloc */ |
---|
12 | #include <string.h> /* strcpy */ |
---|
13 | |
---|
14 | #ifndef quad_tree_H |
---|
15 | #define quad_tree_H |
---|
16 | |
---|
17 | |
---|
18 | // *********************************************************************** |
---|
19 | // triangle struct - Struct that stores data for triangles being inseted |
---|
20 | // into the tree. Triangles form a linked list for easy |
---|
21 | // storage. |
---|
22 | |
---|
23 | typedef struct triangle{ |
---|
24 | |
---|
25 | // points defining triangle. |
---|
26 | double x1,y1; |
---|
27 | double x2,y2; |
---|
28 | double x3,y3; |
---|
29 | |
---|
30 | // index stores the triangles unique id. |
---|
31 | int index; |
---|
32 | |
---|
33 | // outward normal vectors of triangles sides. |
---|
34 | double nx1,ny1; |
---|
35 | double nx2,ny2; |
---|
36 | double nx3,ny3; |
---|
37 | |
---|
38 | // next triangle turns the struct into a linked list. |
---|
39 | struct triangle * next; |
---|
40 | |
---|
41 | } triangle; |
---|
42 | |
---|
43 | // creates a new triangle and returns a pointer to the malloc'ed memory. |
---|
44 | triangle * new_triangle(int index, double x1, double x2, double x3, |
---|
45 | double y1, double y2, double y3); |
---|
46 | |
---|
47 | // deletes entire list of triangles |
---|
48 | void delete_triangle_list(triangle * T); |
---|
49 | |
---|
50 | // take a point and calculate 'sigma' with the given triangle. returns |
---|
51 | // a pointer to malloc'ed memory of a double array. |
---|
52 | double * calculate_sigma(triangle * T,double x,double y); |
---|
53 | |
---|
54 | // Tests to see if a triangle contains a given point, |
---|
55 | // returns a int value 0 false, 1 true. |
---|
56 | int triangle_contains_point(triangle * T,double pointx,double pointy); |
---|
57 | |
---|
58 | //************************************************************************** |
---|
59 | |
---|
60 | |
---|
61 | //************************************************************************** |
---|
62 | // quad_tree struct - Each quad_tree struct is a node in the tree, and |
---|
63 | // can be treated as an independent quad_tree. |
---|
64 | |
---|
65 | typedef struct quad_tree{ |
---|
66 | |
---|
67 | // rectangular extents of current node |
---|
68 | double xmin,xmax,ymin,ymax; |
---|
69 | int count; |
---|
70 | // parent and children of quad_tree |
---|
71 | struct quad_tree *parent; |
---|
72 | struct quad_tree *q[4]; |
---|
73 | |
---|
74 | // triangle stored in this node - leaves is a linked list of triangles |
---|
75 | triangle * leaves; |
---|
76 | // triangle end_leaves allows easy adding onto end of triangles |
---|
77 | triangle * end_leaves; |
---|
78 | |
---|
79 | } quad_tree; |
---|
80 | |
---|
81 | // returns a new quad_tree pointer with malloc'ed memory. Inputs are the |
---|
82 | // extents of the node. |
---|
83 | quad_tree* new_quad_tree(double xmin, double xmax, double ymin, double ymax); |
---|
84 | |
---|
85 | // delete a search tree - recursively deletes all children. |
---|
86 | void delete_quad_tree(quad_tree * tree); |
---|
87 | |
---|
88 | // add a new triangle to the quad_tree |
---|
89 | void quad_tree_insert_triangle(quad_tree *node,triangle *T); |
---|
90 | |
---|
91 | // returns the quadrant of the quad_tree containing the point, or 0 if intersects |
---|
92 | // center axes |
---|
93 | int trivial_contain_split_point(quad_tree *node, double xp,double yp); |
---|
94 | |
---|
95 | // returns the quadrant of the quad_tree containing the triangle, or 0 if intersects |
---|
96 | // center axes |
---|
97 | int trivial_contain_split(quad_tree *node, triangle *T); |
---|
98 | |
---|
99 | // returns the triangle in the quad_tree's leaves containing the point or NULL |
---|
100 | // if none of the triangles on the current quad_tree contain it. |
---|
101 | triangle * search_triangles_of_quad_tree(quad_tree * node,double xp,double yp); |
---|
102 | |
---|
103 | // search the tree for a triangle containing the given point. returns the triangle |
---|
104 | // if found, and NULL otherwise |
---|
105 | triangle * search(quad_tree * node ,double xp, double yp); |
---|
106 | |
---|
107 | // return number of noes in tree |
---|
108 | int quad_tree_node_count(quad_tree * tree); |
---|
109 | |
---|
110 | // split the node to make 4 children |
---|
111 | void quad_tree_make_children(quad_tree *node); |
---|
112 | |
---|
113 | // add a triangle to the nodes leaves |
---|
114 | void quad_tree_add_triangle_to_list(quad_tree *node,triangle *T); |
---|
115 | |
---|
116 | |
---|
117 | //************************************************************************** |
---|
118 | |
---|
119 | //************************************************************************** |
---|
120 | // quad_tree_ll struct - Used for serialising |
---|
121 | // |
---|
122 | |
---|
123 | typedef struct quad_tree_ll { |
---|
124 | |
---|
125 | void * tree; |
---|
126 | struct quad_tree_ll * next; |
---|
127 | int index; |
---|
128 | |
---|
129 | } quad_tree_ll; |
---|
130 | |
---|
131 | quad_tree_ll * new_quad_tree_ll(quad_tree * start,int index); |
---|
132 | |
---|
133 | //************************************************************************** |
---|
134 | |
---|
135 | //************************************************************************** |
---|
136 | // queue_ll struct - Used for deserialising |
---|
137 | // |
---|
138 | |
---|
139 | typedef struct queue_ll { |
---|
140 | |
---|
141 | int node; |
---|
142 | struct queue_ll * next; |
---|
143 | |
---|
144 | |
---|
145 | } queue_ll; |
---|
146 | |
---|
147 | queue_ll * new_queue_ll(int node); |
---|
148 | |
---|
149 | //************************************************************************** |
---|
150 | |
---|
151 | #endif |
---|