com.github.davidmoten.rtree

Class RTree<T,S extends Geometry>

java.lang.Object

com.github.davidmoten.rtree.RTree<T,S>

Type Parameters:

T - the entry value type

S - the entry geometry type

public final class RTree<T,S extends Geometry>
extends Object

Immutable in-memory 2D R-Tree with configurable splitter heuristic.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RTree.Builder RTree Builder.

Field Summary

Fields

Modifier and Type	Field and Description
static int	MAX_CHILDREN_DEFAULT_GUTTMAN Benchmarks show that this is a good choice for up to O(10,000) entries when using Quadratic splitter (Guttman).
static int	MAX_CHILDREN_DEFAULT_STAR Benchmarks show that this is the sweet spot for up to O(10,000) entries when using R*-tree heuristics.

Method Summary

Methods

Modifier and Type	Method and Description
RTree<T,S>	add(Entry<? extends T,? extends S> entry) Returns an immutable copy of the RTree with the addition of given entry.
RTree<T,S>	add(Iterable<Entry<T,S>> entries) Returns an immutable RTree with the current entries and the additional entries supplied as a parameter.
rx.Observable<RTree<T,S>>	add(rx.Observable<Entry<T,S>> entries) Returns the Observable sequence of trees created by progressively adding entries.
RTree<T,S>	add(T value, S geometry) Returns an immutable copy of the RTree with the addition of an entry comprised of the given value and Geometry.
String	asString() Returns a human readable form of the RTree.
int	calculateDepth() The tree is scanned for depth and the depth returned.
Context	context() Returns a Context containing the configuration of the RTree at the time of instantiation.
static <T,S extends Geometry> RTree<T,S>	create() Returns a new Builder instance for RTree.
RTree<T,S>	delete(Entry<? extends T,? extends S> entry) Deletes one entry if it exists, returning an immutable copy of the RTree without that entry.
RTree<T,S>	delete(Entry<? extends T,? extends S> entry, boolean all) Deletes one or all matching entries depending on the value of all.
RTree<T,S>	delete(Iterable<Entry<T,S>> entries) Returns a new R-tree with the given entries deleted but only one matching occurence of each entry is deleted.
RTree<T,S>	delete(Iterable<Entry<T,S>> entries, boolean all) Returns a new R-tree with the given entries deleted.
rx.Observable<RTree<T,S>>	delete(rx.Observable<Entry<T,S>> entries, boolean all) Returns the Observable sequence of trees created by progressively deleting entries.
RTree<T,S>	delete(T value, S geometry) Deletes maximum one entry matching the given value and geometry.
RTree<T,S>	delete(T value, S geometry, boolean all) If all is false deletes one entry matching the given value and Geometry.
rx.Observable<Entry<T,S>>	entries() Returns all entries in the tree as an Observable sequence.
static rx.functions.Func1<Geometry,Boolean>	intersects(Rectangle r) Returns a predicate function that indicates if Geometry intersects with a given rectangle.
boolean	isEmpty() Returns true if and only if the R-tree is empty of entries.
static RTree.Builder	maxChildren(int maxChildren) Sets the max number of children in an R-tree node.
static RTree.Builder	minChildren(int minChildren) When the number of children in an R-tree node drops below this number the node is deleted and the children are added on to the R-tree again.
rx.Observable<Entry<T,S>>	nearest(Point p, double maxDistance, int maxCount) Returns the nearest k entries (k=maxCount) to the given point where the entries are strictly less than a given maximum distance from the point.
rx.Observable<Entry<T,S>>	nearest(Rectangle r, double maxDistance, int maxCount) Returns the nearest k entries (k=maxCount) to the given rectangle where the entries are strictly less than a given maximum distance from the rectangle.
rx.Observable<Entry<T,S>>	search(Point p) Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangle intersects with the given point.
rx.Observable<Entry<T,S>>	search(Point p, double maxDistance) Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangles are within maxDistance from the given point.
<R extends Geometry> rx.Observable<Entry<T,S>>	search(R g, double maxDistance, rx.functions.Func2<? super S,? super R,Double> distance) Returns all entries strictly less than maxDistance from the given geometry.
rx.Observable<Entry<T,S>>	search(Rectangle r) Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangle intersects with the given rectangle.
rx.Observable<Entry<T,S>>	search(Rectangle r, double maxDistance) Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangles are strictly less than maxDistance from the given rectangle.
<R extends Geometry> rx.Observable<Entry<T,S>>	search(R g, rx.functions.Func2<? super S,? super R,Boolean> intersects) Returns the intersections with the the given (arbitrary) geometry using an intersection function to filter the search results returned from a search of the mbr of g.
static RTree.Builder	selector(Selector selector) Sets the node Selector which decides which branches to follow when inserting or searching.
int	size() Returns the number of entries in the RTree.
static RTree.Builder	splitter(Splitter splitter) Sets the Splitter to use when maxChildren is reached.
static RTree.Builder	star() Sets the splitter to SplitterRStar and selector to SelectorRStar and defaults to minChildren=10.
Visualizer	visualize(int width, int height) Returns a Visualizer for an image of given width and height and restricted to the the smallest view that fully contains the coordinates.
Visualizer	visualize(int width, int height, Rectangle view) Returns a Visualizer for an image of given width and height and restricted to the given view of the coordinates.

