render bounding polygon

1 files changed, 119 insertions, 2 deletions

diff --git a/site/main.mjs b/site/main.mjs
index 0c81b41..280ee43 100644
--- a/site/main.mjs
+++ b/site/main.mjs
@@ -1,4 +1,4 @@
-const NUM_POINTS = 5;
+const NUM_POINTS = 40;
 
 // thanks vihart
 const TAU = 2 * Math.PI;
@@ -16,6 +16,23 @@ class Point {
     speed = Math.random() * MAX_SPEED;
     color = randColor();
 
+    constructor(x = Math.random(), y = Math.random()) {
+        this.x = x;
+        this.y = y;
+    }
+
+    equalPos(other) {
+        return this.x === other.x && this.y === other.y;
+    }
+
+    dot(other) {
+        return this.x * other.x + this.y * other.y;
+    }
+
+    get mag() {
+        return Math.sqrt(Math.pow(this.x, 2) + Math.pow(this.y, 2));
+    }
+
     #speedX;
     get speedX() {
         if (this.#speedX === undefined) {
@@ -40,9 +57,98 @@ class Point {
         this.#heading = val;
         this.#speedX = this.#speedY = undefined;
     }
+
+    toString() {
+        return `(0.${Math.floor(this.x*100)}, 0.${Math.floor(this.y*100)})`
+    }
+}
+
+class Line {
+    constructor(p1, p2) {
+        this.p1 = p1;
+        this.p2 = p2;
+    }
+
+    get vec() {
+        return new Point(this.p2.x - this.p1.x, this.p2.y - this.p1.y)
+    }
+
+    angleBetween(other) {
+        //        console.debug('    angleBetween', this.toString(), other.toString());
+        const v1 = this.vec;
+        const v2 = other.vec;
+        //        console.debug(`    dot of ${v1} * ${v2}`, v1.dot(v2));
+        //        console.debug(`    mag of ${v1} * ${v2}`, v1.mag * v2.mag);
+        const theta = Math.acos(v1.dot(v2) / (v1.mag * v2.mag));
+        //        console.debug(`    theta is`, 360 * theta / TAU);
+        return theta;
+    }
+    angleBetween2(other) {
+        console.debug('angleBetween',
+            `(${this.p1.x}, ${this.p1.y})-(${this.p2.x}, ${this.p2.y})`,
+            `(${other.p1.x}, ${other.p1.y})-(${other.p2.x}, ${other.p2.y})`,
+        );
+        return Math.atan(Math.abs((this.slope - other.slope) / (1 + this.slope * other.slope)))
+    }
+
+    get slope() {
+        return (this.p2.y - this.p1.y) / (this.p2.x - this.p1.x);
+    }
+
+    toString() {
+        return `${this.p1}-${this.p2}`;
+    }
+}
+
+// assume points is sorted min first.
+function findPoly3(points) {
+    //    console.debug('findPoly()', ...points.map(p => { return {x: p.x, y: p.y} }));
+
+    let lastLine = new Line(new Point(0, 0), new Point(1, 0));
+    //    console.debug('horiz slope', lastLine.slope);
+
+    // bail out counter. shouldn't be necessary, but who knows.
+    let xxx = 100;
+    let res = [points[0]];
+    do {
+        // last result is always a point on the edge.
+        const p1 = res[res.length-1];
+        //        console.debug(`-- checking lines from ${p1}`);
+        let last = res[res.length-1];
+        let minTheta = TAU;
+        let minP = points[0];
+        for (let i = 0; i < points.length; i++) {
+            if (!last.equalPos(points[i])) {
+                let l2 = new Line(last, points[i]);
+                let theta = lastLine.angleBetween(l2);
+                //                console.debug('+++ l2 slope', l2.slope, theta, 360 * theta / TAU);
+                if (theta < minTheta) {
+                    //                    console.debug(' -- min angle')
+                    minTheta = theta;
+                    minP = points[i];
+                }
+            }
+        }
+        lastLine = new Line(res[res.length-1], minP);
+        res.push(minP);
+        //        console.debug('term', xxx, res[0].x, res[0].y, res[res.length-1].x, res[res.length-1].y)
+    } while (xxx-- > 0 && !res[0].equalPos(res[res.length-1]));
+    if (xxx === 0) {
+        alert('couldn\'t find your polycule');
+    }
+
+    //    console.debug('findPoly res', res);
+    return res;
 }
 
 const points = [...Array(NUM_POINTS)].map(_ => new Point());
+// const points = [
+//     new Point(0.5, 0.1),
+//     new Point(0.75, 0.2),
+//     new Point(0.9, 0.9),
+//     new Point(0.2, 0.5),
+//     new Point(0.6, 0.4), // should be inside
+// ];
 
 function randColor() {
     const [r, g, b] = [...Array(3)].map(_ => Math.random() * 255);
@@ -56,6 +162,7 @@ function renderPoints(ctx, points) {
         ctx.arc(p.x, p.y, POINT_RADIUS, 0, TAU);
         ctx.fill();
 
+        ctx.strokeStyle = p.color;
         ctx.lineWidth = 0.005;
         ctx.beginPath();
         ctx.moveTo(p.x, p.y);
@@ -97,7 +204,7 @@ function bouncePoints(points) {
 async function loaded() {
     const canvas = document.querySelector('canvas');
     const ctx = canvas.getContext('2d');
-    console.debug('canvas:', canvas, 'ctx', ctx, 'points:', points);
+    console.debug('canvas:', canvas, 'ctx', ctx);
     ctx.scale(canvas.width, canvas.height);
 
     const fps = document.querySelector('#fps');
@@ -128,6 +235,16 @@ async function loaded() {
         }
         movePoints(points);
 
+        points.sort((a, b) => a.y > b.y);
+        const polyPoints = findPoly3(points);
+
+        ctx.lineWidth = 0.005;
+        ctx.beginPath();
+        ctx.moveTo(polyPoints[0].x, polyPoints[0].y);
+        polyPoints.forEach(p => ctx.lineTo(p.x, p.y));
+        ctx.strokeStyle = 'blue';
+        ctx.stroke();
+
         if (!paused) {
             self.requestAnimationFrame(render);
         }