Class RTreeNode
java.lang.Object
org.apache.sis.io.wkt.FormattableObject
org.apache.sis.geometry.AbstractEnvelope
org.apache.sis.geometry.ArrayEnvelope
org.apache.sis.geometry.GeneralEnvelope
org.apache.sis.internal.referencing.RTreeNode
- All Implemented Interfaces:
Serializable
,Cloneable
,Emptiable
,org.opengis.geometry.Envelope
- Direct Known Subclasses:
SpecializableTransform.SubArea
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
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
The action for getting a common CRS for all nodes, then for setting the CRS of all nodes. -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionRTreeNode
(org.opengis.geometry.Envelope area) Creates a new node for the given envelope. -
Method Summary
Modifier and TypeMethodDescriptionfinal void
Adds the given node to the tree having this node as the root.boolean
Compares this node with the given object for equality, ignoring the parent and the siblings.final RTreeNode
finish()
Finishes the construction of the tree.protected String
Formats this envelope as a "DOMAIN
" element (non-standard).Returns the immediate children of this node, or an empty list if none.final RTreeNode
Returns the parent of this node, ornull
if none.int
hashCode()
Returns a hash code value based on the this node and its children, ignoring the parent and the siblings.static RTreeNode
Returns the node that contains the given position, ornull
if none.toString()
Returns a string representation of this node and its children as a tree.final TreeTable
toTree()
Returns a representation of this node and its children as a tree.private void
toTree
(TreeTable.Node addTo) Adds this node and its children to the given node.private boolean
tryAddChild
(RTreeNode candidate) Tries to add a child.static void
Executes the given action on the given node, all its children and all its siblings.Methods inherited from class org.apache.sis.geometry.GeneralEnvelope
add, add, castOrCopy, clone, horizontal, intersect, normalize, setCoordinateReferenceSystem, setEnvelope, setEnvelope, setRange, setTimeRange, setToInfinite, setToNaN, simplify, subEnvelope, translate, wraparound
Methods inherited from class org.apache.sis.geometry.ArrayEnvelope
getCoordinateReferenceSystem, getDimension, getLower, getMaximum, getMedian, getMinimum, getSpan, getUpper, isAllNaN, isEmpty
Methods inherited from class org.apache.sis.geometry.AbstractEnvelope
contains, contains, contains, equals, getLowerCorner, getMedian, getSpan, getTimeRange, getUpperCorner, intersects, intersects, toSimpleEnvelopes
Methods inherited from class org.apache.sis.io.wkt.FormattableObject
print, toString, toWKT
-
Field Details
-
serialVersionUID
private static final long serialVersionUIDFor cross-version compatibility.- See Also:
-
parent
The parent, ornull
if none.- See Also:
-
firstChild
The first node fully included in this code, ornull
if none. If non-null, that node and all its siblings shall be fully included in thisRTreeNode
. The child may contain other children, thus forming a tree from this wider node to smaller nodes.- See Also:
-
sibling
The next node having the same parent than this node. This is used for creating a linked list of nodes that are the children of the parent.Design note: anRTreeNode children
array instead offirstChild
+sibling
would be more intuitive. But the use of linked list avoid one level of indirection and is one less object to create for each node. The gain may be negligible with a few hundreds nodes, but a future version of this class may target much more numerous nodes.
-
-
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
Returns the parent of this node, ornull
if none.- Returns:
- the parent of this node, or
null
if none.
-
getChildren
Returns the immediate children of this node, or an empty list if none.- Returns:
- the immediate children of this node.
-
walk
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, ornull
if none.action
- the action to execute.
-
addNode
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:
-
tryAddChild
Tries to add a child. This method checks if the given candidate is fully included in thisRTreeNode
. The given node may have children but shall not have any sibling, because this method does not check if the siblings would also be included in this node.- Parameters:
candidate
- the single node (without sibling) to add as a child if possible.- Returns:
- whether the given node has been added.
-
finish
Finishes the construction of the tree. This method should be invoked only on the instance on whichaddNode(RTreeNode)
has been invoked. It performs the following tasks:- 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.
- Set the CRS of all nodes to the common value found in previous step.
- 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
Returns the node that contains the given position, ornull
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, ornull
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.- Overrides:
hashCode
in classArrayEnvelope
- Returns:
- a hash code value for this node and its children.
-
equals
Compares this node with the given object for equality, ignoring the parent and the siblings.- Overrides:
equals
in classArrayEnvelope
- 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
Formats this envelope as a "DOMAIN
" element (non-standard).- Overrides:
formatTo
in classAbstractEnvelope
- 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
Returns a string representation of this node and its children as a tree. This method is for debugging purposes.- Overrides:
toString
in classArrayEnvelope
- Returns:
- a string representation of this node and all its children.
-
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.
-
toTree
Adds this node and its children to the given node. This method invokes itself recursively.
-