Improving Mitchell's best candidate algorithm

Question

I have successfully implemented Mitchell's best candidate algorithm. Mitchell’s best-candidate algorithm generates a new random sample by creating k candidate samples and picking the best of k. Here the “best” sample is defined as the sample that is farthest away from previous samples. The algorithm approximates Poisson-disc sampling, producing a much more natural appearance (better blue noise spectral characteristics) than uniform random sampling.

I am trying to improve it especially in the area of speed. So the first idea that came to my mind was to compare the candidate samples only to the last added element instead of comparing them to the whole previous sample. This would bias Poisson-disc sampling but may produce some interesting results.

Here is the main part of my implementation

public class MitchellBestCandidateII extends JFrame {

    private List<Point> mitchellPoints = new ArrayList<Point>();
    private Point currentPoint;
    private int currentPointIndex =0;
    private boolean isBeginning = true;
    private Point[] candidatesBunch = new Point[MAX_CANDIDATES_AT_TIME];

    public MitchellBestCandidateII() {      
        computeBestPoints();
        initComponents();
    }

The method computeBestPointscomputes the point differently from Mitchell's algorithm in this sense that it compares candidates only to the last added point instead of comparing it to the whole sample.

    private void computeBestPoints() {

        do {
            if (isBeginning) {
                currentPoint = getRandomPoint();
                mitchellPoints.add(currentPoint);
                isBeginning = false;
                currentPointIndex = 0;              
            } 

            setCandidates();
            Point bestCandidate = pickUpCandidateFor(currentPoint);
            mitchellPoints.add(bestCandidate);
            currentPoint = bestCandidate;
            currentPointIndex++;    
        } while (currentPointIndex <MAX_NUMBER_OF_POINTS);

    }

    private Point pickUpCandidateFor(Point p) {
        double biggestDistance = 0.0D;
        Point  result = null;
        for (int i = 0; i < MAX_CANDIDATES_AT_TIME; i++) {

            double d = distanceBetween(p, candidatesBunch[i]);
            if (biggestDistance < d) {
                biggestDistance = d;
                result = candidatesBunch[i];

            }
        }

        return result;
    }

The setCandidates method generates random candidates. Only one of them will end up being part of the sample: the others will be discarded.

    private void setCandidates() {
        for (int i = 0; i < MAX_CANDIDATES_AT_TIME; i++) {
            candidatesBunch[i] = getRandomPoint();
        }
    }


    private Point getRandomPoint() {
        return new Point(Randomizer.getHelper().nextInt(SCREEN_WIDTH),     Randomizer.getHelper().nextInt(SCREEN_HEIGHT));

    }

The initComponents sets up the JFrame and the JPanel and passes the list of points to draw to the JPanel

    private void initComponents() {
        this.setSize(SCREEN_WIDTH,SCREEN_HEIGHT);
        PaintPanel panel = new PaintPanel(mitchellPoints);
        panel.setPreferredSize(new Dimension(SCREEN_WIDTH,SCREEN_HEIGHT));
        this.setContentPane(panel);
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    }

The distanceBetween method computes the distance between two points applying a mathematical formula.

    public double distanceBetween(Point p1, Point p2) {

        double deltaX = p1.getX() - p2.getX();
        double deltaY = p1.getY() - p2.getY();
        double deltaXSquare = Math.pow(deltaX, 2);
        double deltaYSquare = Math.pow(deltaY, 2);

        return Math.sqrt(deltaXSquare + deltaYSquare);

    }

}

Here is an illustration of the execution:

Every run seems to produce the same type of points distribution and as you can see in the pictures above the points seems to be avoiding the central area. I can't understand why it is behaving this way. Can someone help me to understand this behavior? Is there any other approach (or known algorithm) that significantly improve Mitchell's best candidate algorithm? My implementation of Mitchell's best candidate algorithm (not the above code) is under review on Code Review

Thank you for helping.

Answer 1

Every run seems to produce the same type of points distribution and as you can see in the pictures above the points seems to be avoiding the central area. I can't understand why it is behaving this way. Can someone help me to understand this behavior?

As already pointed out in @pens-fan-69 answer, Basically you will end up oscillating between the edges of your space if you base the selection of the new point to add on its distance from the previous one (the exact opposite of the exact opposite of a point is itself).

Is there any other approach (or known algorithm) that significantly improve Mitchell's best candidate algorithm?

For the problem you described, I believe a data structure, that is specifically intended to model spatial data in K dimensions and allows fast searching in the occupied space for a nearest neighbor to a given new coordinate, would make sense. The K-D Tree is such a structure:

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

