package csa.tiletools.worldgen.mapgen;

import csa.tiletools.worldgen.mapgen.processing.CSAProcessing;
import csa.tiletools.worldgen.mapgen.processing.CSAVector;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Vector;


public class PoissonDistribution
{
  /** From "Fast Poisson Disk Sampling in Arbitrary Dimensions"
  * by Robert Bridson
  * http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf
  **/

  PoissonDistribution()
  {
    _points = new Vector<CSAVector>();
  }

  Vector<CSAVector> getPoints() { return _points; }

  Vector<CSAVector> generate(float xmin, float ymin, float xmax, float ymax, float minDist, int rejectionLimit)
  {
    _xmin = xmin; _xmax = xmax; _ymin = ymin; _ymax = ymax;
    _cellSize = (float) (minDist / CSAProcessing.sqrt(2));
    _gridWidth = (int) CSAProcessing.ceil((xmax-xmin) / _cellSize);
    _gridHeight = (int) CSAProcessing.ceil((ymax-ymin) / _cellSize);
    int s = _gridWidth * _gridHeight;
    _grid = new ArrayList<Vector<CSAVector>>();
    for(int i=0; i<s; i++) {
          _grid.add(new Vector<CSAVector>());
      }

    _points.clear();
    LinkedList<CSAVector> processList = new LinkedList<CSAVector>();

    CSAVector p = new CSAVector(CSAProcessing.random(_xmin, _xmax), CSAProcessing.random(_ymin, _ymax));
    processList.add(p);
    _points.add(p);
    addToGrid(p);

    while(processList.size() > 0)
    {
      int i = (int) CSAProcessing.floor(CSAProcessing.random(processList.size()));
      p = processList.get(i);
      processList.remove(i);
      for(i=0; i<rejectionLimit; i++)
      {
        CSAVector n = createRandomPointAround(p, minDist, minDist*2);
        if(insideBoundaries(n) && testGrid(n, minDist)) {
          processList.add(n);
          _points.add(n);
          addToGrid(n);
        }
      }
    }

    return _points;
  }

  boolean insideBoundaries(CSAVector p)
  {
    return (p.x >= _xmin && p.x < _xmax && p.y >= _ymin && p.y < _ymax);
  }

  CSAVector createRandomPointAround(CSAVector p, float minDist, float maxDist)
  {
    float a = CSAProcessing.random((float)(2*CSAProcessing.PI));
    float r = CSAProcessing.random(minDist, maxDist);
    return new CSAVector((float)(p.x + r * CSAProcessing.cos(a)), (float)(p.y + r * CSAProcessing.sin(a)));
  }

  // return true if there are no points inside the circle of minDist radius around p
  boolean testGrid(CSAVector p, float minDist)
  {
    int minX = (int) CSAProcessing.floor(CSAProcessing.max(0, (p.x - minDist - _xmin) / _cellSize));
    int maxX = (int) CSAProcessing.ceil(CSAProcessing.min(_gridWidth - 1, (p.x + minDist - _xmin) / _cellSize));
    int minY = (int) CSAProcessing.floor(CSAProcessing.max(0, (p.y - minDist - _ymin) / _cellSize));
    int maxY = (int) CSAProcessing.ceil(CSAProcessing.min(_gridHeight - 1, (p.y + minDist - _ymin) / _cellSize));

    for(int y=minY; y<=maxY; y++) {
      for(int x=minX; x<=maxX; x++) {
        Vector<CSAVector> cell = _grid.get(y * _gridWidth + x);
        for(CSAVector t : cell)
        {
              if( CSAProcessing.dist(p.x, p.y, t.x, t.y) <= minDist)
                return false;
        }
      }
    }
    return true;
  }

  void addToGrid(CSAVector p)
  {
    _grid.get(index(p.x, p.y)).add(p);
  }

  protected int index(float x, float y)
  {
    int gx = (int) CSAProcessing.floor((x - _xmin) / _cellSize);
    int gy = (int) CSAProcessing.floor((y - _ymin) / _cellSize);
    return gy * _gridWidth + gx;
  }

  private ArrayList<Vector<CSAVector>> _grid;
  private float _cellSize;
  private int _gridWidth, _gridHeight;
  private float _xmin, _xmax, _ymin, _ymax;
  private Vector<CSAVector> _points;
}
