UniformPoissonDiskSampler.java

package com.cardinalblue.android.piccollage.math;

import android.graphics.Point;
import android.graphics.PointF;
import android.graphics.RectF;

import java.util.ArrayList;
import java.util.List;

/**
 * An algorithm to populate large worlds with objects is to simply place objects
 * on a grid, or randomly.
 * <p/>
 * The basic idea is:
 * 1) Generate points around existing points and check whether they can be added
 * so that they won't disturb the minimum distance requirement.
 * 2) A grid is used to perform fast lookups of points.
 * 3) Two lists keep track of points that being generated, and those that needs
 * processing.
 * <p/>
 * Author: boy@cardinalblue.com, prada@cardinalblue.com
 * <p/>
 * Reference:
 * - http://bl.ocks.org/mbostock/19168c663618b7f07158
 * - http://devmag.org.za/2009/05/03/poisson-disk-sampling/
 */
public class UniformPoissonDiskSampler {
    /**
     * Maximum number of samples before rejection
     */
    private final static int MAX_TRY_TIMES = 30;

    /**
     * Policy for generating the initial point.
     */
    public final static int RANDOM_INIT_POINT = 0x1001;
    public final static int CENTER_INIT_POINT = 0x1002;
    public final static int SPECIFY_INIT_POINT = 0x1003;

    private int mInitPointPolicy = RANDOM_INIT_POINT;

    private PointF mInitPoint;
    private RectF mCanvasRect;
    private double mMinDist;
    private double mCellSize;
    private int mGridWidth;
    private int mGridHeight;

    /**
     * List of points that being processed.
     */
    private List<PointF> mProcessList;
    /**
     * List of points that being generated.
     */
    private List<PointF> mPointList;
    /**
     * Grid is used to perform fast lookups of points.
     */
    private final PointF mGridList[][];

    /**
     * @param canvasRect The world that objects populated.
     * @param minDist    The minimum distance that points must guarantee to have each other.
     * @param initPointPolicy   The policy to determine the initial point.
     */
    public UniformPoissonDiskSampler(RectF canvasRect, double minDist, int initPointPolicy) {
        if (canvasRect == null) {
            throw new IllegalArgumentException("The given canvas rect is null.");
        }
        if (canvasRect.width() <= minDist || canvasRect.height() <= minDist) {
            throw new IllegalArgumentException(
                "The given minimum distance is bigger than width/height of given canvas size.");
        }
        if (initPointPolicy < RANDOM_INIT_POINT || initPointPolicy > SPECIFY_INIT_POINT) {
            throw new IllegalArgumentException("The given policy is invalid.");
        }

        mCanvasRect = canvasRect;
        mMinDist = minDist;
        mCellSize = minDist / Math.sqrt(2);
        mGridWidth = (int) (mCanvasRect.width() / mCellSize + 1);
        mGridHeight = (int) (mCanvasRect.height() / mCellSize + 1);
        mProcessList = new ArrayList<>();
        mPointList = new ArrayList<>();
        mGridList = new PointF[mGridWidth][mGridHeight];

        // Empty grids.
        for (int i = 0; i < mGridWidth; ++i) {
            for (int j = 0; j < mGridHeight; ++j) {
                mGridList[i][j] = null;
            }
        }

        // TODO: Take policy into account.
        mInitPointPolicy = initPointPolicy;
    }

    /**
     * @param initPoint Specify an initial point.
     */
    public UniformPoissonDiskSampler(RectF canvasRect, double minDist, PointF initPoint) {
        this(canvasRect, minDist, SPECIFY_INIT_POINT);

        if (initPoint == null) {
            throw new IllegalArgumentException("Given init point is null.");
        }
        if (initPoint.x < mCanvasRect.left || initPoint.x > mCanvasRect.right ||
            initPoint.y < mCanvasRect.top || initPoint.y > mCanvasRect.bottom) {
            throw new IllegalArgumentException("Init point is outside the canvas boundary.");
        }

        mInitPoint = new PointF(initPoint.x, initPoint.y);
    }

