Computer Graphics & Visualization @ufrj.br
Published
Edited
Dec 20, 2021
Importers
9 stars
// Returns the point in 'pts' that maximizes the dot product with 'v'
function support(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let best;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) [maxdot, best] = [dot, p];
}
return best;
}
// Returns the support point of the Minkowski difference pts1 - pts2 w.r.t. v
function support2(pts1, pts2, v) {
try {
return vec2.sub([], support(pts1, v), support(pts2, [-v[0], -v[1]]));
} catch (err) {
console.log("BUG Support2", pts1, pts2, v);
throw "BUG:" + err;
}
}
// Like support, but returns the index, rather than the point
function supportIndex(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let best = -1,
index = 0;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) [maxdot, best] = [dot, index];
index++;
}
return best;
}
// The Gilbert-Johnson-Keerthi algorithm. Given two polygons (pts1, pts2), visits the
// convex hull of the Minkowski difference between them and locates a simplex (a triangle) within the hull
// that contains the origin. Returns an array [a,b,c] with the vertices of that simplex or false if
// the simplex can't be found, i.e., if the hull does not contain the origin.
function gjk(pts1, pts2) {
// First point of pts1-pts2
let a = support2(pts1, pts2, [1, 1]);
// First direction
let v = [-a[0], -a[1]];
// Second point
let b = support2(pts1, pts2, v);
if (vec2.dot(b, v) <= 0) return false; // Second point fails
// Second direction
let ab = vec2.sub([], b, a);
v = tripleProduct(ab, [-a[0], -a[1]], ab);
for (;;) {
// Third point
let c = support2(pts1, pts2, v);
if (vec2.dot(c, v) <= 0) return false; // Third point fails
let c0 = [-c[0], -c[1]];
let cb = vec2.sub([], b, c);
let ca = vec2.sub([], a, c);
let cbPerp = tripleProduct(ca, cb, cb);
let caPerp = tripleProduct(cb, ca, ca);
if (vec2.dot(caPerp, c0) > 0) {
b = c;
v = caPerp;
} else if (vec2.dot(cbPerp, c0) > 0) {
a = c;
v = cbPerp;
} else return [a, b, c];
}
}
// Given a polygon containing the origin, returns the closest edge to the origin as a data structure
// containg 'dist' (the distance), 'i' (the index of the first vertex of the edge),
// 'p' (the first vertex of the edge), 'q' (the second vertex of the edge), 'n' (the edge normal
// in the direction of the origin).
function closestEdge(polytope) {
let npts = polytope.length;
let dmin = Number.POSITIVE_INFINITY;
let closest;
for (let i = 0; i < npts; i++) {
let [p, q] = [polytope[i], polytope[(i + 1) % npts]];
let e = vec2.sub([], q, p);
let n = vec2.normalize([], tripleProduct(e, p, e));
let dist = vec2.dot(n, p);
if (dist < dmin) [dmin, closest] = [dist, { dist, i, p, q, n }];
}
return closest;
}
// The Expanding Polytope Algorithm. Starting from a triangle a,b,c within the convex hull of
// the Minkowski difference between pts1 and pts2, returns the closest edge of this hull
// as a data-structure containing 'p' (the first vertex of the edge), 'q' (the second vertex of the edge),
// 'n' (the edge normal in the direction of the origin) and 'dist' (the distance to the origin)
function epa(pts1, pts2, a, b, c) {
let polytope = [a, b, c];
for (;;) {
let { dist, i, p, q, n } = closestEdge(polytope);
let r = support2(pts1, pts2, n);
if (Math.abs(vec2.dot(n, r) - dist) < 0.001) return { p, q, dist, n };
polytope.splice(i + 1, 0, r);
}
}
// Like support, but returns not only the vertex of pts that maximizes the dot product with v,
// but also the next best contender, if sufficiently close. This is useful if v is perpendicular to one
// of the edges of pts, which is the case for the data returned by the EPA.
function supportEdge(pts, v) {
let maxdot = Number.NEGATIVE_INFINITY;
let maxdot2 = Number.NEGATIVE_INFINITY;
let best, best2;
for (let p of pts) {
let dot = vec2.dot(p, v);
if (dot > maxdot) {
[maxdot2, best2] = [maxdot, best];
[maxdot, best] = [dot, p];
} else if (dot > maxdot2) {
[maxdot2, best2] = [dot, p];
}
}
if (Math.abs(maxdot - maxdot2) < 0.01) return [best2, best];
return [best];
}
mutable changedPolygon = 0;
function minkDiff(a, b) {
let result = [];
for (let p of a) {
for (let q of b) {
result.push(vec2.sub([], p, q));
}
}
return result;
}
function minkPolygon(a, b) {
let result = [];
let prev = [Number.POSITIVE_INFINITY, Number.POSITIVE_INFINITY];
for (let ang = 0; ang < Math.PI * 2; ang += 0.05) {
let p = support2(a, b, [Math.cos(ang), Math.sin(ang)]);
if (vec2.dist(p, prev) > 0.0001) result.push(p);
prev = p;
}
return result;
}
// Returns an array of points with the vertices of a regular polygon
// centered at 'center', with the given radius and number of sides.
function regularPolygonPoints (center = [0,0], radius = 1, nsides=3) {
let poly = [];
let delta = Math.PI*2/nsides;
for (let i = 0; i < nsides; i++) {
poly.push([center[0]+radius*Math.cos(delta*i),center[1]+radius*Math.sin(delta*i)])
}
return poly
}
// Returns an array of 4 points, one for each corner of a rectangle
// having the given center and size
function rectanglePoints(center = [0, 0], size = [1, 1]) {
return [
[-0.5, -0.5],
[0.5, -0.5],
[0.5, 0.5],
[-0.5, 0.5]
].map(([dx, dy]) => [center[0] + size[0] * dx, center[1] + size[1] * dy]);
}
// Returns the center of mass of an array of 2d points
function centerOfMass(pts) {
let sum = pts.reduce((a, b) => [a[0] + b[0], a[1] + b[1]]);
return [sum[0] / pts.length, sum[1] / pts.length];
}
// Returns true iff p inside poly
function pointInPolygon(p, poly) {
let [x, y] = p;
let xLeft = Number.NEGATIVE_INFINITY,
xRight = Number.POSITIVE_INFINITY;
let leftSign = 0,
rightSign = 0;
let q = poly[poly.length - 1];
for (let p of poly) {
if (q[1] < y != p[1] < y) {
let alpha = (p[1] - y) / (p[1] - q[1]);
let xi = p[0] * (1 - alpha) + q[0] * alpha;
if (xi < x) {
if (xi > xLeft) {
xLeft = xi;
leftSign = Math.sign(p[1] - q[1]);
}
} else {
if (xi < xRight) {
xRight = xi;
rightSign = Math.sign(p[1] - q[1]);
}
}
}
q = p;
}
return (
xLeft != Number.NEGATIVE_INFINITY &&
xRight != Number.POSITIVE_INFINITY &&
leftSign < 0
);
}
// A canvas display helper class
class Display {
constructor(w = 640, h = 480) {
[this.w, this.h] = [w, h];
this.canvas = html`<canvas width=${w} height=${h} style="border:1px solid gray" />`;
this.canvas.value = this;
this.ctx = this.canvas.getContext('2d');
}
clear() {
this.ctx.clearRect(0, 0, this.w, this.h);
}
drawPoints(pts, options = {}) {
options = Object.assign(
{ radius: 4, fill: 'black', stroke: null },
options
);
this.ctx.save();
this.ctx.strokeStyle = options.stroke;
this.ctx.fillStyle = options.fill;
for (let p of pts) {
this.ctx.beginPath();
this.ctx.arc(p[0], p[1], options.radius, 0, Math.PI * 2);
if (options.fill) this.ctx.fill();
if (options.stroke) this.ctx.stroke();
}
this.ctx.restore();
}
drawPolygon(pts, options = {}) {
options = Object.assign(
{
radius: 4,
fill: null,
stroke: 'black',
lineWidth: 1,
dash: [],
close: true
},
options
);
this.ctx.save();
this.ctx.strokeStyle = options.stroke;
this.ctx.fillStyle = options.fill;
this.ctx.setLineDash(options.dash);
this.ctx.lineWidth = options.lineWidth;
this.ctx.beginPath();
this.ctx.moveTo(pts[0][0], pts[0][1]);
for (let p of pts) {
this.ctx.lineTo(p[0], p[1]);
}
if (options.close) this.ctx.closePath();
if (options.fill) this.ctx.fill();
if (options.stroke) this.ctx.stroke();
this.ctx.restore();
}
}
glmatrix = import('https://unpkg.com/gl-matrix@3.3.0/esm/index.js?module')
vec2 = glmatrix.vec2
import { combo } from "@esperanc/aggregated-inputs"
import { select } from "@jashkenas/inputs"
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.