Methods inherited from class java.lang.Object

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

Field Detail

MAX_CHILDREN_DEFAULT_GUTTMAN

public static final int MAX_CHILDREN_DEFAULT_GUTTMAN

Benchmarks show that this is a good choice for up to O(10,000) entries when using Quadratic splitter (Guttman).

See Also:

Constant Field Values

MAX_CHILDREN_DEFAULT_STAR

public static final int MAX_CHILDREN_DEFAULT_STAR

Benchmarks show that this is the sweet spot for up to O(10,000) entries when using R*-tree heuristics.

See Also:

Constant Field Values

Method Detail

create

public static <T,S extends Geometry> RTree<T,S> create()

Returns a new Builder instance for RTree. Defaults to maxChildren=128, minChildren=64, splitter=QuadraticSplitter.

Type Parameters:

T - the value type of the entries in the tree

S - the geometry type of the entries in the tree

Returns:

a new RTree instance

calculateDepth

public int calculateDepth()

The tree is scanned for depth and the depth returned. This involves recursing down to the leaf level of the tree to get the current depth. Should be log(n) in complexity.

Returns:

depth of the R-tree

minChildren

public static RTree.Builder minChildren(int minChildren)

When the number of children in an R-tree node drops below this number the node is deleted and the children are added on to the R-tree again.

Parameters:

minChildren - less than this number of children in a node triggers a node deletion and redistribution of its members

Returns:

builder

maxChildren

public static RTree.Builder maxChildren(int maxChildren)

Sets the max number of children in an R-tree node.

Parameters:

maxChildren - max number of children in an R-tree node

Returns:

builder

splitter

public static RTree.Builder splitter(Splitter splitter)

Sets the Splitter to use when maxChildren is reached.

Parameters:

splitter - the splitter algorithm to use

Returns:

builder

selector

public static RTree.Builder selector(Selector selector)

Sets the node Selector which decides which branches to follow when inserting or searching.

Parameters:

selector - determines which branches to follow when inserting or searching

Returns:

builder

star

public static RTree.Builder star()

Sets the splitter to SplitterRStar and selector to SelectorRStar and defaults to minChildren=10.

Returns:

builder

add

public RTree<T,S> add(Entry<? extends T,? extends S> entry)

Returns an immutable copy of the RTree with the addition of given entry.

Parameters:

entry - item to add to the R-tree.

Returns:

a new immutable R-tree including the new entry

add

public RTree<T,S> add(T value,
             S geometry)

Returns an immutable copy of the RTree with the addition of an entry comprised of the given value and Geometry.

Parameters:

value - the value of the Entry to be added

geometry - the geometry of the Entry to be added

Returns:

a new immutable R-tree including the new entry

add

public RTree<T,S> add(Iterable<Entry<T,S>> entries)

Returns an immutable RTree with the current entries and the additional entries supplied as a parameter.

Parameters:

entries - entries to add

Returns:

R-tree with entries added

add

public rx.Observable<RTree<T,S>> add(rx.Observable<Entry<T,S>> entries)

Returns the Observable sequence of trees created by progressively adding entries.

Parameters:

entries - the entries to add

Returns:

a sequence of trees

delete

public rx.Observable<RTree<T,S>> delete(rx.Observable<Entry<T,S>> entries,
                               boolean all)

Returns the Observable sequence of trees created by progressively deleting entries.

Parameters:

entries - the entries to add

all - if true delete all matching otherwise just first matching

Returns:

a sequence of trees

delete

public RTree<T,S> delete(Iterable<Entry<T,S>> entries,
                boolean all)

Returns a new R-tree with the given entries deleted. If all is false deletes only one if exists. If all is true deletes all matching entries.

Parameters:

entries - entries to delete

all - if false deletes one if exists else deletes all

Returns:

R-tree with entries deleted

delete

public RTree<T,S> delete(Iterable<Entry<T,S>> entries)

Returns a new R-tree with the given entries deleted but only one matching occurence of each entry is deleted.

Parameters:

entries - entries to delete

Returns:

R-tree with entries deleted up to one matching occurence per entry

delete

public RTree<T,S> delete(T value,
                S geometry,
                boolean all)

If all is false deletes one entry matching the given value and Geometry. If all is true deletes all entries matching the given value and geometry. This method has no effect if the entry is not present. The entry must match on both value and geometry to be deleted.

Parameters:

value - the value of the Entry to be deleted

geometry - the geometry of the Entry to be deleted

all - if false deletes one if exists else deletes all

Returns:

a new immutable R-tree without one or many instances of the specified entry if it exists otherwise returns the original RTree object

delete

public RTree<T,S> delete(T value,
                S geometry)

Deletes maximum one entry matching the given value and geometry. This method has no effect if the entry is not present. The entry must match on both value and geometry to be deleted.

Parameters:

value -

geometry -

Returns:

an immutable RTree without one entry (if found) matching the given value and geometry

delete

public RTree<T,S> delete(Entry<? extends T,? extends S> entry,
                boolean all)

Deletes one or all matching entries depending on the value of all. If multiple copies of the entry are in the R-tree only one will be deleted if all is false otherwise all matching entries will be deleted. The entry must match on both value and geometry to be deleted.

Parameters:

entry - the Entry to be deleted

all - if true deletes all matches otherwise deletes first found

Returns:

a new immutable R-tree without one instance of the specified entry

delete

public RTree<T,S> delete(Entry<? extends T,? extends S> entry)

Deletes one entry if it exists, returning an immutable copy of the RTree without that entry. If multiple copies of the entry are in the R-tree only one will be deleted. The entry must match on both value and geometry to be deleted.

Parameters:

entry - the Entry to be deleted

all - if true deletes all matches otherwise deletes first found

Returns:

a new immutable R-tree without one instance of the specified entry

intersects

public static rx.functions.Func1<Geometry,Boolean> intersects(Rectangle r)

Returns a predicate function that indicates if Geometry intersects with a given rectangle.

Parameters:

r - the rectangle to check intersection with

Returns:

whether the geometry and the rectangle intersect

search

public rx.Observable<Entry<T,S>> search(Rectangle r)

Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangle intersects with the given rectangle.

Parameters:

r - rectangle to check intersection with the entry mbr

Returns:

entries that intersect with the rectangle r

search

public rx.Observable<Entry<T,S>> search(Point p)

Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangle intersects with the given point.

Parameters:

p - point to check intersection with the entry mbr

Returns:

entries that intersect with the point p

search

public rx.Observable<Entry<T,S>> search(Rectangle r,
                               double maxDistance)

Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangles are strictly less than maxDistance from the given rectangle.

Parameters:

r - rectangle to measure distance from

maxDistance - entries returned must be within this distance from rectangle r

Returns:

the sequence of matching entries

search

public <R extends Geometry> rx.Observable<Entry<T,S>> search(R g,
                                                    rx.functions.Func2<? super S,? super R,Boolean> intersects)