    /**
     * Generate a candidate point.
     */
    public PointF sample() {
        // Generate first point.
        if (mPointList.size() == 0) {
            PointF firstPoint;

            switch (mInitPointPolicy) {
                case CENTER_INIT_POINT: {
                    double xr = mCanvasRect.centerX() + mCellSize * (2 * Math.random() - 1);
                    double yr = mCanvasRect.centerY() + mCellSize * (2 * Math.random() - 1);

                    firstPoint = new PointF((float) xr, (float) yr);
                    break;
                }
                case SPECIFY_INIT_POINT: {
                    firstPoint = mInitPoint;
                    break;
                }
                case RANDOM_INIT_POINT:
                default: {
                    int gridX = (int) Math.floor(mGridWidth * Math.random());
                    int gridY = (int) Math.floor(mGridHeight * Math.random());
                    double xr = gridX * mCellSize + mCellSize * Math.random();
                    double yr = gridY * mCellSize + mCellSize * Math.random();

                    firstPoint = new PointF((float) xr, (float) yr);
                }
            }

            Point gridIndex = pointToGrid(firstPoint);

            mGridList[gridIndex.x][gridIndex.y] = firstPoint;
            mProcessList.add(firstPoint);
            mPointList.add(firstPoint);

            return firstPoint;
        }

        // Find the candidate point around the points in active list.
        while (!mProcessList.isEmpty()) {
            int centerIndex = (int) Math.floor(mProcessList.size() * Math.random());
            PointF center = mProcessList.get(centerIndex);

            // Find valid new point.
            for (int i = 0; i < MAX_TRY_TIMES; ++i) {
                // TODO: Can Math.random() return non-duplicate result?
                double radius = mMinDist + mMinDist * Math.random();
                double angle = 2 * Math.PI * Math.random();
                double newX = radius * Math.sin(angle);
                double newY = radius * Math.cos(angle);
                PointF newPoint = new PointF(center.x + (float) newX,
                                             center.y + (float) newY);
                Point gridIndex = pointToGrid(newPoint);

                if (mCanvasRect.left <= newPoint.x && newPoint.x <= mCanvasRect.right &&
                    mCanvasRect.top <= newPoint.y && newPoint.y <= mCanvasRect.bottom) {
                    boolean isOk = true;

                    // +---+---+---+---+---+---+---+
                    // |   |   |   |   |   |   |   |
                    // +---+---+---+---+---+---+---+
                    // |   |   |///|///|///|   |   |
                    // +---+---+---+---+---+---+---+
                    // |   |///|///|///|///|///|   |
                    // +---+---+---+---+---+---+---+
                    // |   |///|///| C |///|///|   |
                    // +---+---+---+---+---+---+---+
                    // |   |///|///|///|///|///|   |
                    // +---+---+---+---+---+---+---+
                    // |   |   |///|///|///|   |   |
                    // +---+---+---+---+---+---+---+
                    // |   |   |   |   |   |   |   |
                    // +---+---+---+---+---+---+---+
                    // Check the points in the region (if any) around a center point, C. Make sure they don't
                    // disturb the minimum distance requirement.
                    for (int j = Math.max(0, gridIndex.x - 2); j < Math.min(mGridWidth, gridIndex.x + 3); ++j) {
                        for (int k = Math.max(0, gridIndex.y - 2); k < Math.min(mGridHeight, gridIndex.y + 3); ++k) {
                            PointF gridPoint = mGridList[j][k];

                            if (gridPoint != null &&
                                distanceBetween(gridPoint, newPoint) < mMinDist) {
                                isOk = false;
                            }
                        }

                        if (!isOk) break;
                    }

                    if (isOk) {
                        mGridList[gridIndex.x][gridIndex.y] = newPoint;

                        mProcessList.add(newPoint);
                        mPointList.add(newPoint);

                        return newPoint;
                    }
                }
            }

            mProcessList.remove(centerIndex);
        }

        return null;
    }

    /**
     * Find out all the points populated in the world.
     */
    public List<PointF> sampleAll() {
        for (int i = 0; i < 3; ++i) {
            while (sample() != null) ;
        }

        return mPointList;
    }

    /**
     * Clear the sample result.
     */
    public void clear() {
        mProcessList.clear();
        mPointList.clear();

        // Empty grids.
        for (int i = 0; i < mGridWidth; ++i) {
            for (int j = 0; j < mGridHeight; ++j) {
                mGridList[i][j] = null;
            }
        }
    }

    public static double distanceBetween(PointF pointA, PointF pointB) {
        return Math.sqrt(Math.pow(pointA.x - pointB.x, 2) + Math.pow(pointA.y - pointB.y, 2));
    }

    ///////////////////////////////////////////////////////////////////////////
    // Private ////////////////////////////////////////////////////////////////

    /**
     * Find the position of a given point in the grid.
     *
     * @param pt The given point that being to lookup in the grid list.
     */
    private Point pointToGrid(PointF pt) {
        return new Point((int) ((pt.x - mCanvasRect.left) / mCellSize),
                         (int) ((pt.y - mCanvasRect.top) / mCellSize));
    }
}