1 files changed, 103 insertions, 18 deletions

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);
+}