QuadTree.c File Reference

#include <sparse/general.h>
#include <common/geom.h>
#include <common/arith.h>
#include <math.h>
#include <sparse/QuadTree.h>
#include <stdbool.h>
#include <stddef.h>
#include <util/alloc.h>

Include dependency graph for QuadTree.c:

Go to the source code of this file.

Functions
double	distance_cropped (double *x, int dim, int i, int j)
static node_data	node_data_new (int dim, double weight, double *coord, int id)
static void	node_data_delete (node_data nd)
static void	check_or_realloc_arrays (int dim, int *nsuper, int *nsupermax, double **center, double **supernode_wgts, double **distances)
static void	QuadTree_get_supernodes_internal (QuadTree qt, double bh, double *pt, int nodeid, int *nsuper, int *nsupermax, double **center, double **supernode_wgts, double **distances, double *counts)
void	QuadTree_get_supernodes (QuadTree qt, double bh, double *pt, int nodeid, int *nsuper, int *nsupermax, double **center, double **supernode_wgts, double **distances, double *counts)
static double *	get_or_assign_node_force (double *force, int i, node_data l, int dim)
static double *	get_or_alloc_force_qt (QuadTree qt, int dim)
static void	QuadTree_repulsive_force_interact (QuadTree qt1, QuadTree qt2, double *x, double *force, double bh, double p, double KP, double *counts)
static void	QuadTree_repulsive_force_accumulate (QuadTree qt, double *force, double *counts)
void	QuadTree_get_repulsive_force (QuadTree qt, double *force, double *x, double bh, double p, double KP, double *counts)
QuadTree	QuadTree_new_from_point_list (int dim, int n, int max_level, double *coord)
QuadTree	QuadTree_new (int dim, double *center, double width, int max_level)
void	QuadTree_delete (QuadTree q)
static int	QuadTree_get_quadrant (int dim, double *center, double *coord)
QuadTree	QuadTree_new_in_quadrant (int dim, double *center, double width, int max_level, int i)
static QuadTree	QuadTree_add_internal (QuadTree q, double *coord, double weight, int id, int level)
QuadTree	QuadTree_add (QuadTree q, double *coord, double weight, int id)
static void	draw_polygon (FILE *fp, int dim, double *center, double width)
static void	QuadTree_print_internal (FILE *fp, QuadTree q, int level)
void	QuadTree_print (FILE *fp, QuadTree q)
static void	QuadTree_get_nearest_internal (QuadTree qt, double *x, double *y, double *min, int *imin, bool tentative)
void	QuadTree_get_nearest (QuadTree qt, double *x, double *ymin, int *imin, double *min)

Function Documentation

check_or_realloc_arrays()

static void check_or_realloc_arrays ( int  dim, int *  nsuper, int *  nsupermax, double **  center, double **  supernode_wgts, double **  distances  )

static

Definition at line 39 of file QuadTree.c.

References center(), dim, and gv_recalloc().

Referenced by QuadTree_get_supernodes_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

distance_cropped()

double distance_cropped ( double *  x, int  dim, int  i, int  j  )

extern

Definition at line 141 of file general.c.

References dim, dist(), distance(), and MINDIST.

Referenced by get_edge_label_matrix(), improve_contiguity(), QuadTree_repulsive_force_interact(), spring_electrical_embedding(), spring_electrical_embedding_slow(), spring_electrical_spring_embedding(), StressMajorizationSmoother2_new(), and TriangleSmoother_new().

Here is the call graph for this function:

Here is the caller graph for this function:

draw_polygon()

static void draw_polygon ( FILE *  fp, int  dim, double *  center, double  width  )

static

Definition at line 521 of file QuadTree.c.

References center(), and dim.

Referenced by QuadTree_print_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

get_or_alloc_force_qt()

static double * get_or_alloc_force_qt ( QuadTree  qt, int  dim  )

static

Definition at line 120 of file QuadTree.c.

References QuadTree_struct::data, dim, and gv_calloc().

Referenced by QuadTree_repulsive_force_accumulate(), and QuadTree_repulsive_force_interact().

Here is the call graph for this function:

Here is the caller graph for this function:

get_or_assign_node_force()

static double * get_or_assign_node_force ( double *  force, int  i, node_data  l, int  dim  )

static

Definition at line 109 of file QuadTree.c.

References node_data_struct::data, and dim.

Referenced by QuadTree_repulsive_force_accumulate(), and QuadTree_repulsive_force_interact().

Here is the caller graph for this function:

node_data_delete()

static void node_data_delete ( node_data  nd )

static

Definition at line 33 of file QuadTree.c.

