source: trunk/anuga_core/source/anuga/utilities/quad_tree.h @ 8710

Last change on this file since 8710 was 8691, checked in by steve, 12 years ago

Adding in the new c files

File size: 4.7 KB
Line 
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
23typedef 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.
44triangle * new_triangle(int index, double x1, double x2, double x3,
45                                                double y1, double y2, double y3);
46
47// deletes entire list of triangles
48void 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.
52double * 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.
56int 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
65typedef 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.
83quad_tree* new_quad_tree(double xmin, double xmax, double ymin, double ymax);
84
85// delete a search tree - recursively deletes all children.
86void delete_quad_tree(quad_tree * tree);
87
88// add a new triangle to the quad_tree
89void 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
93int 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
97int 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.
101triangle * 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
105triangle * search(quad_tree * node ,double xp, double yp);
106
107// return number of noes in tree
108int quad_tree_node_count(quad_tree * tree);
109
110// split the node to make 4 children
111void quad_tree_make_children(quad_tree *node);
112
113// add a triangle to the nodes leaves
114void 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
123typedef struct quad_tree_ll {
124
125    void * tree;
126    struct quad_tree_ll * next;
127    int index;
128
129} quad_tree_ll;
130
131quad_tree_ll * new_quad_tree_ll(quad_tree * start,int index);
132
133//**************************************************************************
134
135//**************************************************************************
136// queue_ll struct - Used for deserialising 
137// 
138
139typedef struct queue_ll {
140
141    int node;
142    struct queue_ll * next;
143
144
145} queue_ll;
146
147queue_ll * new_queue_ll(int node);
148
149//**************************************************************************
150
151#endif
Note: See TracBrowser for help on using the repository browser.