Class QuadTreeFloat

gdx/src/com/badlogic/gdx/utils/QuadTreeFloat.java:26–275

A quad tree that stores a float for each point. @author Nathan Sweet

/** A quad tree that stores a float for each point.
 * @author Nathan Sweet */
public class QuadTreeFloat implements Poolable {
	static public final int VALUE = 0, X = 1, Y = 2, DISTSQR = 3;

	static private final Pool<QuadTreeFloat> pool = new Pool(128, 4096) {
		protected Object newObject () {
			return new QuadTreeFloat();
		}
	};

	public final int maxValues, maxDepth;
	public float x, y, width, height;
	public int depth;
	public @Null QuadTreeFloat nw, ne, sw, se;

	/** For each entry, stores the value, x, and y. */
	public float[] values;

	/** The number of elements stored in {@link #values} (3 values per quad tree entry). */
	public int count;

	/** Creates a quad tree with 16 for maxValues and 8 for maxDepth. */
	public QuadTreeFloat () {
		this(16, 8);
	}

	/** @param maxValues The maximum number of values stored in each quad tree node. When exceeded, the node is split into 4 child
	 *           nodes. If the maxDepth has been reached, more than maxValues may be stored.
	 * @param maxDepth The maximum depth of the tree nodes. Nodes at the maxDepth will not be split and may store more than
	 *           maxValues number of entries. */
	public QuadTreeFloat (int maxValues, int maxDepth) {
		this.maxValues = maxValues * 3;
		this.maxDepth = maxDepth;
		values = new float[this.maxValues];
	}

	public void setBounds (float x, float y, float width, float height) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
	}

	public void add (float value, float valueX, float valueY) {
		int count = this.count;
		if (count == -1) {
			addToChild(value, valueX, valueY);
			return;
		}
		if (depth < maxDepth) {
			if (count == maxValues) {
				split(value, valueX, valueY);
				return;
			}
		} else if (count == values.length) //
			values = Arrays.copyOf(values, growValues());
		values[count] = value;
		values[count + 1] = valueX;
		values[count + 2] = valueY;