如何清理四叉树的边缘？

Question

我一直在实施四叉树的一个版本来处理正方形的相交测试。然而，在测试算法后，似乎有很多噪声。示例可以在这里看到： a preview 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;
}

我不确定我是否错误地实现了算法或使用了错误的算法，但我们将不胜感激！ 我想进行更改以使框更加基于象限并解决边缘问题。

Answer 1

你在哪里

returns.addAll(objects);

在将其添加到 returns 之前，您需要检查每个对象是否确实与边界框相交（或者它是否在边界框内，具体取决于您希望它与哪些对象相交 return）。

如何清理四叉树的边缘？

How to clean up edges of a quadtree?

java

algorithm

quadtree