<commit_before>"use strict";

var manhattanDistanceN = require('mathp/functions/manhattanDistanceN'),
    chebyshevDistanceN = require('mathp/functions/chebyshevDistanceN'),
    euclideanDistanceN = require('mathp/functions/euclideanDistanceN'),
    zeros = require('zeros'),
    moore = require('moore'),
    sphereRandom = require('sphere-random');

/**
 *
 * @param shape
 * @param minDistance
 * @param maxTries
 * @param rng
 * @constructor
 */
var Poisson = function (shape, minDistance, maxTries, rng) {
    this.shape = shape;
    this.minDistance = minDistance;
    this.cellSize = minDistance / Math.sqrt(shape.length);
    this.maxTries = maxTries || 30;
    this.rng = rng || Math.random;
    this.randomDistAmount = 1;

    this.distanceFunction = euclideanDistanceN;
    //this.distanceFunction = manhattanDistanceN; //FIXME does not work correctly, why ?

    this.neighbourhood = moore(2, this.shape.length);
    var origin = [];
    for (var dimension = 0; dimension < this.shape.length; dimension++) {
        origin.push(0);
    }
    this.neighbourhood.push(origin);

    this.currentPoint = null;
    this.processList = [];
    this.samplePoints = [];

    /* multidimension grid thing */
    this.gridShape = [];

    for (var i = 0; i < shape.length; i++) {
        this.gridShape.push(Math.ceil(shape[i] / this.cellSize));
    }
    //console.log(this.gridShape);
    this.grid = zeros(this.gridShape, 'uint32'); //first float is a flag for point presence
};

/**
 * Add a totally random point in the grid
 * @returns {*} The point added to the grid
 */
Poisson.prototype.addRandomPoint = function () {
    var point = new Array(this.shape.length);

    for (var i = 0; i < this.shape.length; i++) {
        point[i] = this.rng() * this.shape[i];
    }

    return this.addPoint(point);
};

/**
 * Add a given point to the grid
 * @param {array} point Point
 * @returns {*} The point added to the grid
 * @protected
 */
Poisson.prototype.addPoint = function (point) {
    this.processList.push(point);
    this.samplePoints.push(point);

    var internalArrayIndex = 0,
        stride = this.grid.stride,
        dimension,
        currentDimensionValue;

    for (dimension = 0; dimension < this.shape.length; dimension++) {
        internalArrayIndex += ((point[dimension] / this.cellSize) | 0) * stride[dimension];
    }

    this.grid.data[internalArrayIndex] = this.samplePoints.length; // store the point reference

    return point;
};

/**
 * Check whether a given is in the neighbourhood of existing points
 * @param {array} point Point
 * @param {number} minDist Minimum distance
 * @returns {boolean} Whether the point is in the neighbourhood of another point
 * @protected
 */
Poisson.prototype.inNeighbourhood = function (point, minDist) {

    /* */
    var dimensionNumber = this.shape.length,
        stride = this.grid.stride,
        neighbourIndex,
        internalArrayIndex,
        dimension,
        currentDimensionValue,
        existingPoint;

    //console.log('- - -');

    for (neighbourIndex = 0; neighbourIndex < this.neighbourhood.length; neighbourIndex++) {
        internalArrayIndex = 0;

        for (dimension = 0; dimension < dimensionNumber; dimension++) {
            currentDimensionValue = ((point[dimension] / this.cellSize) | 0) + this.neighbourhood[neighbourIndex][dimension];

            //console.log(point[dimension], currentDimensionValue, this.gridShape[dimension]);
            //console.log((point[dimension] / this.cellSize) | 0, this.neighbourhood[neighbourIndex][dimension], currentDimensionValue);

            if (currentDimensionValue >= 0 && currentDimensionValue < this.gridShape[dimension]) {
                internalArrayIndex += currentDimensionValue * stride[dimension];
            }
        }

        if (this.grid.data[internalArrayIndex] !== 0) {
            existingPoint = this.samplePoints[this.grid.data[internalArrayIndex] - 1];
            //console.log(internalArrayIndex, this.grid.data[internalArrayIndex], this.samplePoints.length, existingPoint);

            //console.log(point, existingPoint, this.distanceFunction(point, existingPoint), this.distanceFunction(point, existingPoint) < minDist);
            if (this.distanceFunction(point, existingPoint) < minDist) {
                return true;
            }
        }
    }



    /*/
    var i = (point[0] / this.cellSize) | 0,
        j = (point[1] / this.cellSize) | 0;

    var startI = Math.max(i - 2, 0),
        endI = Math.min(i + 2, this.gridWidth);

    var startJ = Math.max(j - 2, 0),
        endJ = Math.min(j + 2, this.gridHeight);

    for (i = startI; i <= endI; i++) {
        for (j = startJ; j <= endJ; j++) {
            var existingPoint = this.grid[j * this.gridWidth + i];

            if (existingPoint && this.distanceFunction(point, existingPoint) < minDist) {
                return true;
            }
        }
    }
    /* */

    return false;
};

