如何清理四叉树的边

Question

我一直在实现一个四叉树的版本来处理正方形的相交测试。然而，经过测试，算法出现了大量的噪声。示例如下:预览可以在这里看到。据我所知，四叉树应该只返回相交象限内的对象，但有挥之不去的边缘。

我的代码可以在这里看到:

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

我不确定是否我实现的算法不正确或使用错误的算法，但任何帮助将非常感激!我想做一些改变，使盒子更加基于象限，并解决这个边缘问题

Answer 1

哪里有

returns.addAll(objects);

在将每个对象添加到returns之前，您需要检查每个对象是否实际上与边界框相交(或者它是否在边界框内，取决于您希望它返回的对象)。