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.
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?
