CppQuadtree: C++ quadtree data structure

Source: R/CppQuadtree-class.R

The CppQuadtree class is the underlying C++ data structure used by the Quadtree S4 class. Note that the average user should not need to use these functions - there are R wrapper functions that provide access to the many of the member functions.

Details

This class is defined in 'src/QuadtreeWrapper.h' and 'src/QuadtreeWrapper.cpp'. When made available to R, it is exposed as CppQuadtree rather than QuadtreeWrapper. QuadtreeWrapper contains a pointer to a Quadtree C++ object (defined in 'src/Quadtree.h' and 'src/Quadtree.cpp'). All of the core functionality is in the Quadtree C++ class - QuadtreeWrapper is a wrapper class that adds the 'Rcpp' code required for it to be accessible from R.

Fields

constructor

  • Description: Default constructor. Can be used as follows: qt <- new(CppQuadtree)

  • Parameters: none

  • Returns: an empty CppQuadtree object

constructor

  • Description: Constructor. Can be used as follows: qt <- new(CppQuadtree, xlims, ylims, maxCellLength, minCellLength, splitAllNAs, splitAnyNAs). Used in quadtree(). The parameters for this constructor correspond with the similarly named parameters in quadtree() - see its documentation for more details on what the parameters signify. Note that the constructor does not "build" the quadtree structure - that is done by createTree().

  • Parameters:

    • xlims: two-element numeric vector (xmin, xmax)

    • ylims: two-element numeric vector (ymin, ymax)

    • maxCellLength: two-element numeric vector - first element is for the x dimension, second is for the y dimension

    • minCellLength: two-element numeric vector - first element is for the x dimension, second is for the y dimension

    • splitAllNAs: boolean

    • splitAnyNAs: boolean

readQuadtree

  • Description: Reads a quadtree from a file. Note that this is a static function, so it does not require an instance of CppQuadtree to be called. read_quadtree() is a wrapper for this function - see its documentation for more details.

  • Parameters:

    • filePath: string; the file to read from

  • Returns: a CppQuadtree

asList

  • Description: Outputs a list containing details about each cell. as_data_frame() is a wrapper for this function that rbinds the individual list elements into a data frame.

  • Parameters: none

  • Returns: a list of named numeric vectors. Each numeric vector provides information on a single cell. The elements returned are the same as the columns described in the documentation for as_data_frame() - see that help page for details.

asVector

  • Description: Returns cell values as a vector. as_vector() is a wrapper for this function.

  • Parameters:

    • terminalOnly: boolean; if TRUE, returns only the values of the terminal cells. If FALSE, returns all cell values

  • Returns: a numeric vector

copy

  • Description: Returns a deep copy of a quadtree. copy() is a wrapper for this function - see the documentation for that function for more details.

  • Parameters: none

  • Returns: a CppQuadtree object

createTree

  • Description: Constructs a quadtree from a matrix. quadtree() is a wrapper for this function and should be used to create quadtrees. The parameters correspond with the similarly named parameters in quadtree() - see the documentation of that function for details on the parameters.

  • Parameters:

    • mat: matrix; data to be used to create the quadtree

    • splitMethod: string

    • splitThreshold: double

    • splitFun: function

    • splitArgs: list

    • combineFun: function

    • combineArgs: list

    • templateQuadtree: CppQuadtree object

  • Returns: void - no return value

extent

  • Description: Returns the extent of the quadtree. This is equivalent to extent(qt, original = FALSE)

  • Parameters: none

  • Returns: four-element numeric vector, in this order: xmin, xmax, ymin, ymax

getCell

  • Description: Given the x and y coordinates of a point, returns the cell at that point.

  • Parameters:

    • pt: two-element numeric vector (x,y)

  • Returns: a CppNode object representing the cell that contains the point

getCells

  • Description: Given x and y coordinates of points, returns a list of the cells at those points (as CppNode objects). It is the same as getCell, except that it allows users to get multiple cells at once instead of one at a time.

  • Parameters:

    • x: numeric vector; the x coordinates

    • y: numeric vector; the y coordinates; must be the same length as x

  • Returns: a list of CppNode objects corresponding to the x and y coordinates passed to the function

getCellsDetails

  • Description: Given points defined by their x and y coordinates, returns a matrix giving details on the cells at each of the points. extract(qt, extents = TRUE) is a wrapper for this function.

  • Parameters:

    • x: numeric vector; the x coordinates

    • y: numeric vector; the y coordinates; must be the same length as x

  • Returns: A matrix with the cell details. See extract() for details about the matrix columns

getLcpFinder

  • Description: Returns a CppLcpFinder object that can be used to find least-cost paths on the quadtree. lcp_finder() is a wrapper for this function. For details on the parameters see the documentation of the similarly named parameters in lcp_finder().

  • Parameters:

    • startPoint: two-element numeric vector

    • xlim: two-element numeric vector

    • ylim: two-element numeric vector

    • searchByCentroid : boolean

  • Returns: a CppLcpFinder object