Generally, when constructing a K-D Tree, this is done using a set of (sorted) data points, and recursively dividing (partitioning) the search space along one of the dimensional axes using the median value among the remaining points along that axis.

I have added a very simple and naive implementation, that contains only those operations that are used in your problem, and performs no tree rebalancing for inserts. Due to the specific nature of the points being inserted (largest distance from existing points), this seems to work pretty well, see image below (evaluating 500, 10 candidates per round, 5000, 1000 points total respectively for the left and right image).

It is in C#, because I had some parts already available, but it should be very straightforward to translate this to Java. I omitted the code for the Points class.

// A very naive partial K-D Tree implementation with K = 2 for Points.
public class TwoDTree
{
    private Node _root;

    public void Insert(Point coordinate)
    {
        _root = Node.Insert(coordinate, _root, 0);
    }

    public Point FindNearest(Point to, out double bestDistance)
    {
        bestDistance = double.MaxValue;
        var best = Node.FindNearest(to, _root, 0, null, ref bestDistance);
        return best != null ? best.Coordinate : null;
    }

    public IEnumerable<Point> GetPoints()
    {
        if (_root != null)
            return _root.GetPoints();
        return Enumerable.Empty<Point>();
    }

    private class Node
    {
        private Node _left;
        private Node _right;

        public Node(Point coord)
        {
            Coordinate = coord;
        }

        public readonly Point Coordinate;

        public IEnumerable<Point> GetPoints()
        {
            if (_left != null)
            {
                foreach (var pt in _left.GetPoints())
                    yield return pt;
            }
            yield return Coordinate;

            if (_right != null)
            {
                foreach (var pt in _right.GetPoints())
                    yield return pt;
            }
        }

        // recursive insert (non-balanced).
        public static Node Insert(Point coord, Node root, int level)
        {
            if (root == null)
                return new Node(coord);

            var compareResult = ((level % 2) == 0)
                ? coord.X.CompareTo(root.Coordinate.X)
                : coord.Y.CompareTo(root.Coordinate.Y);

            if (compareResult > 0)
                root._right = Insert(coord, root._right, level + 1);
            else
                root._left = Insert(coord, root._left, level + 1);
            return root;
        }

        public static Node FindNearest(Point coord, Node root, int level, Node best, ref double bestDistance)
        {
            if (root == null)
                return best;

            var axis_dif = ((level % 2) == 0)
                ? coord.X - root.Coordinate.X
                : coord.Y - root.Coordinate.Y;

            // recurse near & maybe far as well
            var near = axis_dif <= 0.0d ? root._left : root._right;
            best = Node.FindNearest(coord, near, level + 1, best, ref bestDistance);
            if (axis_dif * axis_dif < bestDistance)
            {
                var far = axis_dif <= 0.0d ? root._right : root._left;
                best = Node.FindNearest(coord, far, level + 1, best, ref bestDistance);
            }

            // do we beat the old best.
            var dist = root.Coordinate.DistanceTo(coord);
            if (dist < bestDistance)
            {
                bestDistance = dist;
                return root;
            }
            return best;
        }
    }
}

// Mitchell Best Candidate algorithm, using the K-D Tree.
public class MitchellBestCandidate
{
    private const int MaxX = 420;
    private const int MaxY = 320;
    private readonly int _maxCandidates;
    private readonly int _maxPoints;
    private readonly Random _rnd;
    private readonly TwoDTree _tree = new TwoDTree();

    public MitchellBestCandidate(int maxPoints, int maxCandidatesPerRound)
    {
        _maxPoints = maxPoints;
        _maxCandidates = maxCandidatesPerRound;
        _rnd = new Random();
    }

    public IEnumerable<Point> CurrentPoints
    {
        get { return _tree.GetPoints(); }
    }

    public void Generate()
    {
        _tree.Insert(GetRandomPoint(_rnd, MaxX, MaxY));
        for (var i = 1; i < _maxPoints; i++)
        {
            var bestDistance = double.MinValue;
            var bestCandidate = default(Point);
            for (var ci = 0; ci < _maxCandidates; ci++)
            {
                var distance = default(double);
                var candidate = GetRandomPoint(_rnd, MaxX, MaxY);
                var nearest = _tree.FindNearest(candidate, out distance);
                if (distance > bestDistance)
                {
                    bestDistance = distance;
                    bestCandidate = candidate;
                }
            }
            _tree.Insert(bestCandidate);
        }
    }

    private static Point GetRandomPoint(Random rnd, int maxX, int maxY)
    {
        return new Point(rnd.Next(maxX), rnd.Next(maxY));
    }
}