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 computeBestPoints
computes 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.