com.github.gwtd3.api.geom

Class Quadtree

java.lang.Object

com.google.gwt.core.client.JavaScriptObject

com.github.gwtd3.api.geom.Quadtree

public class Quadtree
extends com.google.gwt.core.client.JavaScriptObject

A quadtree is a two-dimensional recursive spatial subdivision.

This implementation uses square partitions, dividing each square into four equally-sized squares. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes.

Quadtrees can be used to accelerate various spatial operations, such as the Barnes-Hut approximation for computing n-body forces, or collision detection.

Author:

Anthony Schiochet

See Also:

http://bl.ocks.org/mbostock/4343214#index.html, http://bl.ocks.org/mbostock/1804919

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	Quadtree.Callback<T> A callback to be passed to RootNode#visit(Callback).
static class	Quadtree.Node<T> Node of the quadtree.
static class	Quadtree.RootNode<T> The root node of the quadtree.

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	Quadtree()

Method Summary

Methods

Modifier and Type	Method and Description
<T> Quadtree.RootNode<T>	apply(Array<T> points) Constructs a new quadtree for the specified array of points.
<T> Quadtree.RootNode<T>	apply(List<T> points) Constructs a new quadtree for the specified list of points.
Array<Array<Double>>	extent() Returns the current extent, which defaults to null.
Quadtree	extent(Array<Array<Double>> extent) If the specified extent is null, this causes the quadtree extent to be automatically computed for the initial array of points.
Quadtree	extent(double x0, double y0, double x1, double y1) If the specified extent is a two-dimensional array [‍[ x0, y0 ], [ x1, y1 ]], where x0 and y0 are the lower bounds of the extent, and x1 and y1 are the upper bounds of the extent, this sets the quadtree's extent.
Quadtree	x(DatumFunction<Double> xAccessor) Sets the x-coordinate accessor.
Quadtree	y(DatumFunction<Double> yAccessor) Sets the y-coordinate accessor.

Methods inherited from class com.google.gwt.core.client.JavaScriptObject

cast, createArray, createArray, createFunction, createObject, equals, hashCode, toSource, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Quadtree

protected Quadtree()

Method Detail

x

public final Quadtree x(DatumFunction<Double> xAccessor)

Sets the x-coordinate accessor.

The default accessor consider datum as a two element array and returns the first element.

Parameters:

xAccessor - the x accessor

Returns:

the current Quadtree

y

public final Quadtree y(DatumFunction<Double> yAccessor)

Sets the y-coordinate accessor.

The default accessor consider datum as a two element array and returns the first element.

Parameters:

yAccessor - the y accessor

Returns:

the current Quadtree

apply

public final <T> Quadtree.RootNode<T> apply(Array<T> points)

Constructs a new quadtree for the specified array of points.

The x and y coordinates of each point is determined using the default x(DatumFunction) and y(DatumFunction) accessors.

To build a quadtree by adding points incrementally, the specified points array can be empty, and points can be later added to the returned root node; in this case, you must also specify the extent() of the quadtree.

Returns the root of the quadtree.

Parameters:

points - the points

Returns:

the root of the quadtree

apply

public final <T> Quadtree.RootNode<T> apply(List<T> points)

Constructs a new quadtree for the specified list of points.

Returns the root of the quadtree.

Parameters:

points - the points

Returns:

the root of the quadtree

extent

public final Array<Array<Double>> extent()

Returns the current extent, which defaults to null.

Returns:

the current extent, which defaults to null.

extent

public final Quadtree extent(Array<Array<Double>> extent)

If the specified extent is null, this causes the quadtree extent to be automatically computed for the initial array of points.

If the specified extent is a two-dimensional array [‍[ x0, y0 ], [ x1, y1 ]], where x0 and y0 are the lower bounds of the extent, and x1 and y1 are the upper bounds of the extent, this sets the quadtree's extent.

Parameters:

extent - null to compute the extent with the initial array of points, or a 2-dim array [‍[ x0, y0 ], [ x1, y1 ]]

Returns:

the quadtree

extent

public final Quadtree extent(double x0,
              double y0,
              double x1,
              double y1)

If the specified extent is a two-dimensional array [‍[ x0, y0 ], [ x1, y1 ]], where x0 and y0 are the lower bounds of the extent, and x1 and y1 are the upper bounds of the extent, this sets the quadtree's extent.

Parameters:

x0 - the lower x coordinate of the extent

y0 - the lower y coordinate of the extent

x1 - the upper x coordinate of the extent

y1 - the upper y coordinate of the extent

Returns:

the quadtree