Returns the intersections with the the given (arbitrary) geometry using an intersection function to filter the search results returned from a search of the mbr of g.

Type Parameters:

R - type of geometry being searched for intersection with

Parameters:

g - geometry being searched for intersection with

intersects - function to determine if the two geometries intersect

Returns:

a sequence of entries that intersect with g

search

public <R extends Geometry> rx.Observable<Entry<T,S>> search(R g,
                                                    double maxDistance,
                                                    rx.functions.Func2<? super S,? super R,Double> distance)

Returns all entries strictly less than maxDistance from the given geometry. Because the geometry may be of an arbitrary type it is necessary to also pass a distance function.

Type Parameters:

R - type of the geometry being searched for

Parameters:

g - geometry to search for entries within maxDistance of

maxDistance - strict max distance that entries must be from g

distance - function to calculate the distance between geometries of type S and R.

Returns:

entries strictly less than maxDistance from g

search

public rx.Observable<Entry<T,S>> search(Point p,
                               double maxDistance)

Returns an Observable sequence of all Entrys in the R-tree whose minimum bounding rectangles are within maxDistance from the given point.

Parameters:

p - point to measure distance from

maxDistance - entries returned must be within this distance from point p

Returns:

the sequence of matching entries

nearest

public rx.Observable<Entry<T,S>> nearest(Rectangle r,
                                double maxDistance,
                                int maxCount)

Returns the nearest k entries (k=maxCount) to the given rectangle where the entries are strictly less than a given maximum distance from the rectangle.

Parameters:

r - rectangle

maxDistance - max distance of returned entries from the rectangle

maxCount - max number of entries to return

Returns:

nearest entries to maxCount, in ascending order of distance

nearest

public rx.Observable<Entry<T,S>> nearest(Point p,
                                double maxDistance,
                                int maxCount)

Returns the nearest k entries (k=maxCount) to the given point where the entries are strictly less than a given maximum distance from the point.

Parameters:

p - point

maxDistance - max distance of returned entries from the point

maxCount - max number of entries to return

Returns:

nearest entries to maxCount, in ascending order of distance

entries

public rx.Observable<Entry<T,S>> entries()

Returns all entries in the tree as an Observable sequence.

Returns:

all entries in the R-tree

visualize

public Visualizer visualize(int width,
                   int height,
                   Rectangle view)

Returns a Visualizer for an image of given width and height and restricted to the given view of the coordinates. The points in the view are scaled to match the aspect ratio defined by the width and height.

Parameters:

width - of the image in pixels

height - of the image in pixels

view - using the coordinate system of the entries

Returns:

visualizer

visualize

public Visualizer visualize(int width,
                   int height)

Returns a Visualizer for an image of given width and height and restricted to the the smallest view that fully contains the coordinates. The points in the view are scaled to match the aspect ratio defined by the width and height.

Parameters:

width - of the image in pixels

height - of the image in pixels

Returns:

visualizer

isEmpty

public boolean isEmpty()

Returns true if and only if the R-tree is empty of entries.

Returns:

is R-tree empty

size

public int size()

Returns the number of entries in the RTree.

Returns:

the number of entries

context

public Context context()

Returns a Context containing the configuration of the RTree at the time of instantiation.

Returns:

the configuration of the RTree prior to instantiation

asString

public String asString()

Returns a human readable form of the RTree. Here's an example:

 mbr=Rectangle [x1=10.0, y1=4.0, x2=62.0, y2=85.0]
   mbr=Rectangle [x1=28.0, y1=4.0, x2=34.0, y2=85.0]
     entry=Entry [value=2, geometry=Point [x=29.0, y=4.0]]
     entry=Entry [value=1, geometry=Point [x=28.0, y=19.0]]
     entry=Entry [value=4, geometry=Point [x=34.0, y=85.0]]
   mbr=Rectangle [x1=10.0, y1=45.0, x2=62.0, y2=63.0]
     entry=Entry [value=5, geometry=Point [x=62.0, y=45.0]]
     entry=Entry [value=3, geometry=Point [x=10.0, y=63.0]]
 

Returns:

a string representation of the RTree