quadtree.h File Reference

#include <glib.h>

Go to the source code of this file.

Data Structures
struct	quadtree_item
struct	quadtree_node

Macros
#define	QUADTREE_NODE_CAPACITY   10

Functions
struct quadtree_node *	quadtree_node_new (struct quadtree_node *parent, double xmin, double xmax, double ymin, double ymax)
struct quadtree_item *	quadtree_find_nearest_flood (struct quadtree_node *this_, struct quadtree_item *item, double current_max, struct quadtree_node *toSkip)
struct quadtree_item *	quadtree_find_nearest (struct quadtree_node *this_, struct quadtree_item *item)
struct quadtree_item *	quadtree_find_item (struct quadtree_node *this_, struct quadtree_item *item)
struct quadtree_node *	quadtree_find_containing_node (struct quadtree_node *root, struct quadtree_item *item)
int	quadtree_delete_item (struct quadtree_node *root, struct quadtree_item *item)
void	quadtree_find_rect_items (struct quadtree_node *this_, double dXMin, double dXMax, double dYMin, double dYMax, GList **out)
void	quadtree_split (struct quadtree_node *this_)
void	quadtree_add (struct quadtree_node *this_, struct quadtree_item *item, struct quadtree_iter *iter)
	Add new node to quadtree. More...
void	quadtree_destroy (struct quadtree_node *this_)
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)
struct quadtree_item *	quadtree_item_next (struct quadtree_iter *iter)
void	quadtree_query_free (struct quadtree_iter *iter)
void	quadtree_item_delete (struct quadtree_iter *iter)
struct quadtree_data *	quadtree_data_dup (struct quadtree_data *qdata)
void	quadtree_node_drop_garbage (struct quadtree_node *node, struct quadtree_iter *iter)
	Free space occupied by deleted unreferenced items. More...

Macro Definition Documentation

QUADTREE_NODE_CAPACITY

#define QUADTREE_NODE_CAPACITY   10

Navit, a modular navigation system. Copyright (C) 2005-2011 Navit Team

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Function Documentation

quadtree_add()

void quadtree_add	(	struct quadtree_node *	this_,
		struct quadtree_item *	item,
		struct quadtree_iter *	iter
	)

Add new node to quadtree.

Parameters

this_	pointer to the quadtree (root) node
item	item to add
iter	Quadtree iteration context. Can be NULL if no garbage collection is needed.

Returns

