navit  0.5.1-trunk
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros Groups
quadtree.h
Go to the documentation of this file.
1 
20 #ifndef QUADTREE_H
21 #define QUADTREE_H
22 
23 #include <glib.h>
24 
25 #define QUADTREE_NODE_CAPACITY 10
26 
27 struct quadtree_item {
28  double longitude;
29  double latitude;
30  int ref_count;
31  int deleted;
32  void *data;
33 };
34 
35 struct quadtree_node {
36  int node_num;
38  struct quadtree_node *aa;
39  struct quadtree_node *ab;
40  struct quadtree_node *ba;
41  struct quadtree_node *bb;
42  double xmin, xmax, ymin, ymax;
43  int is_leaf;
45  int ref_count;
46 };
47 
48 struct quadtree_iter;
49 
50 struct quadtree_node* quadtree_node_new(struct quadtree_node* parent, double xmin, double xmax, double ymin, double ymax );
51 struct quadtree_item* quadtree_find_nearest_flood(struct quadtree_node* this_, struct quadtree_item* item, double current_max, struct quadtree_node* toSkip);
53 struct quadtree_item* quadtree_find_item(struct quadtree_node* this_, struct quadtree_item* item);
55 int quadtree_delete_item(struct quadtree_node* root, struct quadtree_item* item);
56 void quadtree_find_rect_items(struct quadtree_node* this_, double dXMin, double dXMax, double dYMin, double dYMax, GList**out);
57 void quadtree_split(struct quadtree_node* this_);
58 void quadtree_add(struct quadtree_node* this_, struct quadtree_item* item, struct quadtree_iter* iter);
59 void quadtree_destroy(struct quadtree_node* this_);
60 struct quadtree_iter *quadtree_query(struct quadtree_node *this_, double dXMin, double dXMax, double dYMin, double dYMax,void (*item_free)(void *context, struct quadtree_item *qitem), void *context);
61 struct quadtree_item * quadtree_item_next(struct quadtree_iter *iter);
62 void quadtree_query_free(struct quadtree_iter *iter);
63 void quadtree_item_delete(struct quadtree_iter *iter);
64 struct quadtree_data *quadtree_data_dup(struct quadtree_data *qdata);
66 
67 #endif
int is_leaf
Definition: quadtree.h:43
Definition: ch.c:41
Definition: gpx2navit_txt.h:51
int ref_count
Definition: quadtree.h:30
Definition: command.c:57
void quadtree_find_rect_items(struct quadtree_node *this_, double dXMin, double dXMax, double dYMin, double dYMax, GList **out)
Definition: quadtree.c:80
struct quadtree_item * quadtree_find_item(struct quadtree_node *this_, struct quadtree_item *item)
Definition: quadtree.c:160
int ref_count
Definition: quadtree.h:45
Definition: item.h:99
void quadtree_node_drop_garbage(struct quadtree_node *node, struct quadtree_iter *iter)
Free space occupied by deleted unreferenced items.
Definition: quadtree.c:359
Definition: quadtree.h:27
double ymin
Definition: quadtree.h:42
struct quadtree_item * quadtree_item_next(struct quadtree_iter *iter)
Definition: quadtree.c:589
double xmax
Definition: quadtree.h:42
struct quadtree_node * bb
Definition: quadtree.h:41
void quadtree_item_delete(struct quadtree_iter *iter)
Definition: quadtree.c:579
struct quadtree_node * quadtree_node_new(struct quadtree_node *parent, double xmin, double xmax, double ymin, double ymax)
Definition: quadtree.c:66
struct quadtree_iter * quadtree_query(struct quadtree_node *this_, double dXMin, double dXMax, double dYMin, double dYMax, void(*item_free)(void *context, struct quadtree_item *qitem), void *context)
Definition: quadtree.c:534
int node_num
Definition: quadtree.h:36
void quadtree_split(struct quadtree_node *this_)
Definition: quadtree.c:457
#define QUADTREE_NODE_CAPACITY
Definition: quadtree.h:25
double ymax
Definition: quadtree.h:42
Definition: csv.c:54
struct quadtree_item * quadtree_find_nearest_flood(struct quadtree_node *this_, struct quadtree_item *item, double current_max, struct quadtree_node *toSkip)
Definition: quadtree.c:114
void(* item_free)(void *context, struct quadtree_item *qitem)
Definition: quadtree.c:42
struct quadtree_node * quadtree_find_containing_node(struct quadtree_node *root, struct quadtree_item *item)
Definition: quadtree.c:211
struct quadtree_node * parent
Definition: quadtree.h:44
void quadtree_destroy(struct quadtree_node *this_)
Definition: quadtree.c:503
struct quadtree_node * ba
Definition: quadtree.h:40
Definition: quadtree.c:36
struct quadtree_node * aa
Definition: quadtree.h:38
int deleted
Definition: quadtree.h:31
struct quadtree_item * items[QUADTREE_NODE_CAPACITY]
Definition: quadtree.h:37
void * data
Definition: quadtree.h:32
void quadtree_query_free(struct quadtree_iter *iter)
Definition: quadtree.c:567
struct quadtree_data * quadtree_data_dup(struct quadtree_data *qdata)
Definition: csv.c:62
double longitude
Definition: quadtree.h:28
int quadtree_delete_item(struct quadtree_node *root, struct quadtree_item *item)
Definition: quadtree.c:258
struct quadtree_item * quadtree_find_nearest(struct quadtree_node *this_, struct quadtree_item *item)
Definition: quadtree.c:281
Definition: quadtree.h:35
double latitude
Definition: quadtree.h:29
void quadtree_add(struct quadtree_node *this_, struct quadtree_item *item, struct quadtree_iter *iter)
Add new node to quadtree.
Definition: quadtree.c:387
double xmin
Definition: quadtree.h:42
struct quadtree_node * ab
Definition: quadtree.h:39