org.ka2ddo.yaac.osm.rtree

Class RTreeNode

java.lang.Object

org.ka2ddo.yaac.osm.rtree.RTreeNode

public class RTreeNode
extends java.lang.Object

This class represents one node in an R-tree, optimized for working with YAAC-encoded OpenStreetMap Ways and Nodes.

Author:

Andrew Pavlin, KA2DDO

Constructor Summary

Constructors

Constructor and Description
RTreeNode() Create a top-level (root) RTreeNode.

Method Summary

Modifier and Type	Method and Description
boolean	contains(Node node) Test if this RTreeNode's bounding box contains the specified OSM Node.
boolean	contains(Way way) Test if this RTreeNode's bounding box contains the specified OSM Way.
void	fitMBR(NodeSizeFunction nsf) Recompute the minimum bounding box for this RTreeNode.
int	getChildRTreeNodeCount() Get the number of direct children (not further descendents) of this RTreeNode.
int	getElementCount() Get the number of OSM elements in this RTreeNode.
int	getMaxDepth() Get the maximum depth of descendents of this RTreeNode.
int	getNodeCount() Get the total number of RTreeNodes in this r-tree.
float[]	getSpread() Get the statistics for the breadth-wise spread of the tree.
long[]	getTotalOverlap() Compute the total amount of overlap between sibling child nodes in the RTree.
void	insertGTN(Node node) Insert a new OSM Node into this RTreeNode.
void	insertGTN(Way way) Insert a new OSM Way into this RTreeNode.
boolean	intersects(int minLat, int maxLat, int minLon, int maxLon) Test if the specified bounding box intersects the minimum bounding box of this RTreeNode.
boolean	isOverfull() Test if this RTreeNode contains too many elements which should be split into sub-nodes.
java.util.List<GenericTaggedNode<?>>	search(int minLat, int maxLat, int minLon, int maxLon, NodeSizeFunction nsf) Search this RTreeNode hierarchy for all OSM elements that match the specified bounding box.
void	split(NodeSizeFunction nsf) Split all the elements of this node into subnodes for minimized overlap between the subnodes.
java.lang.String	toString() Returns a string representation of the object.

Methods inherited from class java.lang.Object

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

Constructor Detail

RTreeNode

public RTreeNode()

Create a top-level (root) RTreeNode.

Method Detail

contains

public boolean contains(Node node)

Test if this RTreeNode's bounding box contains the specified OSM Node.

Parameters:

node - Node to test

Returns:

boolean true if Node is contained inside this RtreeNode's bounds

insertGTN

public void insertGTN(Node node)

Insert a new OSM Node into this RTreeNode. Typically used to preload a root node prior to splitting into an r-tree hierarchy.

Parameters:

node - OSM Node to add to this RTreeNode's elements

contains

public boolean contains(Way way)

Test if this RTreeNode's bounding box contains the specified OSM Way.

Parameters:

way - Way to test

Returns:

boolean true if Way is contained inside this RtreeNode's bounds

insertGTN

public void insertGTN(Way way)

Insert a new OSM Way into this RTreeNode. Typically used to preload a root node prior to splitting into an r-tree hierarchy.

Parameters:

way - OSM Way to add to this RTreeNode's elements

isOverfull

public boolean isOverfull()

Test if this RTreeNode contains too many elements which should be split into sub-nodes.

Returns:

boolean true if element count > MAX_ELEMENTS_PER_CELL

fitMBR

public void fitMBR(NodeSizeFunction nsf)

Recompute the minimum bounding box for this RTreeNode.

Parameters:

nsf - NodeSizeFunction to determine the radius of Node objects

intersects

public boolean intersects(int minLat,
                          int maxLat,
                          int minLon,
                          int maxLon)

Test if the specified bounding box intersects the minimum bounding box of this RTreeNode.

Parameters:

minLat - int minimum latitude in millionths of degrees North

maxLat - int maximum latitude in millionths of degrees North

minLon - int minimum longitude in millionths of degrees East

maxLon - int maximum longitude in millionths of degrees East

Returns:

boolean true if bounding boxes intersect (including one entirely containing the other)

split

public void split(NodeSizeFunction nsf)

Split all the elements of this node into subnodes for minimized overlap between the subnodes. This should not be called unless elements.size() > MAX_ELEMENTS_PER_CELL.

Parameters:

nsf - NodeSizeFunction to calculate bounding box of a Node

search

public java.util.List<GenericTaggedNode<?>> search(int minLat,
                                                   int maxLat,
                                                   int minLon,
                                                   int maxLon,
                                                   NodeSizeFunction nsf)

Search this RTreeNode hierarchy for all OSM elements that match the specified bounding box.

Parameters:

minLat - int minimum latitude in millionths of degrees North

maxLat - int maximum latitude in millionths of degrees North

minLon - int minimum longitude in millionths of degrees East

maxLon - int maximum longitude in millionths of degrees East

nsf - NodeSizeFunction to calculate bounding box of OSM Nodes

Returns:

List of GenericTaggedNode (OSM) elements overlapping the specified bounding box

toString

public java.lang.String toString()

Returns a string representation of the object.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of the object.

getElementCount

public int getElementCount()

Get the number of OSM elements in this RTreeNode. This does not recurse into child nodes.

Returns:

count of GenericTaggedNode elements stored in this RTreeNode

getChildRTreeNodeCount

public int getChildRTreeNodeCount()

Get the number of direct children (not further descendents) of this RTreeNode.

Returns:

int child count

getMaxDepth

public int getMaxDepth()

Get the maximum depth of descendents of this RTreeNode.

Returns:

largest quantity of linear descendent RTreeNodes on any branch

getSpread

public float[] getSpread()

Get the statistics for the breadth-wise spread of the tree.

Returns:

array of float statistics, [0]=#welements, [1]=avg(#elements), [2]=SD(#elements), [3]=#noElements, [4]=min(#elements), [5]=max(#elements), [6]=#wchildren, [7]=avg(#children), [8]=SD(#children), [9]=#noChildren,[10]=min(#children),[11]=max(#children)

getTotalOverlap

public long[] getTotalOverlap()

Compute the total amount of overlap between sibling child nodes in the RTree.

Returns:

total overlap in millionths of a degree squared and the number of overlap pairs

getNodeCount

public int getNodeCount()

Get the total number of RTreeNodes in this r-tree.

Returns:

count of RTreeNodes in the tree