Class: Quadtree

jsts.index.quadtree.Quadtree

new Quadtree()

A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of spatial objects need to be indexed they can be represented by their envelopes

The quadtree structure is used to provide a primary filter for range rectangle queries. The query() method returns a list of all objects which may intersect the query rectangle. Note that it may return objects which do not in fact intersect. A secondary filter is required to test for exact intersection. Of course, this secondary filter may consist of other tests besides intersection, such as testing other kinds of spatial relationships.

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accomodate any extent of dataset.

This data structure is also known as an MX-CIF quadtree following the usage of Samet and others.

Source:

Members

minExtent

minExtent is the minimum envelope extent of all items inserted into the tree so far. It is used as a heuristic value to construct non-zero envelopes for features with zero X and/or Y extent. Start with a non-zero extent, in case the first feature inserted has a zero extent in both directions. This value may be non-optimal, but only one feature will be inserted with this value.
Source:

Methods

(static) ensureExtent(itemEnv, minExtent) → {jsts.geom.Envelope}

Ensures an extent is not zero.
Parameters:
Name Type Description
itemEnv jsts.geom.Envelope The envelope to check.
minExtent Number the minimum width/height to expand the extent with if it is zero.
Source:
Returns:
A valid extent.
Type
jsts.geom.Envelope

collectStats(itemEnv)

Checks wheter a width and height of an envelope is above zero and sets minExtent if the widht or height is less than the current min extent
Parameters:
Name Type Description
itemEnv jsts.geom.Envelope The envelope.
Source:

depth() → {Number}

Returns the depth of the tree.
Source:
Returns:
the depth.
Type
Number

insert(itemEnv, item)

Inserts an item to the tree
Parameters:
Name Type Description
itemEnv jsts.geom.Envelope The envelope.
item Object The item.
Source:

query()

Querys the quadtree. Calls appropriate function depending on arguments
Source:

queryAll() → {Array}

Returns an array of all items in the quadtree.
Source:
Returns:
An array of all items in the quadtree.
Type
Array

queryByEnvelope(searchEnv) → {Array}

Queries the tree and returns items which may lie in the given search envelope. Precisely, the items that are returned are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be returned as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not returned - thus providing improved performance over a simple linear scan.
Parameters:
Name Type Description
searchEnv jsts.geom.Envelope the envelope of the desired query area.
Source:
Returns:
an array of items which may intersect the search envelope.
Type
Array

queryWithVisitor(searchEnv, visitor)

Queries the tree and visits items which may lie in the given search envelope. Precisely, the items that are visited are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be visited as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not visited - thus providing improved performance over a simple linear scan.
Parameters:
Name Type Description
searchEnv jsts.geom.Envelope the envelope of the desired query area.
visitor jsts.index.Visitor a visitor object which is passed the visited items.
Source:

remove(itemEnv, item) → {Boolean}

Removes a single item from the tree
Parameters:
Name Type Description
itemEnv jsts.geom.Envelope the envelope of the item to be removed.
item Object the item to remove.
Source:
Returns:
true if the item was found (and removed).
Type
Boolean

size() → {Number}

Returns the number of items in the tree.
Source:
Returns:
the number of items in the tree.
Type
Number