getNeighborList

  • Description: Returns the neighbor relationships between all cells.

  • Parameters: none

  • Returns: a list of matrices. Each matrix corresponds to a single cell and has one line for each neighboring cell. "neighbor" includes diagonal adjacency. Each matrix has the following columns:

    • id0, x0, y0, val0, hasChildren0: the ID, x and y coordinates of the centroid, cell value, and whether the cell has children. This is for the cell of interest. Note that the values of these columns will be same across all rows because they refer to the same cell.

    • id1, x1, y1, val1, hasChildren1: the ID, x and y coordinates of the centroid, cell value, and whether the cell has children. This is for the neighbors of the cell of interest. (i.e. the cell represented by the columns suffixed with '0').

getNeighbors

  • Description: Given a point, returns a matrix with info on the cells that neighbor the cell that the point falls in. get_neighbors() is a wrapper for this function.

  • Parameters:

    • pt: two-element numeric vector (x,y)

  • Returns: a six-column matrix with one row per neighboring cell. It has the following columns:

    • id

    • xmin

    • xmax

    • ymin

    • ymax

    • value

getValues

  • Description: Given points defined by their x and y coordinates, returns a numeric vector of the values of the cells at each of the points. extract(qt, extents = FALSE) is a wrapper for this function.

  • Parameters:

    • x: numeric vector; the x coordinates

    • y: numeric vector; the y coordinates; must be the same length as x

  • Returns: a numeric vector of cell values corresponding with the x and y coordinates passed to the function

maxCellDims

  • Description: Returns the maximum allowable cell length used when constructing the quadtree (i.e. the value passed to the max_cell_length parameter of quadtree()). Note that this does not return the maximum cell size in the quadtree - it returns the maximum allowable cell size. Also note that if no value was provided for max_cell_length, the max allowable cell length is set to the length and width of the total extent.

  • Parameters: none

  • Returns: A two-element numeric vector giving the maximum allowable side length for the x and y dimensions.

minCellDims

  • Description: Returns the minimum allowable cell length used when constructing the quadtree (i.e. the value passed to the min_cell_length parameter of quadtree()). Note that this does not return the minimum cell size in the quadtree - it returns the minimum allowable cell size. Also note that if no value was provided for min_cell_length, the min allowable cell length is set to -1.

  • Parameters: none

  • Returns: A two-element numeric vector giving the minimum allowable side length for the x and y dimensions.

nNodes

  • Description: Returns the total number of nodes in the quadtree. Note that this includes all nodes, not just terminal nodes.

  • Parameters: none

  • Returns: integer

originalDim

  • Description: Returns the dimensions of the raster used to create the quadtree before its dimensions were adjusted.

  • Parameters: none

  • Returns: two-element numeric vector that gives the number of cells along the x and y dimensions.

originalExtent

  • Description: Returns the extent of the raster used to create the quadtree before its dimensions/extent were adjusted. This is equivalent to extent(qt, original = TRUE)

  • Parameters: none

  • Returns: four-element numeric vector, in this order: xmin, xmax, ymin, ymax

originalRes

  • Description: Returns the resolution of the raster used to create the quadtree before its dimensions/extent were adjusted.

  • Parameters: none

  • Returns: two-element numeric vector (x cell length, y cell length)

print

  • Description: Returns a string that represents the quadtree.

  • Parameters: none

  • Returns: a string

projection

  • Description: Returns the projection of the quadtree.

  • Parameters: none

  • Returns: a string

root

  • Description: Returns the root node of the quadtree.

  • Parameters: none

  • Returns: a CppNode object

setOriginalValues

  • Description: Sets the properties that record the extent and dimensions of the original raster used to create the quadtree

  • Parameters:

    • xmin: double

    • xmax: double

    • ymin: double

    • ymax: double

    • nX: integer - number of cells along the x dimension

    • nY: integer - number of cells along the y dimension

  • Returns: void - no return value

setProjection

  • Description: Sets the the projection of the quadtree.

  • Parameters:

    • projection: string

  • Returns: void - no return value

setValues

  • Description: Given points defined by their x and y coordinates and a vector of values, sets the values of the quadtree cells at each of the points. set_values() is a wrapper for this function - see its documentation page for more details.

  • Parameters:

    • x: numeric vector; the x coordinates

    • y: numeric vector; the y coordinates; must be the same length as x

    • newVals: numeric vector; must be the same length as x and y

  • Returns: void - no return value

transformValues

  • Description: Uses a function to transform the values of all cells. transform_values() is a wrapper for this function - see its documentation page for more details.

  • Parameters:

    • trasform_fun: function

  • Returns: void - no return value

writeQuadtree

  • Description: Writes a quadtree to a file. write_quadtree() is a wrapper for this function - see its documentation page for more details.

  • Parameters:

    • filePath: string; the file to save the quadtree to

  • Returns: void - no return value