From 54c34ca3051743fd3f1c02f73a321299af456b8a Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Sat, 1 Apr 2023 00:15:05 -0500
Subject: attempt implementing convex hull algorithm

---
 src/Geometry.js | 121 ++++++++++++++++++++++++++++++++++++++++--------
 src/MapView.js  |   5 +-
 src/Terrain.js  | 139 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.js     |  24 +++++++++-
 4 files changed, 268 insertions(+), 21 deletions(-)
 create mode 100644 src/Terrain.js

diff --git a/src/Geometry.js b/src/Geometry.js
index 23ef480..05c22e0 100644
--- a/src/Geometry.js
+++ b/src/Geometry.js
@@ -117,6 +117,31 @@ export class Vec3 {
 		return new Point(latitude, longitude)
 	}
 
+	copy() {
+		return new Vec3(this.x, this.y, this.z);
+	}
+
+	add(vec) {
+		this.x = this.x + vec.x;
+		this.y = this.y + vec.y;
+		this.z = this.z + vec.z;
+		return this
+	}
+
+	sub(vec) {
+		this.x = this.x - vec.x;
+		this.y = this.y - vec.y;
+		this.z = this.z - vec.z;
+		return this;
+	}
+
+	scale(a) {
+		this.x = this.x * a;
+		this.y = this.y * a;
+		this.z = this.z * a;
+		return this;
+	}
+
 	dot(vec) {
 		return (this.x * vec.x) + (this.y * vec.y) + (this.z * vec.z);
 	}
@@ -143,25 +168,17 @@ export class Vec3 {
 }
 
 