nothing

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, dbg, quadtree_node::is_leaf, item, quadtree_node::items, lat, quadtree_item::latitude, quadtree_item::longitude, lvl_error, quadtree_node::node_num, QUADTREE_NODE_CAPACITY, quadtree_node_drop_garbage(), quadtree_node_new(), quadtree_split(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by csv_coord_set(), map_new_csv(), and quadtree_split().

quadtree_data_dup()

struct quadtree_data* quadtree_data_dup

(

struct quadtree_data *

qdata

)

References attr_dup(), quadtree_data::attr_list, quadtree_data::id_lo, quadtree_data::item, and quadtree_data::type.

Referenced by csv_coord_set().

quadtree_delete_item()

int quadtree_delete_item	(	struct quadtree_node *	root,
		struct quadtree_item *	item
	)

References quadtree_item::deleted, quadtree_node::items, quadtree_node::node_num, and quadtree_find_containing_node().

Referenced by csv_coord_set().

quadtree_destroy()

void quadtree_destroy

(

struct quadtree_node *

this_

)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, and quadtree_node::bb.

Referenced by map_destroy_csv().

quadtree_find_containing_node()

struct quadtree_node* quadtree_find_containing_node	(	struct quadtree_node *	root,
		struct quadtree_item *	item
	)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, quadtree_node::is_leaf, quadtree_node::items, quadtree_node::node_num, quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by quadtree_delete_item().

quadtree_find_item()

struct quadtree_item* quadtree_find_item	(	struct quadtree_node *	this_,
		struct quadtree_item *	item
	)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, quadtree_node::is_leaf, quadtree_node::items, quadtree_item::latitude, quadtree_item::longitude, quadtree_node::node_num, quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by csv_coord_set().

quadtree_find_nearest()

struct quadtree_item* quadtree_find_nearest	(	struct quadtree_node *	this_,
		struct quadtree_item *	item
	)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, dist_sq(), quadtree_node::is_leaf, quadtree_node::items, quadtree_item::latitude, quadtree_item::longitude, MAX_DOUBLE, quadtree_node::node_num, quadtree_node::parent, quadtree_find_nearest_flood(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

quadtree_find_nearest_flood()

struct quadtree_item* quadtree_find_nearest_flood	(	struct quadtree_node *	this_,
		struct quadtree_item *	item,
		double	current_max,
		struct quadtree_node *	toSkip
	)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, dist_sq(), quadtree_node::is_leaf, quadtree_node::items, quadtree_item::latitude, quadtree_item::longitude, quadtree_node::node_num, and nodes.

Referenced by quadtree_find_nearest().

quadtree_find_rect_items()

void quadtree_find_rect_items	(	struct quadtree_node *	this_,
		double	dXMin,
		double	dXMax,
		double	dYMin,
		double	dYMax,
		GList **	out
	)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, quadtree_node::is_leaf, quadtree_node::items, quadtree_item::latitude, quadtree_item::longitude, quadtree_node::node_num, nodes, quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

quadtree_item_delete()

void quadtree_item_delete

(

struct quadtree_iter *

iter

)

References quadtree_item::deleted, and quadtree_iter::item.

quadtree_item_next()

struct quadtree_item* quadtree_item_next

(

struct quadtree_iter *

iter

)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, dbg, quadtree_item::deleted, quadtree_iter_node::is_leaf, quadtree_node::is_leaf, quadtree_iter::item, quadtree_iter_node::item, quadtree_iter_node::items, quadtree_node::items, quadtree_iter::iter_nodes, lvl_debug, lvl_error, lvl_info, quadtree_iter_node::node, quadtree_iter_node::node_num, quadtree_node::node_num, nodes, quadtree_node::parent, quadtree_node_drop_garbage(), rects_overlap, quadtree_item::ref_count, quadtree_node::ref_count, quadtree_iter_node::subnode, quadtree_iter::xmax, quadtree_node::xmax, quadtree_iter::xmin, quadtree_node::xmin, quadtree_iter::ymax, quadtree_node::ymax, quadtree_iter::ymin, and quadtree_node::ymin.

Referenced by map_rect_get_item_csv(), quadtree_query_free(), and save_map_csv().

quadtree_node_drop_garbage()

void quadtree_node_drop_garbage	(	struct quadtree_node *	node,
		struct quadtree_iter *	iter
	)

Free space occupied by deleted unreferenced items.

Parameters

node	pointer to the quadtree node
iter	Quadtree iteration context.

Returns

nothing

References dbg, quadtree_iter::item_free, quadtree_iter::item_free_context, lvl_debug, and quadtree_node::node_num.

Referenced by quadtree_add(), and quadtree_item_next().

quadtree_node_new()

struct quadtree_node* quadtree_node_new	(	struct quadtree_node *	parent,
		double	xmin,
		double	xmax,
		double	ymin,
		double	ymax
	)

References quadtree_node::is_leaf, quadtree_node::parent, quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by map_new_csv(), quadtree_add(), and quadtree_split().

quadtree_query()

struct quadtree_iter* quadtree_query	(	struct quadtree_node *	this_,
		double	dXMin,
		double	dXMax,
		double	dYMin,
		double	dYMax,
		void(*)(void *context, struct quadtree_item *qitem)	item_free,
		void *	context
	)

References dbg, quadtree_iter_node::is_leaf, quadtree_node::is_leaf, quadtree_iter::item_free, quadtree_iter::item_free_context, quadtree_iter_node::items, quadtree_node::items, quadtree_iter::iter_nodes, lvl_debug, quadtree_iter_node::node, quadtree_iter_node::node_num, quadtree_node::node_num, quadtree_item::ref_count, quadtree_node::ref_count, quadtree_iter::xmax, quadtree_iter::xmin, quadtree_iter::ymax, and quadtree_iter::ymin.

Referenced by map_rect_new_csv(), and save_map_csv().

quadtree_query_free()

void quadtree_query_free

(

struct quadtree_iter *

iter

)

References quadtree_item_next().

Referenced by map_rect_destroy_csv(), and save_map_csv().

quadtree_split()

void quadtree_split

(

struct quadtree_node *

this_

)

References quadtree_node::aa, quadtree_node::ab, quadtree_node::ba, quadtree_node::bb, quadtree_node::is_leaf, quadtree_node::items, quadtree_item::latitude, quadtree_item::longitude, quadtree_node::node_num, quadtree_add(), quadtree_node_new(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by quadtree_add().