Реализация Octree генерирует стекопоток при перечислении более определенного количества объектов - PullRequest
Новая
       80

Реализация Octree генерирует стекопоток при перечислении более определенного количества объектов

0 голосов
/ 27 марта 2020

Класс octree (не мой, кредит: @siddeshpillai / https://github.com/siddeshpillai/Octree), который я немного изменил: 

public class Octree {

    public Point root;
    public Octree[] childNodes;
    boolean parent;
    public int depth;
    public double dimensions;

    public Octree(double x, Point p) {
        this.root = p;
        this.dimensions = x;
    }

    public Octree() {
        root = null;
    }

    public int i = 0;


    public void add_nodes(double x, double y, double z) {

        if (this.i < 8) {
            if (compare(x, y, z)) {
                if (root.childPoints == null) {
                    System.out.println("Root is null" + x + " " + y + " " + z);
                }

                this.root.childPoints[i] = new Point(x, y, z);
                this.i++;
            }
        } else if (this.childNodes == null) {

            this.create_nodes_of_nodes(x, y, z);

            for (int j = 0; j < 8; j++) {
                double tempx = this.root.x - root.childPoints[j].x;
                double tempy = this.root.y - root.childPoints[j].y;
                double tempz = this.root.z - root.childPoints[j].z;

                int checker = compareValues(tempx, tempy, tempz);

                this.childNodes[checker].add_nodes(root.childPoints[j].x,
                        root.childPoints[j].y, root.childPoints[j].z);

            }
            root.childPoints = null;

            double tempx = this.root.x - x;
            double tempy = this.root.y - y;
            double tempz = this.root.z - z;
            int checker = compareValues(tempx, tempy, tempz);
            this.childNodes[checker].add_nodes(x, y, z);

        } else {

            if (childNodes != null) {
                int checker = compareValues(x, y, z);
                childNodes[checker].add_nodes(x, y, z);

            }
        }
    }


    public int compareValues(double x, double y, double z) {

        if (x > 0 && y > 0 && z > 0)
            return 0;
        else if (x > 0 && y > 0 && z < 0)
            return 1;
        else if (x > 0 && y < 0 && z > 0)
            return 2;
        else if (x > 0 && y < 0 && z < 0)
            return 3;
        else if (x < 0 && y > 0 && z > 0)
            return 4;
        else if (x < 0 && y > 0 && z < 0)
            return 5;
        else if (x < 0 && y < 0 && z > 0)
            return 6;
        else
            return 7;

    }


    public boolean compare(double x, double y, double z) {
        if (x <= 2.0 && x >= -2.0) {
            if (y <= 2.0 && y >= -2.0) {
                if (z <= 2.0 && z >= -2.0) {
                    return true;
                }
            }
        }
        return false;
    }

    // dimension/2 power depth

    public double makeDimensions(double dimensions) {
        return (this.dimensions) / (2 ^ depth);
    }


    public void create_nodes_of_nodes(double x, double y, double z) {

        this.childNodes = new Octree[8];

        this.childNodes[0] = new Octree(this.dimensions / 2, new Point(
                this.root.x + dimensions / 2, this.root.y + dimensions / 2,
                this.root.z + dimensions / 2));

        this.childNodes[1] = new Octree(this.dimensions / 2, new Point(
                this.root.x + dimensions / 2, this.root.y + dimensions / 2,
                this.root.z - dimensions / 2));

        this.childNodes[2] = new Octree(this.dimensions / 2, new Point(
                this.root.x + dimensions / 2, this.root.y - dimensions / 2,
                this.root.z + dimensions / 2));

        this.childNodes[3] = new Octree(this.dimensions / 2, new Point(
                this.root.x + dimensions / 2, this.root.y - dimensions / 2,
                this.root.z - dimensions / 2));

        this.childNodes[4] = new Octree(this.dimensions / 2, new Point(
                this.root.x - dimensions / 2, this.root.y + dimensions / 2,
                this.root.z + dimensions / 2));

        this.childNodes[5] = new Octree(this.dimensions / 2, new Point(
                this.root.x - dimensions / 2, this.root.y + dimensions / 2,
                this.root.z - dimensions / 2));

        this.childNodes[6] = new Octree(this.dimensions / 2, new Point(
                this.root.x - dimensions / 2, this.root.y - dimensions / 2,
                this.root.z + dimensions / 2));

        this.childNodes[7] = new Octree(this.dimensions / 2, new Point(
                this.root.x - dimensions / 2, this.root.y - dimensions / 2,
                this.root.z - dimensions / 2));

    }
}

Класс точек: 

public class Point {
    Point[] childPoints;
    public double x, y, z;

    public Point(double _x, double _y, double _z) {
        this.x = _x;
        this.y = _y;
        this.z = _z;
        this.childPoints = new Point[8];
    }
}

Класс TestOctee: 

public class TestOctree {

    public static void main(String[] args) {

        int amount_of_octree_entries = 120;

        double[][] numbers = new double[amount_of_octree_entries][3];
        for (int i = 0; i < amount_of_octree_entries; i++) {
            for (int j = 0; j < 3; j++) {
                numbers[i][j] = Math.random()*4 - 2;
            }
        }

        Octree a = new Octree(2d, new Point(0d, 0d, 0d));


        for (int i = 0; i < amount_of_octree_entries; i++) {

                double x, y, z;
                x = numbers[i][0];
                y = numbers[i][1];
                z = numbers[i][2];
                a.add_nodes(x, y, z);

        }

        a.print_tree(); //Print the tree
    }
}

Класс непрерывно генерирует переполнение стека в методе add_nodes. более конкретно, при сравнении (x, y, z) и при рекурсивном вызове метода add_nodes в add_nodes.

Если amount_of_octree_entries равен 120, он только иногда генерирует переполнение стека, если число существенно выше, оно почти всегда бросает один. Я все еще новичок в java, так что я предполагаю, что это потому, что предел количества массивов находится в зависимости от того, где размещены случайные объекты. Может ли это быть так или я что-то упустил?

Как я могу изменить эту реализацию, чтобы структура октодерева могла вместить большее количество объектов?

...