// http://devmag.org.za/2009/05/03/poisson-disk-sampling/
// http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

/**
 * Try to place a new point in the grid, returns null if it wasn't possible
 * @returns {array|null} The added point or null
 */
Poisson.prototype.next = function () {
    var tries,
        angle,
        distance,
        currentPoint,
        newPoint,
        inShape;

    while (this.processList.length > 0) {
        if (this.currentPoint === null) {
            this.currentPoint = this.processList.shift(); //might want to extract randomly
        }

        currentPoint = this.currentPoint;

        for (tries = 0; tries < this.maxTries; tries++) {
            inShape = true;
            newPoint = sphereRandom(this.shape.length);
            distance = this.minDistance * (1 + this.rng());

            for (var i = 0; inShape && i < this.shape.length; i++) {
                newPoint[i] = currentPoint[i] + newPoint[i] * distance;
                inShape = (newPoint[i] >= 0 && newPoint[i] <= this.shape[i] - 1)
            }

            if (inShape && !this.inNeighbourhood(newPoint, this.minDistance)) {
                return this.addPoint(newPoint);
            }
        }<commit_msg>optimize the generation of new point in 2 dimensions (revert to simple random angle selection in this case)<commit_after>"use strict";

var manhattanDistanceN = require('mathp/functions/manhattanDistanceN'),
    chebyshevDistanceN = require('mathp/functions/chebyshevDistanceN'),
    euclideanDistanceN = require('mathp/functions/euclideanDistanceN'),
    zeros = require('zeros'),
    moore = require('moore'),
    sphereRandom = require('sphere-random');

/**
 *
 * @param shape
 * @param minDistance
 * @param maxTries
 * @param rng
 * @constructor
 */
var Poisson = function (shape, minDistance, maxTries, rng) {
    this.shape = shape;
    this.dimension = this.shape.length;
    this.minDistance = minDistance;
    this.cellSize = minDistance / Math.sqrt(this.dimension);
    this.maxTries = maxTries || 30;
    this.rng = rng || Math.random;
    this.randomDistAmount = 1;

    this.distanceFunction = euclideanDistanceN;
    //this.distanceFunction = manhattanDistanceN; //FIXME does not work correctly, why ?

    this.neighbourhood = moore(2, this.dimension);
    var origin = [];
    for (var dimension = 0; dimension < this.dimension; dimension++) {
        origin.push(0);
    }
    this.neighbourhood.push(origin);

    this.currentPoint = null;
    this.processList = [];
    this.samplePoints = [];

    /* multidimension grid thing */
    this.gridShape = [];

    for (var i = 0; i < this.dimension; i++) {
        this.gridShape.push(Math.ceil(shape[i] / this.cellSize));
    }
    //console.log(this.gridShape);
    this.grid = zeros(this.gridShape, 'uint32'); //first float is a flag for point presence
};

/**
 * Add a totally random point in the grid
 * @returns {*} The point added to the grid
 */
Poisson.prototype.addRandomPoint = function () {
    var point = new Array(this.dimension);

    for (var i = 0; i < this.dimension; i++) {
        point[i] = this.rng() * this.shape[i];
    }

    return this.addPoint(point);
};

/**
 * Add a given point to the grid
 * @param {array} point Point
 * @returns {*} The point added to the grid
 * @protected
 */
Poisson.prototype.addPoint = function (point) {
    this.processList.push(point);
    this.samplePoints.push(point);

    var internalArrayIndex = 0,
        stride = this.grid.stride,
        dimension,
        currentDimensionValue;

    for (dimension = 0; dimension < this.dimension; dimension++) {
        internalArrayIndex += ((point[dimension] / this.cellSize) | 0) * stride[dimension];
    }

    this.grid.data[internalArrayIndex] = this.samplePoints.length; // store the point reference

    return point;
};

/**
 * Check whether a given is in the neighbourhood of existing points
 * @param {array} point Point
 * @param {number} minDist Minimum distance
 * @returns {boolean} Whether the point is in the neighbourhood of another point
 * @protected
 */
Poisson.prototype.inNeighbourhood = function (point) {
    var dimensionNumber = this.dimension,
        stride = this.grid.stride,
        neighbourIndex,
        internalArrayIndex,
        dimension,
        currentDimensionValue,
        existingPoint;

    //console.log('- - -');

    for (neighbourIndex = 0; neighbourIndex < this.neighbourhood.length; neighbourIndex++) {
        internalArrayIndex = 0;

        for (dimension = 0; dimension < dimensionNumber; dimension++) {
            currentDimensionValue = ((point[dimension] / this.cellSize) | 0) + this.neighbourhood[neighbourIndex][dimension];

            //console.log(point[dimension], currentDimensionValue, this.gridShape[dimension]);
            //console.log((point[dimension] / this.cellSize) | 0, this.neighbourhood[neighbourIndex][dimension], currentDimensionValue);

            if (currentDimensionValue >= 0 && currentDimensionValue < this.gridShape[dimension]) {
                internalArrayIndex += currentDimensionValue * stride[dimension];
            }
        }

        if (this.grid.data[internalArrayIndex] !== 0) {
            existingPoint = this.samplePoints[this.grid.data[internalArrayIndex] - 1];
            //console.log(internalArrayIndex, this.grid.data[internalArrayIndex], this.samplePoints.length, existingPoint);

            //console.log(point, existingPoint, this.distanceFunction(point, existingPoint), this.distanceFunction(point, existingPoint) < minDist);
            if (this.distanceFunction(point, existingPoint) < this.minDistance) {
                return true;
            }
        }
    }

    return false;
};

// http://devmag.org.za/2009/05/03/poisson-disk-sampling/
// http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

/**
 * Try to place a new point in the grid, returns null if it wasn't possible
 * @returns {array|null} The added point or null
 */
Poisson.prototype.next = function () {
    var tries,
        angle,
        distance,
        currentPoint,
        newPoint,
        inShape;

    while (this.processList.length > 0) {
        if (this.currentPoint === null) {
            this.currentPoint = this.processList.shift(); //might want to extract randomly
        }

        currentPoint = this.currentPoint;

        for (tries = 0; tries < this.maxTries; tries++) {
            inShape = true;
            distance = this.minDistance * (1 + this.rng());

            if (this.dimension === 2) {
                angle = this.rng() * Math.PI * 2;
                newPoint = [
                    Math.cos(angle),
                    Math.sin(angle)
                ]; // avoiding creating an array at each tries would be nice but would require changing the sphereRandom API
            } else {
                newPoint = sphereRandom(this.dimension);
            }

            for (var i = 0; inShape && i < this.dimension; i++) {
                newPoint[i] = currentPoint[i] + newPoint[i] * distance;
                inShape = (newPoint[i] >= 0 && newPoint[i] <= this.shape[i] - 1)
            }

            if (inShape && !this.inNeighbourhood(newPoint)) {
                return this.addPoint(newPoint);
            }
        }
{'fraction_non_alphanumeric': 0.12816947488957958, 'fraction_numerical': 0.0071159823327335186, 'mean_word_length': 2.585630498533724, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6060490', 'n_tokens_mistral': 3710, 'n_tokens_neox': 3504, 'n_words': 848}