Java functional streams: generate a set of random points between distance A and B from each other

Question

While working on a toy project I was faced with the problem of generating a set of N 2d points where every point was between distance A and B from every other point in the set (and also within certain absolute bounds).

I prefer working with java streams and lambdas for practice, because of their elegance and the possibility for easy parallelization, so I'm not asking how to solve this problem in an imperative manner!

The solution that first came to mind was:

1. seed the set (or list) with a random vector
2. until the set reaches size N:
   1. create a random vector with length between A and B and add it to a random "parent" vector
   2. if it's outside the bounds or closer than A to any vector in the set, discard it, otherwise add it to the set
   3. repeat

This would be trivial for me with imperative programming (loops), but I was stumped when doing this the functional way because the newly generated elements in the stream depend on previously generated elements in the same stream.

Here's what I came up with - notice the icky loop at the beginning.

while (pointList.size() < size) {
    // find a suitable position, not too close and not too far from another one
    Vec point =
            // generate a stream of random vectors
            Stream.generate(vecGen::generate)
                    // elongate the vector and add it to the position of one randomly existing vector
                    .map(v -> listSelector.getRandom(pointList).add(v.mul(random.nextDouble() * (maxDistance - minDistance) + minDistance)))
                    // remove those that are outside the borders
                    .filter(v -> v.length < diameter)
                    // remove those that are too close to another one
                    .filter(v -> pointList.stream().allMatch(p -> Vec.distance(p, v) > minDistance))
                    // take the first one
                    .findAny().get();


    pointList.add(point);
}

I know that this loop might never terminate, depending on the parameters - the real code has additional checks.

One working functional solution that comes to mind is to generate completely random sets of N vectors until one of the sets satisfy the condition, but the performance would be abysmal. Also, this would circumvent the problem I'm facing: is it possible to work with the already generated elements in a stream while adding new elements to the stream (Pretty sure that would violate some fundamental principle, so I guess the answer is NO)?

Is there a way to do this in a functional - and not too wasteful - way?

Answer 1

A simple solution is shown below. The Pair class can be found in the Apache commons lang3.

public List<Pair<Double, Double>> generate(int N, double A, double B) {
    Random ySrc = new Random();

    return new Random()
            .doubles(N, A, B)
            .boxed()
            .map(x -> Pair.of(x, (ySrc.nextDouble() * (B - A)) + A))
            .collect(Collectors.toList());
}

My original solution (above) missed the point that A and B represented the minimum and maximum distance between any two points. So I would instead propose a different solution (way more complicated) that relies on generating points on a unit circle. I scale (multiply) the unit vector representing the point using a random distance with minimum of -1/2 B and maximum of 1/2 B. This approach uniformly distributes points in an area bounded by a circle of radius 1/2 B. This addresses the maximum distance between points constraint. Given sufficient difference between A and B, where A < B, and N is not too large, the minimum distance constraint will probably also be satisfied.Satisfying the maximum distance constraint can be accomplished with purely functional code (i.e., no side effects).

To ensure that the minimum constraint is satisfied requires some imperative code (i.e., side effects). For this purpose, I use a predicate with side effects. The predicate accumulates points that meet the minimum constraint criteria and returns true when N points have been accumulated.

Note the running time is unknown because points are randomly generated. With N = 100, A = 1.0, and B = 30.0, the test code runs quickly. I tried values of 10 and 20 for B and didn't wait for it to end. If you want a tighter cluster of points you will probably need to speed up this code or start looking at linear solvers.

public class RandomPoints {
    /**
     * The stop rule is a predicate implementation with side effects. Not sure
     * about the wisdom of this approach. The class does not support concurrent
     * modification.
     * 
     * @author jgmorris
     *
     */
    private class StopRule implements Predicate<Pair<Double, Double>> {
        private final int N;
        private final List<Pair<Double, Double>> points;

        public StopRule(int N, List<Pair<Double, Double>> points) {
            this.N = N;
            this.points = points;
        }

        @Override
        public boolean test(Pair<Double, Double> t) {
            // Brute force test. A hash based test would work a lot better.
            for (int i = 0; i < points.size(); ++i) {
                if (distance(t, points.get(i)) < dL) {
                    // List size unchanged, continue
                    return false;
                }
            }
            points.add(t);
            return points.size() >= N;
        }

    }

    private final double dL;
    private final double dH;
    private final double maxRadius;
    private final Random r;

    public RandomPoints(double dL, double dH) {
        this.dL = dL;
        this.dH = dH;
        this.maxRadius = dH / 2;
        r = new Random();
    }

    public List<Pair<Double, Double>> generate(int N) {
        List<Pair<Double, Double>> points = new ArrayList<>();
        StopRule pred = new StopRule(N, points);

        new Random()
                // Generate a uniform distribution of doubles between 0.0 and
                // 1.0
                .doubles()
                // Transform primitive double into a Double
                .boxed()
                // Transform to a number between 0.0 and 2&piv;
                .map(u -> u * 2 * Math.PI)
                // Generate a random point
                .map(theta -> randomPoint(theta))
                // Add point to points if it meets minimum distance criteria.
                // Stop when enough points are gathered.
                .anyMatch(p -> pred.test(p));

        return points;
    }

    private final Pair<Double, Double> randomPoint(double theta) {
        double x = Math.cos(theta);
        double y = Math.sin(theta);
        double radius = randRadius();
        return Pair.of(radius * x, radius * y);
    }

    private double randRadius() {
        return maxRadius * (r.nextDouble() - 0.5);
    }

    public static void main(String[] args) {
        RandomPoints rp = new RandomPoints(1.0, 30.0);
        List<Pair<Double, Double>> points = rp.generate(100);

        for (int i = 0; i < points.size(); ++i) {
            for (int j = 1; j < points.size() - 1; ++j) {
                if (i == j) {
                    continue;
                }

                double distance = distance(points.get(i), points.get(j));

                if (distance < 1.0 || distance > 30.0) {
                    System.out.println("oops");
                }
            }
        }
    }

    private static double distance(Pair<Double, Double> p1, Pair<Double, Double> p2) {
        return Math.sqrt(Math.pow(p1.getLeft() - p2.getLeft(), 2.0) + Math.pow(p1.getRight() - p2.getRight(), 2.0));
    }

}