4
\$\begingroup\$

I have written an implementation of 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.

Here is my implementation of it.

First I have a class that I used to generate random values or pick - up values randomly from an array

public  class Randomizer {

    private static Random randomHelper = new Random();

    public static Random getHelper() {
        return randomHelper;
    }

    private Randomizer() {

    }

    public static Object oneOf(Object...objects) {

        if (null == objects) {          
            return null;            
        } else {
            return (objects[randomHelper.nextInt(objects.length)]);
        }

    }
}

Second I have a PaintPanel that I use to draw a bunch of points.

class PaintPanel extends JPanel {   
/**
 * 
 */
    private static final long serialVersionUID = 5614021935627523089L;
    private List<Point> pointsToDraw;

    public PaintPanel(List<Point> pointsToDraw) {
        this.pointsToDraw = pointsToDraw;
        this.setBackground(Color.BLACK);
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        if (null== pointsToDraw) {
            return;
        }

        for (Point p: pointsToDraw) {

            g.setColor(Color.WHITE);
            g.drawArc(
                    (int)p.getX(), 
                    (int)p.getY(), 
                    5, 5, 0,(int) (2*Math.PI * 180));   
        }

    }
}

Third, I have a class that implements the algorithms, computes all the points and send them to the panel to be drawn.

public class MitchellBestCandidateIV extends JFrame {

    /**
     * 
     */
    private static final long serialVersionUID = -7874344109745141056L;
    private static final int SCREEN_WIDTH = 420;
    private static final int SCREEN_HEIGHT = 320;
    private static final int MAX_CANDIDATES_AT_TIME = 10;
    private static final int MAX_NUMBER_OF_POINTS = 1000;

    private List<Point> mitchellPoints = new ArrayList<Point>();
    private Point currentPoint;
    private int currentPointIndex =0;

    private Point[] candidatesBunch = new Point[MAX_CANDIDATES_AT_TIME];

    public MitchellBestCandidateIV() {

        this.setTitle("Mitchell's best candidate algorithm");
        computeBestPoints();
        initComponents();
    }


    private void computeBestPoints() {

        do {

            currentPoint = getRandomPoint();
            mitchellPoints.add(currentPoint);
            currentPointIndex++;

            setCandidates();
            Point bestCandidate =  pickUpCandidate();
            mitchellPoints.add(bestCandidate);
            currentPoint = bestCandidate;
            currentPointIndex++;

        } while (currentPointIndex <MAX_NUMBER_OF_POINTS);

    }


    private Point pickUpCandidate() {

        Map<Point, Double> candidatesMinimalDistance = new HashMap<Point,     Double>();
        for (Point candidate:candidatesBunch ) {
            double minimalDistanceToCloud =     minimalDistanceFromCloudToCandidate(candidate);
            candidatesMinimalDistance.put(candidate,     Double.valueOf(minimalDistanceToCloud));
        }

        Point bestCandidate = getFarthestPoint(candidatesMinimalDistance);
        return bestCandidate;       
    }


    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));  
    }

    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);

    }

    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {

            public void run() {
                new MitchellBestCandidateIV().setVisible(true);

            }});
    }

    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);
    }


    public Point getFarthestPoint(Map<Point, Double> pointsMinimalDistances)          {
        Point result = null;
        double maxDistance = 0.0D;
        for (Point p: pointsMinimalDistances.keySet()) {
            if (maxDistance < pointsMinimalDistances.get(p)) {
                result = p;
                maxDistance = pointsMinimalDistances.get(p);
            }
        }

        return result;
    }

    public double minimalDistanceFromCloudToCandidate(Point candidate) {
        double minimalDistance = 0.0D;

        for (Point p: mitchellPoints) {
            double d = distanceBetween(candidate,  p);
            if (minimalDistance == 0.0D || d < minimalDistance) {
                minimalDistance = d;
            }
        }

        return minimalDistance;
    }
}

Here is an image illustrating the kind of results.

Mitchell's best candidate

Is my implementation of Mitchell's best candidate algorithm correct? Are there any other approaches to its implementation that would make it faster, so I can generate a greater amount of points without it becoming too slow?

\$\endgroup\$
2
\$\begingroup\$

Bug

I only scanned your code briefly, but it looks to me like this code that is in your main loop:

        currentPoint = getRandomPoint();
        mitchellPoints.add(currentPoint);
        currentPointIndex++;

should be outside the loop. Otherwise you are adding one completely random point along with one Mitchell point on every iteration. I think that code was only meant to generate the first point.

Unnecessary Hashing

One other thing I noticed is that you used a HashMap to store your minimal distances. You could instead just make an array of doubles of the same length as your array of points. It would be faster because it would eliminate the need for hashing and comparing of keys (all your keys are unique).

\$\endgroup\$
  • \$\begingroup\$ thank you. I will try your suggestions and let you know how it turns out. \$\endgroup\$ – alainlompo May 4 '15 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.