java - 用Java实现方形分区

Question

我遇到了一个概念性问题。我想实现一个 Android 游戏，其中一个功能是:每次我触摸一个正方形，它被分成 4 个相同大小的小正方形。每个下一个正方形都以相同的方式划分，直到达到限制，比方说，原始大小的 1/1024。这是一个小插图:

问题是，我不确定如何以最佳方式存储这些数据。我需要存储每一 block 的大小，以便它知道分割后应该缩小到什么大小。例如，如果在第一次触摸和第一次除法之后，我的数组(对于 16 个元素限制)将如下所示:

0 0 1 1 
0 0 1 1
2 2 3 3 
2 2 3 3 

然后如果我触摸左上角的方 block ，下一个数组将是这样的:

[0,0] [0,1] 1 1 
[0,2] [0,3] 1 1
   2     2  3 3
   2     2  3 3

或者至少这是我能想到的。然而，这看起来实现起来很复杂，在每次下一次迭代中都会引入额外的维度，而且我不太确定如何正确地做到这一点。有什么想法吗？

Answer 1

使用四叉树。伪代码如下:

public class QuadTree {
    private QuadTree[] children;
    private double x;
    private double y;
    private double size;

    public QuadTree(double x, double y, double size) {
        this.x = x;
        this.y = y;
        this.size = size;
    }

    public void divide() {
        if (children == null) {
            children = new QuadTree[4];
            double s = 0.5 * size;
            children[0] = new QuadTree(x, y, s);
            children[1] = new QuadTree(x + s, y, s);
            children[2] = new QuadTree(x, y + s, s);
            children[3] = new QuadTree(x + s, y + s, s);
        }
    }

    public QuadTree getChild(int index) {
        if (children == null)
            return null;
        else
            return children[index];
    }