1 |
/**
|
2 |
* Navit, a modular navigation system.
|
3 |
* Copyright (C) 2005-2011 Navit Team
|
4 |
*
|
5 |
* This program is free software; you can redistribute it and/or
|
6 |
* modify it under the terms of the GNU General Public License
|
7 |
* version 2 as published by the Free Software Foundation.
|
8 |
*
|
9 |
* This program is distributed in the hope that it will be useful,
|
10 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
11 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
12 |
* GNU General Public License for more details.
|
13 |
*
|
14 |
* You should have received a copy of the GNU General Public License
|
15 |
* along with this program; if not, write to the
|
16 |
* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
|
17 |
* Boston, MA 02110-1301, USA.
|
18 |
*/
|
19 |
|
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 |
void* data;
|
31 |
};
|
32 |
|
33 |
struct quadtree_node {
|
34 |
int node_num;
|
35 |
struct quadtree_item items[QUADTREE_NODE_CAPACITY];
|
36 |
struct quadtree_node *aa;
|
37 |
struct quadtree_node *ab;
|
38 |
struct quadtree_node *ba;
|
39 |
struct quadtree_node *bb;
|
40 |
double xmin, xmax, ymin, ymax;
|
41 |
int is_leaf;
|
42 |
struct quadtree_node*parent;
|
43 |
};
|
44 |
|
45 |
struct quadtree_node* quadtree_node_new(struct quadtree_node* parent, double xmin, double xmax, double ymin, double ymax );
|
46 |
struct quadtree_item* quadtree_find_nearest_flood(struct quadtree_node* this_, struct quadtree_item* item, double current_max, struct quadtree_node* toSkip);
|
47 |
struct quadtree_item* quadtree_find_nearest(struct quadtree_node* this_, struct quadtree_item* item);
|
48 |
struct quadtree_item* quadtree_find_item(struct quadtree_node* this_, struct quadtree_item* item);
|
49 |
struct quadtree_node* quadtree_find_containing_node(struct quadtree_node* root, struct quadtree_item* item);
|
50 |
int quadtree_delete_item(struct quadtree_node* root, struct quadtree_item* item);
|
51 |
void quadtree_find_rect_items(struct quadtree_node* this_, double dXMin, double dXMax, double dYMin, double dYMax, GList**out);
|
52 |
void quadtree_split(struct quadtree_node* this_);
|
53 |
void quadtree_add(struct quadtree_node* this_, struct quadtree_item* item);
|
54 |
void quadtree_destroy(struct quadtree_node* this_);
|
55 |
|
56 |
|
57 |
|
58 |
#endif
|