TKDtree Struct Reference

A KD-tree. More...

#include <cuik-kdtree.h>

Collaboration diagram for TKDtree:

Data Fields
boolean	isLeaf
unsigned int	nd
unsigned int	n
unsigned int	m
double	r
Trectangle	ambient
unsigned int *	topology
unsigned int	height
double	volume
unsigned int	splitDim
double	splitValue
void *	left
void *	right
void *	leftLeaf
void *	rightLeaf
void *	nextLeaf
double **	p
unsigned int *	id
Trectangle	boundingBox
Trectangle	samplingBox

Detailed Description

This structure is used to represent a kd-tree or any kd-sub-tree, including leaves.

For simplicity reasons, we us a recursive implementation of most of the methods for the kd-tree.

Note that our implementation of the kd-tree does not include the points but only pointer to them.

Definition at line 52 of file cuik-kdtree.h.

Field Documentation

boolean isLeaf

TRUE if the sub-tree is a leaf

Definition at line 53 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SampleInKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int nd

Dimension of the ponits.

Definition at line 56 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int n

Number of points in this sub-tree.

Definition at line 57 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), NearestNeighbour(), NeighboursInBall(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int m

Maximum number of points in the leaves.

Definition at line 58 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), and BuildKDTree().

double r

The expansion factor to use in the sampling.

Definition at line 59 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), and KDtreeSamplingExpansion().

Trectangle ambient

Box defining the ambient space for all points.

Definition at line 60 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int* topology

Topology (Real,Circle) for each dimension.

Definition at line 61 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int height

Height of this sub-tree.

Definition at line 62 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), and BuildKDTree().

double volume

Volume of the sampling area.

Definition at line 63 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), and SampleInKDtree().

unsigned int splitDim

Dimension used to split the points.

Definition at line 66 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

double splitValue

Value used to split the points.

Definition at line 67 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), and PrintKDtree().

void* left

Left sub-tree.

Definition at line 68 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SampleInKDtree(), SearchInBallKDtree(), and SearchKDtree().

void* right

Rght sub-tree.

Definition at line 69 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SampleInKDtree(), SearchInBallKDtree(), and SearchKDtree().

void* leftLeaf

Left-most leaf in the sub-tree.

Definition at line 70 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), and BuildKDTree().

void* rightLeaf

Right-most leaf inthe sub-tree.

Definition at line 71 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), and BuildKDTree().

void* nextLeaf

Next leaf in the tree.

Definition at line 74 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), and BuildKDTree().

double** p

Points in the leaf.

Definition at line 75 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

unsigned int* id

Identifiers of the points in the leaf.

Definition at line 76 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

Trectangle boundingBox

Actual bouding box for the points.

Definition at line 77 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), PrintKDtree(), SearchInBallKDtree(), and SearchKDtree().

Trectangle samplingBox

Sampling box (the bounding box enlarged by 'r').

Definition at line 78 of file cuik-kdtree.h.

Referenced by AddPoint2KDtree(), BuildKDTree(), DeleteKDtree(), and SampleInKDtree().

---

The documentation for this struct was generated from the following file:

• cuik-kdtree.h