A Quadtree implementation

BoundingBox.java

/**
	 * Bounding Box for any object managed by the system.
	 *
	 * @author Frédéric Delorme
	 */
	public class BoundingBox {

		/**
		 * position for the boundingbox.
		 */
		Rectangle2D rect;
		/**
		 * diam1 is used for elipse1/circle/capsule BoundingBox type
		 */
		Ellipse2D elipse1;
		Ellipse2D elipse2;
		float e1e2Distance;
		/**
		 * list of specific points for POINT mode.
		 */
		Point[] points;

		BoundingBoxType type;

		public int intersect(BoundingBox b) {
			switch (type) {
			case NONE:
				return 0;
			case RECTANGLE:
				return (b.rect.intersects(rect) ? 1 : 0);
			case CIRCLE:
				return (b.elipse1.intersects(rect) ? 1 : 0);
			case CAPSULE:
				// TODO to be implemented later.
				return 0;
			case POINTS:
				// TODO to be implemented later.
				return 0;
			default:
				return 0;
			}
		}

		/**
		 * Update bounding box according to GameObject size and position.
		 *
		 * @param go
		 */
		public void update(GameObject go) {
			this.rect = new Rectangle2D.Float(go.position.x, go.position.y, go.width, go.height);
			this.elipse1 = new Ellipse2D.Float(go.position.x, go.position.y, go.width, go.height);
			// TODO compute distance for CAPSULE.
			// this.elipse2 = new Ellipse2D.Float(go.position.x, go.position.y, go.width,
			// go.height);
		}

		/**
		 * Create a new Bounding Box.
		 * 
		 * @return
		 */
		public BoundingBox builder() {
			return new BoundingBox();
		}

		/**
		 * Define the BoundingBoxType for this BoundingBox.
		 * 
		 * @param type type of the bounding box
		 * @return this object.
		 * @see BoundingBoxType
		 */
		public BoundingBox setType(BoundingBoxType type) {
			this.type = type;
			return this;
		}
	}

BoundingBoxType.java

	/**
	 * Bounding Box type can have 3 values. * `NONE` No bounding box, * `RECTANGLE`
	 * a simple rectangle as a bounding box, * `CIRCLE` a circle, * `CAPSULE` a
	 * capsule composed of 2 circles and a distance between its axes, * `POINTS` a
	 * list of points defining an object's frontier.
	 * 
	 * @author Frédéric Delorme
	 */
	public enum BoundingBoxType {
		NONE,
		/** No boundigbox */
		RECTANGLE, // a simple rectangle as a bounding box
		CIRCLE, // a circle
		CAPSULE, // a capsule composed of 2 circles and a distance between its axes.
		POINTS; // a list of points defining a perimeter.
	}

Collidable.java

	/**
	 * Interface to managed Collision with CollisionManager and QuadTree.
	 * 
	 * @author Frédéric Delorme
	 * 
	 * @see QuadTree
	 * @see CollisionManager
	 */
	public interface Collidable {

		BoundingBox getBoundingBox();

		void addCollider(Collidable c);
	}

QuadTree.java

