geometryUtils.ts

type Position = [number,number]

/** Return the angle between 2 points in radians relative to the x axis*/
export const points_to_radians = ([[p1lon, p1lat], [p2lon, p2lat]]: [
	Position,
	Position,
]): number => Math.atan2(p2lat - p1lat, p2lon - p1lon);

/** Return the angle between 2 points in degrees relative to the x axis  */
export const points_to_degrees = (points: [Position, Position]): number =>
	points_to_radians(points) * (180 / PI);

/** Return the angle of the midpoint from 3 points in radians relative to the x axis */
export const points_to_radians3 = ([
	[p1lon, p1lat],
	[p2lon, p2lat],
	[p3lon, p3lat],
]: [Position, Position, Position]): number =>
	Math.atan2(p3lat - p1lat, Math.abs(p3lon - p1lon)) -
	Math.atan2(p2lat - p1lat, Math.abs(p2lon - p1lon));

/**
 * Looks nicer than Math.pow(num, 2)
 *
 * @param {number} num the number to square
 * @returns  {number} the square of the provided number
 */
export const sqr = (num: number): number => Math.pow(num, 2);

/**
 * Generates a bezier curve with 3 control points
 */
export const bezier_curve3 = (
	[[p1x, p1y], [p2x, p2y], [p3x, p3y]]: [Position, Position, Position],
	steps: number,
): Position[] => {
	return Array(steps)
		.fill(0)
		.map((_, i) => {
			const t = (1 / steps) * i;
			const x = sqr(1 - t) * p1x + 2 * (1 - t) * t * p2x + sqr(t) * p3x;
			const y = sqr(1 - t) * p1y + 2 * (1 - t) * t * p2y + sqr(t) * p3y;
			return [x, y];
		});
};

/** Calculate a vertex with a given distance and angle from a point */
export const point_to_vertex = (
	[lng, lat]: Position,
	width: number,
	sign: 1 | -1,
	angle: number,
): Position => [
	lng + width * Math.cos(angle + (sign * PI) / 2),
	lat + width * Math.sin(angle + (sign * PI) / 2),
];

/** Return a curve centered on a point */
export const arc_curve = (
	[cx, cy]: Position,
	r: number,
	steps: number,
	tA = 0,
	tB: number = 2 * Math.PI,
): Position[] => {
	const res: Position[] = [];
	const arcLength = tB - tA;
	const increment = arcLength / steps;
	for (let i = tA; i <= tB; i += increment) {
		const t = i;
		const x = cx + r * Math.cos(t);
		const y = cy + r * Math.sin(t);
		res.push([x, y]);
	}
	return res;
};
/** Return the center point between two points */
export const points_center = ([[p1x, p1y], [p2x, p2y]]: [
	Position,
	Position,
]): Position => {
	const x = p1x + (p2x - p1x) / 2;
	const y = p1y + (p2y - p1y) / 2;
	return [x, y];
};

/** Return a curve between two points */
export const arc_curve_points = (
	points: [Position, Position],
	r: number,
	steps: number,
): Position[] => {
	const center = points_center(points);
	const angle = points_to_radians(points);
	return arc_curve(center, r, steps, angle, angle + Math.PI);
};

/** Return the intersection point of two lines */
export const line_intersect = (
	[x1, y1]: Position,
	[x2, y2]: Position,
	[x3, y3]: Position,
	[x4, y4]: Position,
): { x: number; y: number } | null => {
	const denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
	if (denom === 0) {
		return null;
	}
	const ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
	// const ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
	return {
		x: x1 + ua * (x2 - x1),
		y: y1 + ua * (y2 - y1),
	};
};

export const PI = Math.PI;

/**
 * This function transforms a collection of points into a polygon that "wraps" the given points.
 * The algorithm is as follows:
 *  1. if there is one point in the given array draw a circle
 *  2. else for each point:
 * 		1. if it's the first or last point draw a curve to close out the polygon
 * 		2. else
 * 			1. compute the angles between the previous, current and proceeding point
 * 			2. compute the tangent vertices for the previous, current and proceeding points
 * 			3. compute the angle between the three points and the x axis,
 * 			4. check the "direction" that the shape is facing and determine which vertices are overlapping
 * 			5. calculate a curve for the un overlapping vertices
 * 			6. calculate the intersection overlapping vertices
 *
 *  Note:
 *  The "bottom" and "top" paths of the polygon are calculated and inserted simultaneously,
 * 	the "top" path is reversed at the end and appended to the result to make a contiguous path.
 *
 *  Note:
 *  The "direction" of the points is important for traversal, because of this, data is sorted
 *  in ascending order for the x value of each point.
 *
 * @param data {Position[]} - The points around which to create the convex hull
 * @param r - {number} the radius of the hull
 * @param steps - the number of lines used to make a full circle
 * @returns {Position[]} - A collection of points that represent our convexHull path
 */