+export function RandomNormal() {
+	const theta = 2*Math.PI*Math.random();
+	const z = 2*Math.random() - 1;
+	const s = Math.sqrt(1-(z*z));
+	return new Vec3(s*Math.cos(theta), s*Math.sin(theta), z).normalize();
+}
+
+
 export class Shape {
 	constructor(normals) {
 		this.normals = normals;
-		let avgx = 0;
-		let avgy = 0;
-		let avgz = 0;
-		for (let normal of normals) {
-			avgx += normal.x;
-			avgy += normal.y;
-			avgz += normal.z;
-		}
-		avgx /= normals.length;
-		avgy /= normals.length;
-		avgz /= normals.length;
-		this.center = new Vec3(avgx, avgy, avgz).normalize();
-		this.extent = 0
-		for (let normal of normals) {
-			this.extent = Math.max(this.extent, normal.dot(this.center));
-		}
 	}
 
 	translate(circle, angle) {
@@ -169,7 +186,6 @@ export class Shape {
 		for (let i=0; i<this.normals.length; i++) {
 			this.normals[i] = transform.mulv(this.normals[i]);
 		}
-		this.center = transform.mulv(this.normals[i]);
 	}
 
 	getNextRenderPoint(ct, start, view) {
@@ -198,12 +214,81 @@ export class Shape {
 			return;
 		}
 
-
 		ct.moveTo(v.x, v.y);
+		let count = 0;
 		while(v != null) {
+			count += 1;
 			ct.lineTo(v.x, v.y);
 			[ i, v ] = this.getNextRenderPoint(ct, i, view);
 		}
+		if (count == this.normals.length) {
+			ct.closePath();
+		}
 		ct.stroke();
 	}
 }
+
+
+export function ConvexHull(points) {
+	const hull = [];
+
+	console.log("compute center");
+	// compute the average of the group of points
+	let center = new Vec3(0, 0, 0);
+	for (let point of points) {
+		center.add(point);
+	}
+	center.scale(1/points.length).normalize;
+
+	console.log("find furthest");
+	// find the furthest point from the center
+	let furthest = null;
+	let mindot = 1;
+	for (let point of points) {
+		const d = center.dot(point);
+		if (d < mindot) {
+			mindot = d;
+			furthest = point;
+		}
+	}
+
+	const t0 = furthest.copy().sub(center).cross(furthest).normalize();
+
+	function getNextHullPoint(p, tangent) {
+		let next = null;
+		let max = -1;
+		for (let point of points) {
+			const v = point.copy().sub(p).normalize();
+			const d = v.dot(tangent);
+			if (d > max) {
+				max = d;
+				next = point;
+			}
+		}
+		return next;
+	}
+
+	function tangent(p, prev) {
+		return p.copy().sub(prev).normalize();
+	}
+
+	hull.push[furthest];
+	let p = getNextHullPoint(furthest, t0);
+	let tan = tangent(p, furthest);
+
+	// begin loop
+	console.log("loop");
+	let count = 0;
+	while (p != null) {
+		count += 1;
+		hull.push(p);
+		p = getNextHullPoint(p, tan);
+		tan = tangent(p, hull[hull.length-1]);
+		if (p == furthest || count > 50) {
+			console.log(count);
+			p = null;
+		}
+	}
+
+	return new Shape(hull);
+}
diff --git a/src/MapView.js b/src/MapView.js
index 8f41480..0afa713 100644
--- a/src/MapView.js
+++ b/src/MapView.js
@@ -105,11 +105,12 @@ export class MapView {
 
 	zoom(delta) {
 		let scale;
+		const zoom = 1.1;
 		if (delta < 0) {
-			scale = 2;
+			scale = zoom;
 		}
 		else {
-			scale = 1/2;
+			scale = 1/zoom;
 		}
 
 		this.scale *= scale;
diff --git a/src/Terrain.js b/src/Terrain.js
new file mode 100644
index 0000000..a51c0a3
--- /dev/null
+++ b/src/Terrain.js
@@ -0,0 +1,139 @@
+import { Mat3, Vec3, Point, RandomNormal, Shape, ConvexHull } from './Geometry.js';
+
+
+export function RandomPoints(n) {
+	const points = [];
+	for (let i=0; i<n; i++) {
+		points.push(RandomNormal());
+	}
+	return points;
+}
+
+
+export class Plate {
+	constructor(points) {
+		this.color = `hsl(${360*Math.random()}, 100%, 50%)`
+		this.points = points;
+		this.hull = ConvexHull(points);
+		let [avgX, avgY, avgZ] = [0, 0, 0];
+		for (let point of points) {
+			avgX += point.x;
+			avgY += point.y;
+			avgZ += point.z;
+		}
+		avgX /= points.length;
+		avgY /= points.length;
+		avgZ /= points.length;
+		this.center = new Vec3(avgX, avgY, avgZ).normalize();
+		this.extent = 0;
+		for (let point of points) {
+			this.extent = Math.max(this.extent, this.center.dot(point));
+		}
+
+		this.speed = Math.random();
+		this.axis = RandomNormal().cross(this.center).normalize();
+	}
+
+	filterColliding(plate) {
+		const extent = Math.max(this.extent, plate.extent);
+		return this.center.dot(plate.center) < extent;
+	}
+
+	checkColliding(plate) {
+		if (!this.filterColliding(plate)) {
+			return false;
+		}
+		
+		console.log("check", this, plate);
+
+		const threshold = 0.00001;
+		let collisionTotal = 0;
+		for (let pa of this.points) {
+			for (let pb of plate.points) {
+				collisionTotal += pa.dot(pb);
+			}
+		}
+		collisionTotal /= this.points.length * plate.points.length;
+		console.log(this, plate, collisionTotal);
+		if (collisionTotal > threshold) {
+			return true;
+		}
+		return false;
+	}
+
+	move() {
+		const matrix = new Mat3().rotation(this.axis, this.speed * 0.01 * Math.PI);
+		for (let i=0; i<this.points.length; i++) {
+			this.points[i] = matrix.mulv(this.points[i]);
+		}
+		this.hull.translate(this.axis, this.speed * 0.01 * Math.PI);
+		this.center = matrix.mulv(this.center);
+	}
+
+	render(ct, view) {
+		ct.fillStyle = this.color;
+		for (let point of this.points) {
+			point.render(ct, view);
+		}
+		this.hull.render(ct, view);
+	}
+}
+
+
+function randomChoice(array) {
+	const index = Math.floor(array.length * Math.random());
+	return array[index];
+}
+
+
+export class PlateManager {
+	constructor(points, plateCount) {
+		this.points = points;
+		this.plates = this.buildPlates(plateCount);
+	}
+
+
+	buildPlates(plateCount) {
+		const seedPoints = [];
+		const points = [];
+		for (let i=0; i<plateCount; i++) {
+			seedPoints.push(randomChoice(this.points));
+			points.push([]);
+		}
+		
+		for (let point of this.points) {
+			let maxDot = -1;
+			let index = -1;
+			for (let i=0; i<plateCount; i++) {
+				const seed = seedPoints[i];
+				const d = seed.dot(point);
+				if (d > maxDot) {
+					maxDot = d;
+					index = i;
+				}
+			}
+			if (index == -1) {
+				console.error("no closest point", point);
+			}
+			points[index].push(point);
+		}
+
+		const plates = [];
+		for (let p of points) {
+			plates.push(new Plate(p));
+		}
+		return plates;
+	}
+
+	update() {
+		for (let plate of this.plates) {
+			plate.move();
+		}
+	}
+
+	render(ct, view) {
+		for (let plate of this.plates) {
+			plate.render(ct, view);
+		}
+	}
+}
diff --git a/src/main.js b/src/main.js
index db8963d..8ed95d1 100644
--- a/src/main.js
+++ b/src/main.js
@@ -1,6 +1,7 @@
 import Canvas from './Canvas.js';
-import { Mat3, Vec3, Point, Shape } from './Geometry.js';
+import { Mat3, Vec3, Point, Shape, RandomNormal } from './Geometry.js';
 import { MapGrid, MapView } from './MapView.js';
+import { RandomPoints, Plate, PlateManager } from './Terrain.js';
 
 const $ = id => document.getElementById(id)
 
@@ -14,6 +15,17 @@ window.onload = () => {
 	const grid = new MapGrid(30, 30);
 	const map = new MapView(canvas);
 
+	const points = [];
+	for (let i=0; i<100; i++) {
+		points.push(
+			new Point(Math.random() * 0.2 * Math.PI, Math.random() * 0.2 * Math.PI).normal()
+		);
+	}
+	const plate = new Plate(points);
+
+//	const points = RandomPoints(100);
+//	const mgr = new PlateManager(points, 10);
+
 	map.onDraw = (ct, view) => {
 		ct.fillStyle = "#01162B"
 		ct.fillRect(-10,-10, 100, 100);
@@ -22,6 +34,16 @@ window.onload = () => {
 		ct.fillStyle = "blue";
 
 		grid.render(ct, view);
+
+		//mgr.render(ct, view);
+		plate.render(ct, view);
+		ct.fillStyle = "blue";
+		plate.hull.normals[0].render(ct, view);
 	};
 	canvas.draw();
+
+//	setInterval(() => {
+//		mgr.update();
+//		canvas.draw();
+//	}, 100);
 }
-- 
cgit v1.2.1