Generates random point inside a given polygon (it can also be a straight line)

RandomPointsInPlane.java

import java.util.Random;
import java.util.Date;

public class RandomPointsInPlane{

		private static final int BATCH_SIZE = 25;
		private static final int MIN_BATCH_SIZE = 5;

		public static long getSeed(){
				return (new Date().getTime() % Integer.MAX_VALUE);
		}

		public static boolean isValidPolygon(Point[] arr){
				if (arr.length < 2) {
						return true;
				}
				int size = arr.length;
				double[] distances = new double[size];
				double sum = 0;
				double slopes1, slopes2;
				slopes1 = Point.slope(arr[0], arr[1]);
				for (int i = 0; i < size; i++) {
						distances[i] = Point.lengthOfSide(arr[i], arr[(i + 1) % size]);
						sum += distances[i];
						if (i < size - 1) {
								slopes2 = Point.slope(arr[(i + 1) % size], arr[(i + 2) % size]);
								if (slopes1 == slopes2) {
										return false;
								}
						}
				}
				for (int i = 0; i < size; i++) {
						if (distances[i] >= sum - distances[i]) {
								return false;
						}
				}
				return true;
		}

		private static Point centroid(Point[] arr){
				/*
					Centroid is average of all the points
				 */
				Point c = new Point();
				int size = arr.length;
				for (Point pt : arr) {
						c.x += pt.x / size;
						c.y += pt.y / size;
				}
				return c;
		}

		/* Formula taken from
		 * https://www.cs.princeton.edu/~funk/tog02.pdf
		 * https://math.stackexchange.com/questions/18686/uniform-random-point-in-triangle
		 */
		private static void randomsInTriangle(Point a, Point b, Point c, Point[] arr, int lo, int hi, Random r){
				/*
					random point P = (1 - sqrt(r1)) * A + sqrt(r1)*(1-r2) * B + sqrt(r1)*r2 * C
					inside a triangle ABC
				 */
				for (int i = lo; i <= hi; i++) {
						double r1 = Math.sqrt(r.nextDouble());
						double r2 = Math.sqrt(r.nextDouble());
						arr[i].x = (1 - r1) * a.x + (1 - r2) * r1 * b.x + r2 * r1 * c.x;
						arr[i].y = (1 - r1) * a.y + (1 - r2) * r1 * b.y + r2 * r1 * c.y;
				}
		}

		private static void randomsInStraightLine(Point[] line, int size, Point[] arr, Random r){
				double slope = Point.slope(line[0], line[1]);
				double diff, x = line[0].x, y = line[0].y, rand;
				/* If slope is negative we keep x same
				   and y ranges between two pints y
				 */
				if (slope == Double.POSITIVE_INFINITY || slope == Double.NEGATIVE_INFINITY) {
						diff = line[1].y - line[0].y;
						for (int i = 0; i < size; i++) {
								rand = diff * r.nextDouble();
								arr[i].x = x;
								arr[i].y = y + rand;
						}
				} else {
						/*
								We calculate a random x coordinate point between
								two x coordinates of given line and then
								use slope to calculate subsequent y coordinate
								slope = 0 case is taken care of automatically
						 */
						diff = line[1].x - line[0].x;
						for (int i = 0; i < size; i++) {
								rand = diff * r.nextDouble();
								arr[i].x = x + rand;
								arr[i].y = y + rand * slope;
						}
				}
		}

		public static Point[] getRandomPoints(Point[] polygon, int size){
				Random rand = new Random(getSeed());
				Point[] data = new Point[size];

				if (polygon.length == 1) {
						/*
							If only one point is given
							then random points in zero dim space is
							that point itself.
				 		*/
						for (int i = 0; i < size; i++) {
								data[i].x = polygon[0].x;
								data[i].y = polygon[0].y;
						}
						return data;
				} else if (polygon.length == 2) {
						/*
							Generate random points in straight line
						 */
						randomsInStraightLine(polygon, size, data, rand);
						return data;
				}
				/* If a polygon has more than equal to 3
				   sides then first verify if it is valid polygon
				 */
				if (!isValidPolygon(polygon)) {
						return null;
				}
				if (polygon.length == 3) {
						/*
							If a triangle is given then centroid is not needed
							calculate points in it
						 */
						randomsInTriangle(polygon[0], polygon[1], polygon[2], data, 0, size - 1, rand);
						return data;
				}
				/*
					If no of sides is greater than 3
					then find points by creating triangles
					using centroid and finding points
					between triangles.
				 */
				Point centroid = centroid(polygon);
				int len = polygon.length;
				int distribution = size / len;
				int batches = distribution / BATCH_SIZE;
				int smallBatchSize = distribution % BATCH_SIZE;
				int lo, hi;
				int done = BATCH_SIZE * len * batches;
				int index;

				/*
					Process in Batches for each of n possible triangles
				 */
				for (int i = 0; i < batches; i++) {
						lo = i * BATCH_SIZE;
						hi = lo + BATCH_SIZE - 1;
						for (int j = 0; j < len; j++) {
								randomsInTriangle(centroid, polygon[i], polygon[(i + 1) % len], data, lo, hi, rand);
						}
						// Randomize by changing seed 
						if (i % 4 == 0) {
								rand.setSeed(getSeed());
						}
				}
				/* Process in small batch sizes
						only if batch size is greater than MIN_BATCH_SIZE
				 */
				if (smallBatchSize > MIN_BATCH_SIZE) {
						for (int i = 0; i < len; i++) {
								lo = done + i * smallBatchSize;
								hi = lo + smallBatchSize - 1;
								randomsInTriangle(centroid, polygon[i], polygon[(i + 1) % len], data, lo, hi, rand);
								// Randomize by changing seed 
								if (i % 4 == 0) {
										rand.setSeed(getSeed());
								}
						}
						done += len * smallBatchSize;
				}

				/*
					Process the remaining by choosing random triangle
					and random batch sizes
				 */
				for (int i = done; i < size; i++) {
						index = rand.nextInt(len);
						lo = i;
						hi = i + rand.nextInt(MIN_BATCH_SIZE);
						if (hi > size - 1) {
								hi = size - 1;
						}
						i = h;
						randomsInTriangle(centroid, polygon[index], polygon[(index + 1) % len], data, i, i, rand);
						// Randomize by changing seed
						if (i % 4 == 0) {
								rand.setSeed(getSeed());
						}
				}

				return data;
		}

		public static class Point{
				double x;
				double y;

				public Point(){
						x = 0.0;
						y = 0.0;
				}

				public Point(double xx, double yy){
						x = xx;
						y = yy;
				}

				/*
					Calculate slopes between two points
				 */
				public static double slope(Point point1, Point point2){
						if (point1.x != point2.x) {
								return (point1.y - point2.y) / (point1.x - point2.x);
						} else {
								return point2.y > point1.y ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY;
						}
				}

				/*
					 Calculates distance between two points
					 named as such because we are dealing with
					 polygons
				 */
				public static double lengthOfSide(Point a, Point b){
						return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
				}
		}
}