Package org.apache.sis.internal.referencing

Class RTreeNode

java.lang.Object
org.apache.sis.io.wkt.FormattableObject
org.apache.sis.geometry.AbstractEnvelope
org.apache.sis.geometry.GeneralEnvelope
org.apache.sis.internal.referencing.RTreeNode
All Implemented Interfaces:
Serializable, Cloneable, Emptiable, org.opengis.geometry.Envelope
public class RTreeNode extends GeneralEnvelope
Placeholder for a RTree. This simple implementation is not designed for scalability or performance. This class is there for minimal service, to be replaced in some future Apache SIS version by a more sophisticated tree. Current version of this class is okay for small trees where big nodes are added before small nodes.

A RTreeNode instance is used as the root of the tree. Children nodes are stored as a linked list (the list is implemented by the sibling field, which reference the next element in the list).

Possible evolution: a future version could avoid extending GeneralEnvelope. Instead, we could provide abstract contains(…) methods and let subclasses define them, with possibly more efficient implementations. We would still need an implementation that delegate to GeneralEnvelope since that class has the advantage of handling envelopes crossing the anti-meridian.
Since:
1.1
Version:
1.1
Author:
Martin Desruisseaux (Geomatys)
See Also:

  • Constructor Details

    • RTreeNode

      public RTreeNode(org.opengis.geometry.Envelope area)
      Creates a new node for the given envelope.
      Parameters:
      area - the region covered by this node.

  • Method Details

    • getParent

      public final RTreeNode getParent()
      Returns the parent of this node, or null if none.
      Returns:
      the parent of this node, or null if none.

    • getChildren

      public final List<RTreeNode> getChildren()
      Returns the immediate children of this node, or an empty list if none.
      Returns:
      the immediate children of this node.

    • walk

      public static void walk(RTreeNode node, Consumer<? super RTreeNode> action)
      Executes the given action on the given node, all its children and all its siblings.
      Parameters:
      node - the node on which to execute the action, or null if none.
      action - the action to execute.

    • addNode

      public final void addNode(RTreeNode node)
      Adds the given node to the tree having this node as the root. This method assumes that this node or its siblings are likely to contain the nodes given to this method. This method will work even if this assumption does not hold, but the tree will be inefficient in such case.

      A "professional" R-Tree would make a better effort for creating a balanced tree here. Current version of this class uses a simple algorithm, okay for small trees where big nodes are added before small nodes. This is not a good general purpose R-Tree.

      Parameters:
      node - the node to add to this tree. If this node has sibling, they will be added too.
      See Also:

    • finish

      public final RTreeNode finish()
      Finishes the construction of the tree. This method should be invoked only on the instance on which addNode(RTreeNode) has been invoked. It performs the following tasks:
      1. Verify that all nodes have the same CRS or null CRS. An exception is thrown if incompatible CRS are found. This method does not verify the number of dimensions; this check should have been done by the caller.
      2. Set the CRS of all nodes to the common value found in previous step.
      3. Ensure that the tree has a single root, by creating a synthetic parent if necessary.
      Returns:
      the root of the tree, which is this if this node has no sibling.

    • locate

      public static RTreeNode locate(RTreeNode node, org.opengis.geometry.DirectPosition pos)
      Returns the node that contains the given position, or null if none. The given node does not need to be the root of the tree; it can be any node. This method will check that node first. If it does not contain the position, then this method goes up in the parent nodes.

      If consecutive positions are close to each other, then a good strategy is to give to this method the most recently used node.

      Parameters:
      node - any node in the tree. Should be node most likely to contain the position.
      pos - the position of the node to locate, or null if none.
      Returns:
      the smallest node containing the given position, or null if none.

    • hashCode

      public int hashCode()
      Returns a hash code value based on the this node and its children, ignoring the parent and the siblings.
      Returns:
      a hash code value for this node and its children.

    • equals

      public boolean equals(Object obj)
      Compares this node with the given object for equality, ignoring the parent and the siblings.
      Parameters:
      obj - the object to compare with this node.
      Returns:
      whether the two objects are of the same class, have equal envelope and equal children list.

    • formatTo

      protected String formatTo(Formatter formatter)
      Formats this envelope as a "DOMAIN" element (non-standard).
      Overrides:
      formatTo in class AbstractEnvelope
      Parameters:
      formatter - the formatter where to format the inner content of this envelope.
      Returns:
      the pseudo-WKT keyword, which is "Box" for this element.
      See Also:

    • toString

      public String toString()
      Returns a string representation of this node and its children as a tree. This method is for debugging purposes.
      Returns:
      a string representation of this node and all its children.

    • toTree

      public final TreeTable toTree()
      Returns a representation of this node and its children as a tree. This is mostly for debugging purposes.
      Returns:
      a tree representation of this node and all its children.

    • getDimension

      public int getDimension()
      Returns the length of coordinate sequence (the number of entries) in this envelope. This information is available even when the coordinate reference system is unknown.
      Specified by:
      getDimension in interface org.opengis.geometry.Envelope
      Returns:
      the dimensionality of this envelope.

    • getCoordinateReferenceSystem

      public org.opengis.referencing.crs.CoordinateReferenceSystem getCoordinateReferenceSystem()
      Returns the envelope coordinate reference system, or null if unknown. If non-null, it shall be the same as lower corner and upper corner CRS.
      Specified by:
      getCoordinateReferenceSystem in interface org.opengis.geometry.Envelope
      Returns:
      the envelope CRS, or null if unknown.

    • getLower

      public double getLower(int dimension) throws IndexOutOfBoundsException
      Returns the limit in the direction of decreasing coordinate values in the specified dimension. This is usually the algebraic minimum, except if this envelope spans the anti-meridian.
      Specified by:
      getLower in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the coordinate value.
      Returns:
      the starting coordinate value at the given dimension.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.
      See Also:

    • getUpper

      public double getUpper(int dimension) throws IndexOutOfBoundsException
      Returns the limit in the direction of increasing coordinate values in the specified dimension. This is usually the algebraic maximum, except if this envelope spans the anti-meridian.
      Specified by:
      getUpper in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the coordinate value.
      Returns:
      the starting coordinate value at the given dimension.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.
      See Also:

    • getMinimum

      public double getMinimum(int dimension) throws IndexOutOfBoundsException
      Returns the minimal coordinate value for the specified dimension. In the typical case of non-empty envelopes not crossing the anti-meridian, this method returns the AbstractEnvelope.getLower(int) value verbatim. In the case of envelope crossing the anti-meridian, this method returns the axis minimum value. If the range in the given dimension is invalid, then this method returns NaN.
      Specified by:
      getMinimum in interface org.opengis.geometry.Envelope
      Overrides:
      getMinimum in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the coordinate value.
      Returns:
      the minimal coordinate value at the given dimension.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.

    • getMaximum

      public double getMaximum(int dimension) throws IndexOutOfBoundsException
      Returns the maximal coordinate value for the specified dimension. In the typical case of non-empty envelopes not crossing the anti-meridian, this method returns the AbstractEnvelope.getUpper(int) value verbatim. In the case of envelope crossing the anti-meridian, this method returns the axis maximum value. If the range in the given dimension is invalid, then this method returns NaN.
      Specified by:
      getMaximum in interface org.opengis.geometry.Envelope
      Overrides:
      getMaximum in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the coordinate value.
      Returns:
      the maximal coordinate value at the given dimension.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.

    • getMedian

      public double getMedian(int dimension) throws IndexOutOfBoundsException
      Returns the median coordinate along the specified dimension. In most cases, the result is equal (minus rounding error) to:

      Crossing the anti-meridian of a Geographic CRS

      If upper < lower and the range meaning for the requested dimension is wraparound, then the median calculated above is actually in the middle of the space outside the envelope. In such cases, this method shifts the median value by half of the periodicity (180° in the longitude case) in order to switch from outer space to inner space. If the axis range meaning is not WRAPAROUND, then this method returns NaN.
      Specified by:
      getMedian in interface org.opengis.geometry.Envelope
      Overrides:
      getMedian in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the coordinate value.
      Returns:
      the median coordinate at the given dimension, or Double.NaN.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.
      See Also:

    • getSpan

      public double getSpan(int dimension) throws IndexOutOfBoundsException
      Returns the envelope span (typically width or height) along the specified dimension. In most cases, the result is equal (minus rounding error) to:

      Crossing the anti-meridian of a Geographic CRS

      If upper < lower and the range meaning for the requested dimension is wraparound, then the span calculated above is negative. In such cases, this method adds the periodicity (typically 360° of longitude) to the span. If the result is a positive number, it is returned. Otherwise this method returns NaN.
      Specified by:
      getSpan in interface org.opengis.geometry.Envelope
      Overrides:
      getSpan in class AbstractEnvelope
      Parameters:
      dimension - the dimension for which to obtain the span.
      Returns:
      the span (typically width or height) at the given dimension, or Double.NaN.
      Throws:
      IndexOutOfBoundsException - if the given index is negative or is equal or greater than the envelope dimension.

    • isEmpty

      public boolean isEmpty()
      Determines whether or not this envelope is empty. An envelope is empty if it has zero dimension, or if the span of at least one axis is negative, 0 or NaN.
      Note: Strictly speaking, there is an ambiguity if a span is NaN or if the envelope contains both 0 and infinite spans (since 0⋅∞ = NaN). In such cases, this method arbitrarily ignores the infinite values and returns true.
      If isEmpty() returns false, then AbstractEnvelope.isAllNaN() is guaranteed to also return false. However, the converse is not always true.
      Specified by:
      isEmpty in interface Emptiable
      Overrides:
      isEmpty in class AbstractEnvelope
      Returns:
      true if this envelope is empty.
      See Also:

    • isAllNaN

      public boolean isAllNaN()
      Returns false if at least one coordinate value is not NaN. This isAllNaN() check is different than the AbstractEnvelope.isEmpty() check since it returns false for a partially initialized envelope, while isEmpty() returns false only after all dimensions have been initialized. More specifically, the following rules apply:
      • If isAllNaN() == true, then isEmpty() == true
      • If isEmpty() == false, then isAllNaN() == false
      • The converse of the above-cited rules are not always true.
      Note that an all-NaN envelope can still have a non-null coordinate reference system.
      Overrides:
      isAllNaN in class AbstractEnvelope
      Returns:
      true if this envelope has NaN values.
      See Also: