How to clean up edges of a quadtree?

Question

I have been implementing a version of a quadtree to handle intersection testing of squares. However, after testing the algorithm there appears to be a lot of noise. Example can be seen here: a preview can be seen here. From what I understand the quadtree should only be returning the objects within the intersecting quadrants but there are lingering edges.

My code can be seen here:

public class QuadTree extends BoundingBox implements IntersectionAlgorithm {

@Setter
private int MAX_OBJECTS = 10;
@Setter
private int MAX_LEVELS = 12;

private int level;
private List<BoundingBox> objects;
private QuadTree[] nodes;

public QuadTree(int width, int height){
    this(0, 0, 0, width, height);
}

private QuadTree(int pLevel, int x, int y, int width, int height) {
    super(x, y, width, height);
    this.level = pLevel;
    this.objects = new ArrayList<>();
    this.nodes = new QuadTree[4];
}

@Override
public void insert(BoundingBox box) {
    if (nodes[0] != null) {
        int index = getIndex(box);

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

            return;
        }
    }

    objects.add(box);

    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++;
            }
        }
    }
}

@Override
public List<BoundingBox> retrieve(BoundingBox box) {
    return this.retrieve(box, new ArrayList<>());
}

private List<BoundingBox> retrieve(BoundingBox box, List<BoundingBox> returns) {
    int index = getIndex(box);
    if (index != -1 && nodes[0] != null) {
        nodes[index].retrieve(box, returns);
    }

    returns.addAll(objects);

    return returns;
}

private void split() {
    int subWidth = (width / 2);
    int subHeight = (height / 2);

    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);
}

private int getIndex(BoundingBox pRect) {
    int index = -1;
    double verticalMidpoint = x + (width / 2);
    double horizontalMidpoint = y + (width/ 2);

    boolean topQuadrant = (pRect.getY() < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint);
    boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint);

    if (pRect.getX() < verticalMidpoint && pRect.getX() + pRect.getWidth() < verticalMidpoint) {
        if (topQuadrant) {
            index = 1;
        } else if (bottomQuadrant) {
            index = 2;
        }
    }
    else if (pRect.getX() > verticalMidpoint) {
        if (topQuadrant) {
            index = 0;
        } else if (bottomQuadrant) {
            index = 3;
        }
    }

    return index;
}

I am not sure if I implemented the algorithm incorrectly or am using the wrong algorithm but any help would be greatly appreciated! I would like to make changes to make the boxes a lot more quadrant based and resolve this limbo like edge problem.

Answer 1

Where you have

returns.addAll(objects);

you need to check if each object actually intersects the bounding box (or if it's inside the bounding box, depending on which objects you want it to return) before adding it to returns.