2D Geometry Utils / yalmar

md`# 2D Geometry Utils`

Curve = {

// A curve is an array of points

class Curve extends Array {

constructor (...args) {

super(...args)

}

// Returns an array with the same size as this curve where each element

// is the total arc length at that point

arcLength () {

let q = this[0];

let r = 0;

let per = [];

per [0] = 0;

for (let i = 1; i < this.length; i++) {

var p = this[i];

r += p.dist(q);

per [i] = r;

q = p;

}

return per;

}

// Total length of the curve

perimeter() {

return this.arcLength ()[this.length-1]

}

// Returns the area enclosed by the curve

area () {

let s = 0.0;

for (let i = 0; i < this.length; i++) {

let j = (i+1)%this.length;

s += this[i].x * this[j].y;

s -= this[i].y * this[j].x;

}

return s;

}

// A minimum bounding rectangle for the curve

mbr () {

let r = new MBR();

for (let p of this) r.add(p);

return r;

}

// Returns true if this curve (assuming it represents a closed simple polygon)

// contains point p.

contains (p) {

if (this.length < 3) return false;

let a = this [this.length-1];

let closest = [];

let dist = Number.POSITIVE_INFINITY;

for (let b of this) {

let d = p.distSegment (a,b);

if (d < dist && a.dist(b) >= 1) {

closest = [a,b];

dist = d

}

a = b;

}

let orient = p.orient(closest[0],closest[1])

return (orient != 0) && (this.area() < 0) == (orient < 0)

}

// Returns a subsampled version of this curve, where tol is

// the maximum allowed Douglas Peucker distance and count is the

// maximum number of points allowed

subsample (tol = 0, count = 1e10) {

let rank = douglasPeuckerRank(this,tol);

var r = new Curve();

for (let i = 0; i < this.length; i++) {

if (rank[i] != undefined && rank[i] < count) {

r.push(this[i])

}

return r;

}

// Returns another curve resampled by arc length with n points

resample (n) {

let per = this.arcLength()

let len = per [per.length-1];

let dlen = len / (n-1);

let p = this[0];

let r = new Curve();

r.push (p.clone());

let j = 0;

for (let i = 1; i < n; i++) {

let d = dlen*i;

while (j+1 < this.length-1 && per[j+1]<d) j++;

let alpha = (d-per[j])/(per[j+1]-per[j]);

r.push(this[j].mix(this[j+1],alpha));

}

return r;

}

// Returns a resampling of this curve with n points where the original points are considered

// control points. If not closed, the first and last points are considered twice so that

// the catmull-rom spline interpolates them. If closed, the first and last points are also

// considered twice, but in the opposite order. The tension parameter controls the spline interpolation

splineResample(n, closed=false, tension = 0.5) {

let p = (closed?[]:[this[0]]).concat(this)

if (!closed) p.push (this[this.length-1])

let cr = new CatmullRom(...p)

cr.tension = tension;

let r = new Curve();

let f = closed ? this.length / (n-1) : (this.length-1) / (n-1);

for (let i = 0; i < n; i++) {

let u = i * f

r.push (cr.point(u))

}

return r

}

// Creates a Douglas Peucker Item, which

// represents a span of a polyline and the farthest element from the

// line segment connecting the first and the last element of the span.

// Poly is an array of points, first is the index of the first element of the span,

// and last the last element.

function dpItem (first, last, poly) {

var dist = 0;

var farthest = first+1;

var a = poly[first];

var b = poly[last];

for (var i = first+1; i < last; i++) {

var d = poly[i].distSegment (a, b);

if (d > dist) {

dist = d;

farthest = i;

}

return {

first: first,

last: last,

farthest: farthest,

dist : dist

}

};

// Returns an array of ranks of vertices of a polyline according to the

// generalization order imposed by the Douglas Peucker algorithm.

// Thus, if the i'th element has value k, then vertex i would be the (k+1)'th

// element to be included in a generalization (simplification) of this polyline.

// Does not consider vertices farther than tol. Disconsidered

// vertices are left undefined in the result.

function douglasPeuckerRank (poly, tol) {

// A priority queue of intervals to subdivide, where top priority is biggest dist

var pq = new BinaryHeap (function (dpi) { return -dpi.dist; });

// The result vector

var r = [];

// Put the first and last vertices in the result

r [0] = 0;

r [poly.length-1] = 1;

// Add first interval to pq

if (poly.length <= 2) { return r };

pq.push (dpItem (0, poly.length-1, poly));

// The rank counter

var rank = 2;

// Recursively subdivide up to tol

while (pq.size ()>0) {

var item = pq.pop ();

if (item.dist < tol) break; // All remaining points are closer

r [item.farthest] = rank++;

if (item.farthest > item.first+1) {

pq.push (dpItem (item.first, item.farthest, poly));

}

if (item.last > item.farthest+1) {

pq.push (dpItem (item.farthest, item.last, poly));

}

return r;

}

return Curve

}

Vec = (x,y)=>new Vector(x,y)

viewof tolerance = new View (5)

md`### Matrices`

mutable tcount = 0

Transform = {

function Slider (options={}) {

let {title="", min=-100, max=100, step=1, size="20em", value=0, callback=()=>0 } = options;

let input = html`<input type=range min=${min} max=${max} step=${step} style='width:${size}'>`;

let output = html`<output>${value}</output>`;

input.value = value;

input.oninput = (e) => {

value = input.value;

output.value = value

callback(value)

}

return html`${title}: ${input} ${output}`;

}

function XYSlider (options) {

let {title="", min=-100, max=100, step=1, size="10em", value=Vec(0,0), callback=()=>0 } = options;

let xslider = Slider({title:"x", min:min, max:max, step:step, value:value.x,

callback : x=> {value.x = +x; callback(value) }});

let yslider = Slider({title:"y", min:min, max:max, step:step, value:value.y,

callback : y=> {value.y = +y; callback(value) }});

return html`${title}   ${xslider} ,  ${yslider}`;

}

function matrixTex (m) {

let fmt = (x) => x.toFixed(4) == x ? x : x.toFixed(4);

return `\\begin{bmatrix}

${fmt(m.a)} & ${fmt(m.c)} & ${fmt(m.e)} \\\\

${fmt(m.b)} & ${fmt(m.d)} & ${fmt(m.f)} \\\\

0 & 0 & 1

\\end{bmatrix}`

}

class Transform {

constructor (callback = (t) => {}) {

this.callback = callback;

this.matrices = [];

this.sliders = [];

}

reset () {

this.matrices = [];

this.sliders = [];

this.callback(this);

return this

}

addTranslate () {

let i = this.matrices.length;

this.matrices.push (new Matrix())

this.sliders.push (XYSlider({title : "Translate ", min:-100, max:100, step:1, value:Vec(0,0),

callback : t => { this.matrices[i] = Matrix.translate(t.x,t.y); this.callback(this) }}));

return this;

}

addScale() {

let i = this.matrices.length;

this.matrices.push (new Matrix())

this.sliders.push (XYSlider({title : "Scale ", min:0.2, max:4, step:0.2, value:Vec(1,1),

callback: s => { this.matrices[i] = Matrix.scale(s.x,s.y); this.callback(this) }}));

return this;

}

addShear() {

let i = this.matrices.length;

this.matrices.push (new Matrix())

this.sliders.push (XYSlider({title : "Shear ", min:-4, max:4, step:0.2, value:Vec(0,0),

callback: s => { this.matrices[i] = Matrix.shear(s.x,s.y); this.callback(this) }}));

return this;

}

addRotate() {

let i = this.matrices.length;

this.matrices.push (new Matrix())

this.sliders.push (Slider({title:"Rotate", min:-180, max:180, step:5, value:0,

callback : a => { this.matrices[i] = Matrix.rotate(Math.PI*a/180);

this.callback(this) }}));

return this;

}

UI () {

let ui = html`<div></div>`;

for (let slider of this.sliders) {

ui.append(slider)

ui.append(html`<br>`)

}

return ui

}

matrix() {

if (this.matrices.length == 0) return new Matrix()

if (this.matrices.length == 1) return this.matrices[0];

return this.matrices.reduce((a,b) => a.mult(b))

}

tex() {

if (this.matrices.length < 2) return tex`${matrixTex(this.matrix())}`;

return tex`${(this.matrices.map(matrixTex)).join("\\times")+"="+matrixTex(this.matrix())}`;

}

return Transform

}

mutable T = new Transform(() => { mutable tcount++ } )

matrixDemoUI = T.UI()

matrix = {

tcount;

return html`<p>Matrix: <\p> ${T.tex()}`

}

Purpose-built for displays of data