quadtree.c File Reference

#include <stdlib.h>
#include <glib.h>
#include "debug.h"
#include "quadtree.h"

Data Structures
struct	quadtree_iter
struct	quadtree_iter_node

Macros
#define	QUADTREE_NODE_CAPACITY   10
#define	MAX_DOUBLE   9999999
#define	segments_overlap(x11, x12, x21, x22)   (((x11)<=(x21) && (x21)<=(x12)) || ((x21)<=(x11) && (x11)<=(x22)))
#define	rects_overlap(x11, y11, x12, y12, x21, y21, x22, y22)   (segments_overlap(x11,x12, x21,x22) && segments_overlap(y11,y12, y21,y22))

Functions
static double	dist_sq (double x1, double y1, double x2, double y2)
struct quadtree_node *	quadtree_node_new (struct quadtree_node *parent, double xmin, double xmax, double ymin, double ymax)
void	quadtree_find_rect_items (struct quadtree_node *this_, double dXMin, double dXMax, double dYMin, double dYMax, GList **out)
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_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)
struct quadtree_item *	quadtree_find_nearest (struct quadtree_node *this_, struct quadtree_item *item)
void	quadtree_node_drop_garbage (struct quadtree_node *node, struct quadtree_iter *iter)
	Free space occupied by deleted unreferenced items. More...
void	quadtree_add (struct quadtree_node *this_, struct quadtree_item *item, struct quadtree_iter *iter)
	Add new node to quadtree. More...
void	quadtree_split (struct quadtree_node *this_)
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 *item_free_context)
void	quadtree_query_free (struct quadtree_iter *iter)
void	quadtree_item_delete (struct quadtree_iter *iter)
struct quadtree_item *	quadtree_item_next (struct quadtree_iter *iter)

Macro Definition Documentation

MAX_DOUBLE

#define MAX_DOUBLE   9999999

Referenced by quadtree_find_nearest().

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.

Referenced by quadtree_add().

rects_overlap

#define rects_overlap	(		x11,
			y11,
			x12,
			y12,
			x21,
			y21,
			x22,
			y22
	)		(segments_overlap(x11,x12, x21,x22) && segments_overlap(y11,y12, y21,y22))

Referenced by quadtree_item_next().

segments_overlap

#define segments_overlap	(		x11,
			x12,
			x21,
			x22
	)		(((x11)<=(x21) && (x21)<=(x12)) || ((x21)<=(x11) && (x11)<=(x22)))

Function Documentation

dist_sq()

static double dist_sq ( double  x1, double  y1, double  x2, double  y2  )

static

Referenced by quadtree_find_nearest(), and quadtree_find_nearest_flood().

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, quadtree_iter::item, quadtree_node::items, lat, quadtree_item::latitude, quadtree_item::longitude, lvl_error, quadtree_node::node_num, quadtree_add(), 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(), quadtree_add(), and quadtree_split().

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, quadtree_node::bb, and quadtree_destroy().

Referenced by map_destroy_csv(), and quadtree_destroy().

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_item::latitude, quadtree_item::longitude, quadtree_node::node_num, quadtree_find_containing_node(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by quadtree_delete_item(), and quadtree_find_containing_node().

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_find_item(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by csv_coord_set(), and quadtree_find_item().

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(), quadtree_find_nearest_flood(), quadtree_node::xmax, quadtree_node::xmin, quadtree_node::ymax, and quadtree_node::ymin.

Referenced by quadtree_find_nearest().

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, nodes, quadtree_find_nearest_flood(), quadtree_iter::xmax, quadtree_iter::xmin, quadtree_iter::ymax, and quadtree_iter::ymin.

Referenced by quadtree_find_nearest(), and quadtree_find_nearest_flood().

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_find_rect_items(), quadtree_iter::xmax, quadtree_iter::xmin, quadtree_iter::ymax, and quadtree_iter::ymin.

Referenced by quadtree_find_rect_items().

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_node::is_leaf, quadtree_iter_node::is_leaf, quadtree_iter::item, quadtree_iter_node::item, quadtree_node::items, quadtree_iter_node::items, quadtree_iter::iter_nodes, lvl_debug, lvl_error, lvl_info, quadtree_iter_node::node, quadtree_node::node_num, quadtree_iter_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_iter::xmin, quadtree_iter::ymax, and quadtree_iter::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_item::deleted, quadtree_iter::item_free, quadtree_iter::item_free_context, quadtree_node::items, lvl_debug, quadtree_node::node_num, and quadtree_item::ref_count.

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_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_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 *	item_free_context
	)

References dbg, quadtree_node::is_leaf, quadtree_iter_node::is_leaf, quadtree_iter::item_free, quadtree_iter::item_free_context, quadtree_node::items, quadtree_iter_node::items, quadtree_iter::iter_nodes, lvl_debug, quadtree_iter_node::node, quadtree_node::node_num, quadtree_iter_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().