/**
	 * A lot of this code was stolen from this article: <br>
	 * http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374
	 * <br>
	 * <br>
	 * created by chrislo27
	 *
	 */
	public class QuadTree {

		private int MAX_OBJECTS = 4;
		private int MAX_LEVELS = 12;

		private int level;
		private List<Collidable> objects;
		private float posX, posY, width, height;
		private QuadTree[] nodes;
		private int identifiedIndex;

		/**
		 * ideal constructor for making a quadtree that's empty <br>
		 * simply calls the normal constructor with <code>
		 * this(0, 0, 0, width, height)
		 * </code>
		 * 
		 * @param width  your game world width in units
		 * @param height your game world height in units
		 */
		public QuadTree(float width, float height) {
			this(0, 0, 0, width, height);
		}

		/**
		 * 
		 * @param pLevel start at level 0 if you're creating an empty quadtree
		 * @param x
		 * @param y
		 * @param width
		 * @param height
		 */
		public QuadTree(int pLevel, float x, float y, float width, float height) {
			level = pLevel;
			objects = new ArrayList<>();
			posX = x;
			posY = y;
			this.width = width;
			this.height = height;
			nodes = new QuadTree[4];
		}

		public QuadTree setMaxObjects(int o) {
			MAX_OBJECTS = o;
			return this;
		}

		public QuadTree setMaxLevels(int l) {
			MAX_LEVELS = l;
			return this;
		}

		public int getChecks() {
			int num = 0;

			num += (objects.size() * objects.size());

			for (int i = 0; i < nodes.length; i++) {
				if (nodes[i] != null) {
					num += nodes[i].getChecks();
				}
			}

			return num;
		}

		/*
		 * Clears the quadtree
		 */
		public void clear() {
			objects.clear();

			for (int i = 0; i < nodes.length; i++) {
				if (nodes[i] != null) {
					nodes[i].clear();
					nodes[i] = null;
				}
			}
		}

		/*
		 * Splits the node into 4 subnodes
		 */
		private void split() {
			float subWidth = (width / 2);
			float subHeight = (height / 2);
			float x = posX;
			float y = posY;

			nodes[0] = new QuadTree(level + 1, x + subWidth, y, subWidth, subHeight);
			nodes[1] = new QuadTree(level + 1, x, y, subWidth, subHeight);
			nodes[2] = new QuadTree(level + 1, x, y + subHeight, subWidth, subHeight);
			nodes[3] = new QuadTree(level + 1, x + subWidth, y + subHeight, subWidth, subHeight);
		}

		/*
		 * Determine which node the object belongs to. -1 means object cannot completely
		 * fit within a child node and is part of the parent node
		 */
		private int getIndex(Collidable col) {
			BoundingBox bb = col.getBoundingBox();
			int index = -1;
			double verticalMidpoint = posX + (width / 2);
			double horizontalMidpoint = posY + (width / 2);

			// Object can completely fit within the top quadrants
			boolean topQuadrant = (bb.rect.getX() < horizontalMidpoint
					&& bb.rect.getY() + bb.rect.getHeight() < horizontalMidpoint);
			// Object can completely fit within the bottom quadrants
			boolean bottomQuadrant = (bb.rect.getY() > horizontalMidpoint);

			// Object can completely fit within the left quadrants
			if (bb.rect.getX() < verticalMidpoint && bb.rect.getX() + bb.rect.getWidth() < verticalMidpoint) {
				if (topQuadrant) {
					index = 1;
				} else if (bottomQuadrant) {
					index = 2;
				}
			}
			// Object can completely fit within the right quadrants
			else if (bb.rect.getX() > verticalMidpoint) {
				if (topQuadrant) {
					index = 0;
				} else if (bottomQuadrant) {
					index = 3;
				}
			}
			identifiedIndex = index;

			return index;
		}

		/*
		 * Insert the object into the quadtree. If the node exceeds the capacity, it
		 * will split and add all objects to their corresponding nodes.
		 */
		public void insert(Collidable pRect) {
			if (nodes[0] != null) {
				int index = getIndex(pRect);

				if (index != -1) {
					nodes[index].insert(pRect);

					return;
				}
			}

			objects.add(pRect);

			if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
				if (nodes[0] == null) {
					split();
				}

				int i = 0;
				while (i < objects.size()) {
					int index = getIndex(objects.get(i));
					if (index != -1) {
						nodes[index].insert(objects.remove(i));
					} else {
						i++;
					}
				}
			}
		}

		/*
		 * Return all objects that could collide with the given object
		 */
		public List<Collidable> retrieve(List<Collidable> returnObjects, Collidable pRect) {
			int index = getIndex(pRect);
			if (index != -1 && nodes[0] != null) {
				nodes[index].retrieve(returnObjects, pRect);
			}

			returnObjects.addAll(objects);

			return returnObjects;
		}

		public void draw(Graphics2D g) {

			for (int i = 0; i < nodes.length; i++) {
				QuadTree n = nodes[i];
				if (n != null) {
					if (i == n.identifiedIndex) {
						g.setColor(Color.ORANGE);
					} else {
						g.setColor(Color.BLUE);
					}
					g.drawRect((int) n.posX, (int) n.posY, (int) n.width, (int) n.height);
					n.draw(g);
				}
			}
		}

	}