export const pathConvexHull = (
	data: Position[],
	r: number,
	steps: number,
): Position[] => {
	// To A
	const path = data.sort(([x1], [x2]) => (x1 < x2 ? -1 : 1));

	const vUp: Position[] = [],
		vDown: Position[] = [];

	//Only one point in our path generate a circle
	if (path.length === 1) {
		return arc_curve(path[0], r, steps);
	}

	for (let i = 0; i < path.length; i++) {
		const isLast = i === path.length - 1,
			isFirst = i === 0;

		//The first point, draw an arc
		if (isFirst) {
			const p1 = path[i];
			const p2 = path[i + 1];

			const angle1 = points_to_radians([p1, p2]);

			const v1: Position = point_to_vertex(p1, r, -1, angle1);
			const v5: Position = point_to_vertex(p1, r, 1, angle1);

			//Save the first point to close the loop
			vUp.push(v5);

			//Create the first arc
			vDown.push(...arc_curve_points([v1, v5], r, steps));
		}

		//The last point, draw an arc
		if (isLast) {
			const p1 = path[i - 1];
			const p2 = path[i];

			const angle2 = points_to_radians([p1, p2]);
			const v4: Position = point_to_vertex(p2, r, -1, angle2);
			const v8: Position = point_to_vertex(p2, r, 1, angle2);
			//Create the last arc
			vUp.push(...arc_curve_points([v8, v4], r, steps).reverse());
		}

		if (!isFirst && !isLast) {
			const p1 = path[i - 1];
			const p2 = path[i];
			const p3 = path[i + 1];

			//Angle from the previous point to the current point
			const angle1 = points_to_radians([p1, p2]);
			//Angle from the current point to the next point
			const angle2 = points_to_radians([p2, p3]);
			//Angle between the previous, current and next points
			const angle3 = points_to_radians3([p1, p2, p3]);

			//All "bottom" path vertices
			const v1: Position = point_to_vertex(p1, r, -1, angle1);
			const v2: Position = point_to_vertex(p2, r, -1, angle1);
			const v3: Position = point_to_vertex(p2, r, -1, angle2);
			const v4: Position = point_to_vertex(p3, r, -1, angle2);

			//All "top" path vertices
			const v5: Position = point_to_vertex(p1, r, 1, angle1);
			const v6: Position = point_to_vertex(p2, r, 1, angle1);
			const v7: Position = point_to_vertex(p2, r, 1, angle2);
			const v8: Position = point_to_vertex(p3, r, 1, angle2);

			//if the angle between the three points is negative then our shape is facing "down"
			//and the "top" vertices are separated by a curve meaning the bottom vertices are overlapping.
			//calculate a curve for the top 2 vertices and the intersection for the bottom 2.
			if (angle3 < 0) {
				const intersection = line_intersect(v1, v2, v3, v4);
				if (!intersection) {
					throw new Error('Invalid data');
				}
				const { x, y } = intersection;
				vDown.push([x, y]);
				vUp.push(
					...arc_curve(
						p2,
						r,
						steps,
						angle2 + PI / 2,
						angle1 + PI / 2,
					).reverse(),
				);
			}
			//else calculate a curve for the bottom 2 vertices and the intersection for the top 2.
			else {
				const intersection = line_intersect(v5, v6, v7, v8);
				if (!intersection) {
					throw new Error('Invalid data');
				}
				const { x, y } = intersection;
				vUp.push([x, y]);
				vDown.push(
					...arc_curve(
						p2,
						r,
						steps,
						angle1 - PI / 2,
						angle2 - PI / 2,
					),
				);
			}
		}
	}
	const res = [...vDown, ...vUp.reverse()];
	return res;
};

/**
 * Draw a polygon on an existing canvas context
 *
 * @param ctx {CanvasRenderingContext2D} - the canvas context on which to draw
 * @param points {Position[]} - the points that define our path
 */
export function drawPolygon(
	ctx: CanvasRenderingContext2D,
	points: Position[],
): void {
	if (points.length === 0) return;
	const [initx, inity] = points.filter(p => !!p).shift() as Position;
	ctx.beginPath();
	ctx.moveTo(initx, inity);
	points.forEach(([x, y]) => {
		ctx.lineTo(x, y);
	});
	ctx.fill();
}
/**
 * Generate a random integer in some range
 *
 * @param max {number} - the maximum random number allowed
 * @returns {number} an integer between zero and max
 */
export const randomInt = (max: number): number =>
	Math.floor(Math.random() * max);