createTree: Create a Search Tree Index

In SearchTrees: Spatial Search Trees

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, ...)

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

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).

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.

Author(s)

Gabriel Becker

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)

SearchTrees documentation built on Oct. 4, 2022, 1:06 a.m.