References node_data_struct::coord, and free().

Referenced by QuadTree_add_internal(), and QuadTree_delete().

Here is the call graph for this function:

Here is the caller graph for this function:

node_data_new()

static node_data node_data_new ( int  dim, double  weight, double *  coord, int  id  )

static

Definition at line 22 of file QuadTree.c.

References coord(), node_data_struct::coord, node_data_struct::data, dim, gv_alloc(), gv_calloc(), id, node_data_struct::id, node_data_struct::node_weight, and NULL.

Referenced by QuadTree_add_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_add()

QuadTree QuadTree_add	(	QuadTree	q,
		double *	coord,
		double	weight,
		int	id
	)

Definition at line 515 of file QuadTree.c.

References coord(), and QuadTree_add_internal().

Referenced by QuadTree_new_from_point_list().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_add_internal()

static QuadTree QuadTree_add_internal ( QuadTree  q, double *  coord, double  weight, int  id, int  level  )

static

Definition at line 435 of file QuadTree.c.

References QuadTree_struct::average, QuadTree_struct::center, coord(), node_data_struct::coord, dim, QuadTree_struct::dim, gv_calloc(), node_data_struct::id, QuadTree_struct::l, MACHINEACC, QuadTree_struct::max_level, QuadTree_struct::n, node_data_struct::next, node_data_delete(), node_data_new(), node_data_struct::node_weight, NULL, QuadTree_struct::qts, QuadTree_add_internal(), QuadTree_get_quadrant(), QuadTree_new_in_quadrant(), QuadTree_struct::total_weight, and QuadTree_struct::width.

Referenced by QuadTree_add(), and QuadTree_add_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_delete()

void QuadTree_delete

(

QuadTree

q

)

Definition at line 375 of file QuadTree.c.

References QuadTree_struct::average, QuadTree_struct::center, QuadTree_struct::data, dim, QuadTree_struct::dim, free(), QuadTree_struct::l, node_data_struct::next, node_data_delete(), QuadTree_struct::qts, and QuadTree_delete().

Referenced by furtherest_point(), node_distinct_coloring(), QuadTree_delete(), spring_electrical_embedding(), spring_electrical_embedding_fast(), and spring_electrical_spring_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_nearest()

void QuadTree_get_nearest	(	QuadTree	qt,
		double *	x,
		double *	ymin,
		int *	imin,
		double *	min
	)

Definition at line 682 of file QuadTree.c.

References imin(), QuadTree_get_nearest_internal(), and ymin.

Referenced by make_map_internal(), and node_distinct_coloring_internal2().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_nearest_internal()

static void QuadTree_get_nearest_internal ( QuadTree  qt, double *  x, double *  y, double *  min, int *  imin, bool  tentative  )

static

Definition at line 632 of file QuadTree.c.

References QuadTree_struct::average, QuadTree_struct::center, coord(), node_data_struct::coord, dim, QuadTree_struct::dim, dist(), node_data_struct::id, imin(), QuadTree_struct::l, node_data_struct::next, point_distance(), QuadTree_struct::qts, QuadTree_get_nearest_internal(), and QuadTree_struct::width.

Referenced by QuadTree_get_nearest(), and QuadTree_get_nearest_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_quadrant()

static int QuadTree_get_quadrant ( int  dim, double *  center, double *  coord  )

static

Definition at line 396 of file QuadTree.c.

References center(), coord(), and dim.

Referenced by QuadTree_add_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_repulsive_force()

void QuadTree_get_repulsive_force	(	QuadTree	qt,
		double *	force,
		double *	x,
		double	bh,
		double	p,
		double	KP,
		double *	counts
	)

Definition at line 281 of file QuadTree.c.

References bh, dim, QuadTree_struct::dim, QuadTree_struct::n, QuadTree_repulsive_force_accumulate(), and QuadTree_repulsive_force_interact().

Referenced by spring_electrical_embedding_fast().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_supernodes()

void QuadTree_get_supernodes	(	QuadTree	qt,
		double	bh,
		double *	pt,
		int	nodeid,
		int *	nsuper,
		int *	nsupermax,
		double **	center,
		double **	supernode_wgts,
		double **	distances,
		double *	counts
	)

Definition at line 93 of file QuadTree.c.

References bh, center(), dim, QuadTree_struct::dim, gv_calloc(), and QuadTree_get_supernodes_internal().

Referenced by spring_electrical_embedding(), and spring_electrical_spring_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_get_supernodes_internal()

static void QuadTree_get_supernodes_internal ( QuadTree  qt, double  bh, double *  pt, int  nodeid, int *  nsuper, int *  nsupermax, double **  center, double **  supernode_wgts, double **  distances, double *  counts  )

