Stuck on recursive Fork/Join

Question

I have a method that returns a set of Points, I'm certain that the for loop portion of this method could be split into a RecursiveTask that returns a set of points for each thread.

I've tried a number of attempts but have come up short. Any java geniuses out there?

My existing method:

private Set<Point3D> getCordinatesAroundCenterPoint(Point3D point, int width) {
    Set<Point3D> points         =   new LinkedHashSet<>();

    double maxValue             =   width;
    double minValue             =   maxValue * -1;

    double minX                 =   point.getX() + minValue;
    double maxX                 =   point.getX() + maxValue;
    double minY                 =   point.getY() + minValue;
    double maxY                 =   point.getY() + maxValue;
    double minZ                 =   point.getY() + minValue;
    double maxZ                 =   point.getZ() + maxValue;
    double x                    =   point.getX();
    double y                    =   point.getY();
    double z                    =   point.getZ();

    double numberOfPoints       =   Math.pow((double) (maxValue * 2) + 1, Double.parseDouble("3"));     

    for (int i = 1; i <= numberOfPoints; i++) {
        if (x > maxX) {
            x = minX;
            y++;
        }

        if (y > maxY) {
            y = minY;
            z++;
        }

        if (z > maxZ) {
            z = minZ;
        }

        Point3D ppoint =    new Point3D();

        ppoint.setX(x);
        ppoint.setY(y);
        ppoint.setZ(z);

        points.add(ppoint);
        x++;
    }

    return points;
}

UPDATE #1:

Here is my attempt at splitting this into a recursive task, it seems to work fine with an extent of 1 (which should equal 27 points) -1, 0, +1, = 3 points, 3 cubed = 27. Any higher numbers for extent fails, for example an extent of 2 should return 125 points. -2, -1, 0, +1, +2 = 5 points, 5 cubed = 125.

Main.java:

public static void main(String[] args) {

        System.out.println("Enter system extent: ");

        BufferedReader bufferedReader   =   new BufferedReader(new InputStreamReader(System.in));

        try {
            String string                   =   bufferedReader.readLine();
            LinkedHashSet<Point3D> set      =   getStarSystemCordinatesAroundCenterSystem(Integer.parseInt(string));
            System.out.println(set.size() + " systems generated.");
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static LinkedHashSet<Point3D> getStarSystemCordinatesAroundCenterSystem(int extent) {
        ForkJoinPool pool           =   new ForkJoinPool();

        double maxValue             =   extent;
        double minValue             =   maxValue * -1;

        ForkPoints task =   new ForkPoints(minValue, maxValue);

        LinkedHashSet<Point3D> linkedHashSet = (LinkedHashSet<Point3D>) pool.invoke(task);

        return linkedHashSet;
    }

ForkPoints.java:

public class ForkPoints extends RecursiveTask<Set<Point3D>> {

    private static final long serialVersionUID = -5450450150370659468L;

    private double minValue;
    private double maxValue;

    static final double SEQUENTIAL_THRESHHOLD = 2;

    public ForkPoints(double minValue, double maxValue) {
        this.minValue   =   minValue;
        this.maxValue   =   maxValue;
    }

    @Override
    protected Set<Point3D> compute() {
        if (maxValue - minValue <= SEQUENTIAL_THRESHHOLD) {
            return computeValue(minValue, maxValue);
        } else {
            double midValue             =   minValue + SEQUENTIAL_THRESHHOLD;
            ForkPoints left             =   new ForkPoints(minValue, midValue);
            ForkPoints right            =   new ForkPoints(midValue, maxValue);
            left.fork();
            Set<Point3D> rightPoints    =   right.compute();
            Set<Point3D> leftPoints     =   left.join();
            leftPoints.addAll(rightPoints);
            return leftPoints;
        }
    }

    private Set<Point3D> computeValue(double minv, double maxv) {

        //Assume starting point of 0,0,0
        double minX                 =   0 + minv;
        double maxX                 =   0 + maxv;
        double minY                 =   0 + minv;
        double maxY                 =   0 + maxv;
        double minZ                 =   0 + minv;
        double maxZ                 =   0 + maxv;
        double x                    =   minv;
        double y                    =   minv;
        double z                    =   minv;

        Set<Point3D> points         =   new LinkedHashSet<>();

        boolean notFinished = true;

        while (notFinished) {
            if (x > maxX) {
                x = minX;
                y++;
            }

            if (y > maxY) {
                y = minY;
                z++;
            }

            if (z > maxZ) {
                z = minZ;
            }

            Point3D ppoint = new Point3D(); 

            ppoint.setX(x);
            ppoint.setY(y);
            ppoint.setZ(z);

            points.add(ppoint);
            if (x == maxX && y == maxY && z == maxZ) {
                notFinished = false;
            }
            x++;
        }

        return points;
    }
}

Answer 1

You're trying to split your task in parts, but you forgot your data are 3D: applying same constraints to all three coordinates limits the solution to a chain of cubes along the 'main diagonal', leaving all the other space unhandled. That's why you get only 54 points (one doubled) instead of 125: it is 27 + 27 (twice three-cubed), covering the cubes ((0,0,0)..(2,2,2)) and ((2,2,2)..(5,5,5)) with point (2,2,2) in common.

You can solve the issue in several ways. The simplest is possibly splitting the working space in halves, preferably at the longest edge, until parts have a number of points low enough.

public class ForkPoints extends RecursiveTask<Set<Point3D>> {

    private static final long serialVersionUID = -5450450150370659468L;

    private double minX;
    private double minY;
    private double minZ;
    private double maxX;
    private double maxY;
    private double maxZ;

    // max number of points allowed for a task
    static final double PTS_THRESHOLD = 25;

    // cube case
    public ForkPoints(double minValue, double maxValue) {
        this.minX   =   minValue;
        this.minY   =   minValue;
        this.minZ   =   minValue;
        this.maxX   =   maxValue;
        this.maxY   =   maxValue;
        this.maxZ   =   maxValue;
    }

    // rectangular cuboid case
    public ForkPoints(double minx, double maxx, double miny, double maxy, double minz, double maxz) {
        this.minX   =   minx;
        this.minY   =   miny;
        this.minZ   =   minz;
        this.maxX   =   maxx;
        this.maxY   =   maxy;
        this.maxZ   =   maxz;
    }

    @Override
    protected Set<Point3D> compute() {
        double dx = maxX - minX + 1;  // no of points
        double dy = maxY - minY + 1;  // in every
        double dz = maxZ - minZ + 1;  // direction

        if (dx*dy*dz <= PTS_THRESHOLD) {  // no of points to make
            return computeValue();    // cuboid small enough
        } else {
            bool splitx = (dx >= dy) && (dx >= dz);  // choose axis
            bool splity = !splitx && (dy >= dz);     // for split

            ForkPoints left;
            ForkPoints right;

            if (splitx) {
                double midx = Math.floor( (minx + maxx)/2);
                left    =   new ForkPoints(minx,   midx, miny, maxy, minz, maxz);
                right   =   new ForkPoints(midx+1, maxx, miny, maxy, minz, maxz);
            } else if (splity) {
                double midy = Math.floor( (miny + maxy)/2);
                left    =   new ForkPoints(minx, maxx, miny,   midy, minz, maxz);
                right   =   new ForkPoints(minx, maxx, midy+1, maxy, minz, maxz);
            } else {
                double midz = Math.floor( (minz + maxz)/2);
                left    =   new ForkPoints(minx, maxx, miny, maxy, minz,   midz);
                right   =   new ForkPoints(minx, maxx, miny, maxy, midz+1, maxz);
            }
            left.fork();
            Set<Point3D> rightPoints    =   right.compute();
            Set<Point3D> leftPoints     =   left.join();
            leftPoints.addAll(rightPoints);
            return leftPoints;
        }
    }

    private Set<Point3D> computeValue() {
        Set<Point3D> points =   new LinkedHashSet<>();

        for (double z = minZ; z < maxZ + 0.01; z += 1)
        for (double y = minY; y < maxY + 0.01; y += 1)
        for (double x = minX; x < maxX + 0.01; x += 1)
        {
            Point3D ppoint = new Point3D(); 

            ppoint.setX(x);
            ppoint.setY(y);
            ppoint.setZ(z);

            points.add(ppoint);
        }

        return points;
    }
}

Answer 2

The major problem here is you are trying to split 3D object, but splitting only in one direction. I.e. ForkPoints.compute() should actually produce not 2, but a minimum of 8 subtasks in case it's not able to perform calculations by itself.

Below is the example of how it may look like - minimal changes from your code:

public class ForkPoints extends RecursiveTask<Set<Point3D>> {

    private static final long serialVersionUID = -5450450150370659468L;

    private final Point3D origin;
    private final double radius;

    static final double SEQUENTIAL_THRESHHOLD = 5;

    public ForkPoints(final Point3D origin, final double radius) {
        this.origin = origin;
        this.radius = radius;
    }

    @Override
    protected Set<Point3D> compute() {
        if (radius <= SEQUENTIAL_THRESHHOLD) {
            return computeValue();
        } else {
            final ForkPoints subCubes[] = new ForkPoints[8];
            final double newRadius = radius / 2;

            Point3D newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[0] = new ForkPoints(newOrigin, newRadius);
            subCubes[0].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[1]   = new ForkPoints(newOrigin, newRadius);
            subCubes[1].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[2]   = new ForkPoints(newOrigin, newRadius);
            subCubes[2].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[3]   = new ForkPoints(newOrigin, newRadius);
            subCubes[3].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[4]   = new ForkPoints(newOrigin, newRadius);
            subCubes[4].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[5]   = new ForkPoints(newOrigin, newRadius);
            subCubes[5].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[6]   = new ForkPoints(newOrigin, newRadius);
            subCubes[6].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[7]   = new ForkPoints(newOrigin, newRadius);
            subCubes[7].fork();

            final Set<Point3D> results = new LinkedHashSet<Point3D>();
            for(final ForkPoints singleSubCube : subCubes) {
                results.addAll(singleSubCube.join());
            }

            return results;
        }
    }

    private Set<Point3D> computeValue() {
        double minX                 =   origin.getX() - radius;
        double maxX                 =   origin.getX() + radius;
        double minY                 =   origin.getY() - radius;
        double maxY                 =   origin.getY() + radius;
        double maxZ                 =   origin.getZ() + radius;
        double x                    =   minX;
        double y                    =   minY;
        double z                    =   origin.getZ() - radius;

        Set<Point3D> points         =   new LinkedHashSet<>();

        boolean notFinished = true;

        while (notFinished) {
            if (x > maxX) {
                x = minX;
                y++;
            }

            if (y > maxY) {
                y = minY;
                z++;
            }

            if (z > maxZ) {
                break;
            }

            Point3D ppoint = new Point3D(); 

            ppoint.setX(x);
            ppoint.setY(y);
            ppoint.setZ(z);

            points.add(ppoint);
            x++;
        }

        return points;
    }
}

But please note that there's still much work to be done with this code. As an example - two subtasks performing calculations for neighbouring spaces both generate points located on the mutual pane; current code excludes these duplicates by means of Point3D.equals(..) called by Set.addAll(..). In real life algorithm should not even generate them 'cause these duplicated points take a significant part of the overall generated points especially for low values of SEQUENTIAL_THRESHHOLD.