SearchTrees (version 0.5.5)

createTree: Create a Search Tree Index

Description

Create a search tree from the supplied data for use in during future lookups.

Usage

createTree(data, treeType = "quad", dataType = "point",
           columns = if (dataType=="point") 1:2 else 1:4, ...)

Value

The class of the returned object depends on the tree type created, though all will inherit from the SearchTree S4 class and have the following slots:

ref

An external pointer to the C level data structure.

numNodes

Total number of nodes comprising the tree.

dataNodes

Number of nodes which store at least one data point.

maxDepth

Maximum depth of the tree.

maxBucket

Maximum number of data points stored in a single node.

totalData

Number of items indexed in the tree.

dataType

Type of objects stored in the tree.

Arguments

data

data.frame or matrix. Data to be indexed.

treeType

Character. Indicates type of index tree to be created. Currently only "quad" (quad trees) is supported.

dataType

Character. Indicates type of data being indexed. Currently "point", and "rect" are supported corresponding to points and rectangles, respectively. Defaults to "point".

columns

Numeric. Indicates columns in data the information to be indexed can be found. Length depends on value of dataType (2 for "point" and 4 for "rect"). Defaults to columns 1 and 2. See Details.

...

Any additional/type specific parameters to be passed to the tree creation function. These include:

maxDepth:

Numeric. Maximum depth of the tree. Defaults to 7.

minNodeArea:

Numeric. Minimum (rectangular) area to be represented by a single node. When set, this overrides maxDepth

Author

Gabriel Becker

Details

For a point based tree, the two columns specified in columns represent the x and y values of the points.

For a rectangle based tree, four columns must be specified. These columns represent the x and y coordinates of point 1 and the x and y coordinates of point 2, in that order (where point 1 and point 2 specify the rectangle to be stored).

References

Finkel, R. A. and Bentley, J. L. "Quad Trees, a Data Structure for Retrieval on Composite Keys." Acta Informatica 4, 1-9, 1974.

See Also

SearchTree linkS4Class{QuadTree}

Examples

x = rnorm(100)
y = rnorm(100)
dat = cbind(x,y)
tree = createTree(dat)