static

Definition at line 50 of file QuadTree.c.

References QuadTree_struct::average, bh, QuadTree_struct::center, center(), check_or_realloc_arrays(), coord(), node_data_struct::coord, dim, QuadTree_struct::dim, dist(), node_data_struct::id, QuadTree_struct::l, node_data_struct::next, node_data_struct::node_weight, point_distance(), QuadTree_struct::qts, QuadTree_get_supernodes_internal(), QuadTree_struct::total_weight, and QuadTree_struct::width.

Referenced by QuadTree_get_supernodes(), and QuadTree_get_supernodes_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_new()

QuadTree QuadTree_new	(	int	dim,
		double *	center,
		double	width,
		int	max_level
	)

Definition at line 357 of file QuadTree.c.

References QuadTree_struct::average, QuadTree_struct::center, center(), QuadTree_struct::data, dim, QuadTree_struct::dim, gv_alloc(), gv_calloc(), QuadTree_struct::l, QuadTree_struct::max_level, QuadTree_struct::n, NULL, QuadTree_struct::qts, QuadTree_struct::total_weight, and QuadTree_struct::width.

Referenced by furtherest_point(), QuadTree_new_from_point_list(), and QuadTree_new_in_quadrant().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_new_from_point_list()

QuadTree QuadTree_new_from_point_list	(	int	dim,
		int	n,
		int	max_level,
		double *	coord
	)

Definition at line 309 of file QuadTree.c.

References center(), coord(), dim, free(), gv_calloc(), NULL, QuadTree_add(), QuadTree_new(), xmax, and xmin.

Referenced by lab_gamut_quadtree(), make_map_internal(), node_distinct_coloring(), spring_electrical_embedding(), spring_electrical_embedding_fast(), and spring_electrical_spring_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_new_in_quadrant()

QuadTree QuadTree_new_in_quadrant	(	int	dim,
		double *	center,
		double	width,
		int	max_level,
		int	i
	)

Definition at line 413 of file QuadTree.c.

References QuadTree_struct::center, center(), dim, and QuadTree_new().

Referenced by furtherest_point(), and QuadTree_add_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_print()

void QuadTree_print	(	FILE *	fp,
		QuadTree	q
	)

Definition at line 615 of file QuadTree.c.

References QuadTree_struct::dim, and QuadTree_print_internal().

Here is the call graph for this function:

QuadTree_print_internal()

static void QuadTree_print_internal ( FILE *  fp, QuadTree  q, int  level  )

static

Definition at line 576 of file QuadTree.c.

References QuadTree_struct::center, coord(), node_data_struct::coord, dim, QuadTree_struct::dim, draw_polygon(), node_data_struct::id, QuadTree_struct::l, node_data_struct::next, QuadTree_struct::qts, QuadTree_print_internal(), and QuadTree_struct::width.

Referenced by QuadTree_print(), and QuadTree_print_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_repulsive_force_accumulate()

static void QuadTree_repulsive_force_accumulate ( QuadTree  qt, double *  force, double *  counts  )

static

Definition at line 242 of file QuadTree.c.

References dim, QuadTree_struct::dim, get_or_alloc_force_qt(), get_or_assign_node_force(), node_data_struct::id, QuadTree_struct::l, QuadTree_struct::n, node_data_struct::next, node_data_struct::node_weight, QuadTree_struct::qts, QuadTree_repulsive_force_accumulate(), and QuadTree_struct::total_weight.

Referenced by QuadTree_get_repulsive_force(), and QuadTree_repulsive_force_accumulate().

Here is the call graph for this function:

Here is the caller graph for this function:

QuadTree_repulsive_force_interact()

static void QuadTree_repulsive_force_interact ( QuadTree  qt1, QuadTree  qt2, double *  x, double *  force, double  bh, double  p, double  KP, double *  counts  )

static

Definition at line 129 of file QuadTree.c.

References QuadTree_struct::average, bh, node_data_struct::coord, dim, QuadTree_struct::dim, dist(), distance_cropped(), get_or_alloc_force_qt(), get_or_assign_node_force(), node_data_struct::id, QuadTree_struct::l, QuadTree_struct::n, node_data_struct::next, node_data_struct::node_weight, point_distance(), QuadTree_struct::qts, QuadTree_repulsive_force_interact(), QuadTree_struct::total_weight, and QuadTree_struct::width.

Referenced by QuadTree_get_repulsive_force(), and QuadTree_repulsive_force_interact().

Here is the call graph for this function:

Here is the caller graph for this function: