Package org.orekit.rugged.intersection.duvenhage

Class MinMaxTreeTile

  • All Implemented Interfaces:
    Tile, UpdatableTile
    public class MinMaxTreeTile
extends SimpleTile
    Implementation of a Tile with a min/max kd tree.

    A n level min/max kd-tree contains sub-tiles merging individual cells together from coarse-grained (at level 0) to fine-grained (at level n-1). Level n-1, which is the deepest one, is computed from the raw cells by merging adjacent cells pairs columns (i.e. cells at indices (i, 2j) and (i, 2j+1) are merged together by computing and storing the minimum and maximum in a sub-tile. Level n-1 therefore has the same number of rows but half the number of columns of the raw tile, and its sub-tiles are 1 cell high and 2 cells wide. Level n-2 is computed from level n-1 by merging sub-tiles rows. Level n-2 therefore has half the number of rows and half the number of columns of the raw tile, and its sub-tiles are 2 cells high and 2 cells wide. Level n-3 is again computed by merging columns, level n-4 merging rows and so on. As depth decreases, the number of sub-tiles decreases and their size increase. Level 0 is reached when there is only either one row or one column of large sub-tiles.

    During the merging process, if at some stage there is an odd number of rows or columns, then the last sub-tile at next level will not be computed by merging two rows/columns from the current level, but instead computed by simply copying the last single row/column. The process is therefore well defined for any raw tile initial dimensions. A direct consequence is that the dimension of the sub-tiles in the last row or column may be smaller than the dimension of regular sub-tiles.

    If we consider for example a tall 107 ⨉ 19 raw tile, the min/max kd-tree will have 9 levels:

    "min/max kd-tree levels for a 107 x19 raw tile "
    Level Number of sub-tiles Regular sub-tiles dimension
    8 107 ⨉ 10 1 ⨉ 2
    7 54 ⨉ 10 2 ⨉ 2
    6 54 ⨉ 5 2 ⨉ 4
    5 27 ⨉ 5 4 ⨉ 4
    4 27 ⨉ 3 4 ⨉ 8
    3 14 ⨉ 3 8 ⨉ 8
    2 14 ⨉ 2 8 ⨉ 16
    1 7 ⨉ 2 16 ⨉ 16
    0 7 ⨉ 1 16 ⨉ 32
    Author:
    Luc Maisonobe
    See Also:
    MinMaxTreeTileFactory

    • Constructor Detail

      • MinMaxTreeTile

        protected MinMaxTreeTile()
        Simple constructor.

        Creates an empty tile.

    • Method Detail

      • processUpdatedElevation

        protected void processUpdatedElevation​(double[] elevations)
        Process elevation array at completion.

        This method is called at tile update completion, it is expected to be overridden by subclasses. The default implementation does nothing.

        Overrides:
        processUpdatedElevation in class SimpleTile
        Parameters:
        elevations - elevations array

      • getMinElevation

        public double getMinElevation​(int i,
                              int j,
                              int level)
        Get the minimum elevation at some level tree.

        Note that the min elevation is not computed only at cell center, but considering that it is interpolated considering also Eastwards and Northwards neighbors, and extends up to the center of these neighbors. As an example, lets consider four neighboring cells in some Digital Elevation Model:

        "four neighboring cells"
        j/i i i+1
        j+11112
        j 10 11
        When we interpolate elevation at a point located slightly South-West to the center of the (i+1, j+1) cell, we use all four cells in the interpolation, and we will get a result very close to 10 if we start close to (i+1, j+1) cell center. As the min value for this interpolation is stored at (i, j) indices, this implies that getMinElevation(i, j, l) must return 10 if l is chosen such that the sub-tile at tree level l includes cell (i,j) but not cell (i+1, j+1). In other words, interpolation implies sub-tile boundaries are overshoot by one column to the East and one row to the North when computing min.
        Parameters:
        i - row index of the cell
        j - column index of the cell
        level - tree level
        Returns:
        minimum value that can be reached when interpolating elevation in the sub-tile
        See Also:
        getLevels(), getMaxElevation(int, int, int), getMergeLevel(int, int, int, int)

      • getMaxElevation

        public double getMaxElevation​(int i,
                              int j,
                              int level)
        Get the maximum elevation at some level tree.

        Note that the max elevation is not computed only at cell center, but considering that it is interpolated considering also Eastwards and Northwards neighbors, and extends up to the center of these neighbors. As an example, lets consider four neighboring cells in some Digital Elevation Model:

        "four neighboring cells"
        j/i i i+1
        j+11110
        j 12 11
        When we interpolate elevation at a point located slightly South-West to the center of the (i+1, j+1) cell, we use all four cells in the interpolation, and we will get a result very close to 12 if we start close to (i+1, j+1) cell center. As the max value for this interpolation is stored at (i, j) indices, this implies that getMaxElevation(i, j, l) must return 12 if l is chosen such that the sub-tile at tree level l includes cell (i,j) but not cell (i+1, j+1). In other words, interpolation implies sub-tile boundaries are overshoot by one column to the East and one row to the North when computing max.
        Parameters:
        i - row index of the cell
        j - column index of the cell
        level - tree level
        Returns:
        maximum value that can be reached when interpolating elevation in the sub-tile
        See Also:
        getLevels(), getMinElevation(int, int, int), getMergeLevel(int, int, int, int)

      • locateMin

        public int[] locateMin​(int i,
                       int j,
                       int level)
        Locate the cell at which min elevation is reached for a specified level.

        Min is computed with respect to the continuous interpolated elevation, which takes four neighboring cells into account. This implies that the cell at which min value is reached for some level is either within the sub-tile for this level, or in some case it may be one column outside to the East or one row outside to the North. See SimpleTile.getMinElevation() for a more complete explanation.

        Parameters:
        i - row index of the cell
        j - column index of the cell
        level - tree level of the sub-tile considered
        Returns:
        row/column indices of the cell at which min elevation is reached

      • locateMax

        public int[] locateMax​(int i,
                       int j,
                       int level)
        Locate the cell at which max elevation is reached for a specified level.

        Max is computed with respect to the continuous interpolated elevation, which takes four neighboring cells into account. This implies that the cell at which max value is reached for some level is either within the sub-tile for this level, or in some case it may be one column outside to the East or one row outside to the North. See SimpleTile.getMaxElevation() for a more complete explanation.

        Parameters:
        i - row index of the cell
        j - column index of the cell
        level - tree level of the sub-tile considered
        Returns:
        row/column indices of the cell at which min elevation is reached

      • getMergeLevel

        public int getMergeLevel​(int i1,
                         int j1,
                         int i2,
                         int j2)
        Get the deepest level at which two cells are merged in the same min/max sub-tile.
        Parameters:
        i1 - row index of first cell
        j1 - column index of first cell
        i2 - row index of second cell
        j2 - column index of second cell
        Returns:
        deepest level at which two cells are merged in the same min/max sub-tile, or -1 if they are never merged in the same sub-tile
        See Also:
        getLevels(), getMinElevation(int, int, int), getMaxElevation(int, int, int)

      • getCrossedBoundaryRows

        public int[] getCrossedBoundaryRows​(int row1,
                                    int row2,
                                    int level)
        Get the index of sub-tiles start rows crossed.

        When going from one row to another row at some tree level, we cross sub-tiles boundaries. This method returns the index of these boundaries.

        Parameters:
        row1 - starting row
        row2 - ending row
        level - tree level
        Returns:
        indices of rows crossed at sub-tiles boundaries, in crossing order, the endpoints are included (i.e. if row1 or row2 are boundary rows, they will be in returned array)

      • getCrossedBoundaryColumns

        public int[] getCrossedBoundaryColumns​(int column1,
                                       int column2,
                                       int level)
        Get the index of sub-tiles start columns crossed.

        When going from one column to another column at some tree level, we cross sub-tiles boundaries. This method returns the index of these boundaries.

        Parameters:
        column1 - starting column
        column2 - ending column (excluded)
        level - tree level
        Returns:
        indices of columns crossed at sub-tiles boundaries, in crossing order, the endpoints are included (i.e. if column1 or column2 are boundary columns, they will be in returned array)

      • isColumnMerging

        public boolean isColumnMerging​(int level)
        Check if the merging operation between level and level-1 is a column merging.
        Parameters:
        level - level to check
        Returns:
        true if the merging operation between level and level-1 is a column merging, false if is a row merging