Package org.orekit.rugged.intersection.duvenhage

Class MinMaxTreeTile

java.lang.Object

org.orekit.rugged.raster.SimpleTile

org.orekit.rugged.intersection.duvenhage.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:

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

Nested Class Summary

Nested classes/interfaces inherited from interface org.orekit.rugged.raster.Tile

Tile.Location

Method Summary

Modifier and Type	Method	Description
int[]	getCrossedBoundaryColumns(int column1, int column2, int level)	Get the index of sub-tiles start columns crossed.
int[]	getCrossedBoundaryRows(int row1, int row2, int level)	Get the index of sub-tiles start rows crossed.
int	getLevels()	Get the number of kd-tree levels (not counting raw elevations).
double	getMaxElevation(int i, int j, int level)	Get the maximum elevation at some level tree.
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.
double	getMinElevation(int i, int j, int level)	Get the minimum elevation at some level tree.
boolean	isColumnMerging(int level)	Check if the merging operation between level and level-1 is a column merging.
int[]	locateMax(int i, int j, int level)	Locate the cell at which max elevation is reached for a specified level.
int[]	locateMin(int i, int j, int level)	Locate the cell at which min elevation is reached for a specified level.
protected void	processUpdatedElevation(double[] elevations)	Process elevation array at completion.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from class org.orekit.rugged.raster.SimpleTile

cellIntersection, getElevationAtIndices, getFloorLatitudeIndex, getFloorLongitudeIndex, getLatitudeAtIndex, getLatitudeRows, getLatitudeStep, getLocation, getLongitudeAtIndex, getLongitudeColumns, getLongitudeStep, getMaxElevation, getMaxElevationLatitudeIndex, getMaxElevationLongitudeIndex, getMaximumLatitude, getMaximumLongitude, getMinElevation, getMinElevationLatitudeIndex, getMinElevationLongitudeIndex, getMinimumLatitude, getMinimumLongitude, interpolateElevation, setElevation, setGeometry, tileUpdateCompleted

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

getLevels

public int getLevels()

Get the number of kd-tree levels (not counting raw elevations).

Returns:

number of kd-tree levels

See Also:

getMinElevation(int, int, int), getMaxElevation(int, int, int), getMergeLevel(int, int, int, int)

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:

j+1	11	10
j	12	11
j/i	i	i+1

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:

j+1	11	12
j	10	11
j/i	i	i+1

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