Published
Edited
Apr 26, 2022
Importers
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
mahalanobis = (p,q) => Math.sqrt(
(
((p[0]-q[0]) * 1 + (p[1]-q[1]) * 0.5) * (p[0]-q[0]) +
((p[0]-q[0]) * 0.5 + (p[1]-q[1]) * 1) * (p[1]-q[1])
)
)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
viewof polygonDemo = {
let ctx = DOM.context2d(640,480);
let polygon = new VList();
let rlist = new RectList (polygon);
let operation;
let lastPos = [100,100], side, R;
let setOperation = (opname) => {
operation = (opname=="draw") ? union : difference;
}
setOperation ("draw");
let refresh = () => {
ctx.clearRect(0,0,640,480);
let hit = rlist.rectIntersection(R);
ctx.strokeStyle = hit ? "red" : "black";
drawPolygon (ctx, polygon);
drawVList(ctx,R);
}
let setBrush = (s) => {
side = s;
R = rectangle (lastPos, [side,side]);
refresh();
}
setBrush (20);

let dilatePolygon = ()=>{
polygon = dilate(polygon,side);
rlist = new RectList (polygon);
refresh();
}
let erodePolygon = () => {
polygon = erode(polygon,side);
rlist = new RectList (polygon);
refresh();
}

ctx.canvas.onmousemove = ctx.canvas.onmousedown = (e) => {
let c = side/Math.sqrt(2);
lastPos = [e.offsetX-c,e.offsetY-c];
R = rectangle(lastPos,[side,side]);
if (e.buttons != 0) {
polygon = operation(polygon,R);
rlist = new RectList (polygon);
}
refresh();
}
refresh();
ctx.canvas.value = { setOperation, setBrush, dilatePolygon, erodePolygon };
return ctx.canvas;
}
Insert cell
Insert cell
Insert cell
// Returns the perimeter of an orthogonal polygon represented as vertex list vlist
function perimeter (vlist) {
let hedgesLen = (vlist) => {
let sum = 0;
for (let [prev,v] of vlist.faces()) {
sum += v.p[0] - prev.p[0];
}
return sum
};
return hedgesLen(vlist) + hedgesLen(vlist.rotAxesClock())
}
Insert cell
// Returns a vertex list representing a square having length/height equal to side
// and minimum corner (corner with smallest coordinates) at mincorner
function square (minCorner = [0,0], side = 1) {
return rectangle(minCorner,[side,side])
}
Insert cell
// Returns a vertex list representing a rectangle having [length,height] equal to sides
// and minimum corner (corner with smallest coordinates) at mincorner
function rectangle (minCorner = [0,0], sides = [10,10]) {
let [x,y] = minCorner;
let [sidex,sidey] = sides;
return new VList(
new Vertex(+1,[x,y]),
new Vertex(-1,[x+sidex,y]),
new Vertex(-1,[x,y+sidey]),
new Vertex(+1,[x+sidex,y+sidey])
)
}
Insert cell
// Returns true iff rectangle a intersects rectangle b
function rectRectIntersect (a,b) {
return Math.min(a[3].p[0],b[3].p[0]) > Math.max(a[0].p[0],b[0].p[0]) &&
Math.min(a[3].p[1],b[3].p[1]) > Math.max(a[0].p[1],b[0].p[1])
}
Insert cell
// A data structure for quick intersection tests against an orthogonal polygon
class RectList {
// Constructor from a vertex list
constructor (vlist) {
this.rects = vlist.rectangles();
this.it = createIntervalTree(this.rects.map(r=>{
let interval = [r[0].p[1],r[3].p[1]];
interval.rect = r
return interval
}))
}
rangeSearch (ymin,ymax) {
let all = [];
this.it.queryInterval (ymin,ymax,interval=>{all.push(interval)});
return all;
}
// Returns true if polygon intersects point p
pointIntersection (p) {
for (let interval of this.rangeSearch(p[1],p[1]+1)) {
let r = interval.rect;
if (r[3].p[1]>p[1] && r[3].p[0]>p[0] && r[0].p[0]<=p[0]) return true;
}
return false
}
// Returns true if polygon intersects rectangle R
rectIntersection (R) {
let ymin = R[0].p[1];
let ymax = R[3].p[1];
for (let interval of this.rangeSearch(ymin,ymax)) {
let r = interval.rect;
if (rectRectIntersect (r,R)) return true;
}
return false
}
}
Insert cell
// Returns the union of two orthogonal polygons represented as vertex lists
function union (a,b) {
return a.add(b).transform(w => +(w>0))
}

Insert cell
// Returns the intersection of two orthogonal polygons represented as vertex lists
function intersection (a,b) {
return a.add(b).transform(w => +(w>1))
}
Insert cell
// Returns the difference of two orthogonal polygons represented as vertex lists
function difference (a,b) {
return a.add(b.scale(-1)).transform(w => +(w>0))
}
Insert cell
// Returns the minimum and maximum corner of the smallest rectangle containing all vertices of vlist
function boundingBox (vlist) {
let min = [Number.MAX_VALUE,Number.MAX_VALUE],
max = [Number.MIN_VALUE,Number.MIN_VALUE];
for (let v of vlist) {
for (let i of [0,1]) {
if (v.p[i] < min[i]) min[i] = v.p[i];
if (v.p[i] > max[i]) max[i] = v.p[i];
}
}
return {min,max}
}
Insert cell
// Returns a normalized vlist, i.e., one with no 2 vertices at the same position
function normalizeVList(vlist) {
if (vlist.length < 2) return vlist;
let result = new VList();
let prev = vlist[0];
for (let i = 1; i < vlist.length; i++) {
let next = vlist[i];
if (prev.cmp(next) == 0) {
prev.w += next.w;
}
else {
if (prev.w != 0) result.push (prev)
prev = next;
}
}
if (prev.w != 0) result.push (prev)
return result;
}
Insert cell
// Returns the polygon given by vlist dilated (positive d) or contracted (negative d)
function topo (vlist, d) {
if (d < 0) return erode (vlist,-d)
else return dilate (vlist, d)
}
Insert cell
// Returns the polygon given by vlist dilated by d
function dilate (vlist, d) {
let vtx = [];
for (let r of vlist.rectangles()) {
[[-d,-d],[d,-d],[-d,d],[d,d]].forEach(([dx,dy],i) => {
r[i].p[0]+=dx;
r[i].p[1]+=dy;
vtx.push(r[i]);
});
}
return normalizeVList(new VList(...vtx)).transform(w => +(w>0))
}
Insert cell
function erode(vlist,d) {
if (vlist.length < 4) return new VList();
// Find bounding box
let {min,max} = boundingBox(vlist);
for (let v of vlist) {
for (let i of [0,1]) {
if (v.p[i] < min[i]) min[i] = v.p[i];
if (v.p[i] > max[i]) max[i] = v.p[i];
}
}
let m = 10; //margin
let box = rectangle ([min[0]-m,min[1]-m],[max[0]-min[0]+m+m,max[1]-min[1]+m+m]);
// subtract
let boxMinus = new VList();
boxMinus.push(box[0],box[1]);
for (let v of vlist) boxMinus.push (v.scale(-1));
boxMinus.push(box[2],box[3]);
// dilate the result
let result = dilate(boxMinus,d);
// Return -hole
return result.slice(2,result.length-2).map(v=>{v.w = -v.w; return v})
}
Insert cell
// Draws a color-coded representation of vlist onto canvas using context ctx
function drawVList (ctx,vlist) {
for (let d of vlist.rectangles()) {
let x = d[0].p[0];
let y = d[0].p[1];
let w = d[1].p[0] - d[0].p[0];
let h = d[2].p[1] - d[0].p[1];
ctx.fillStyle = colorScale(d[0].w);
ctx.fillRect (x,y,w,h);
}
}
Insert cell
// Draws the boundary of vertex list vlist onto a canvas using context ctx
function drawPolygon (ctx,vlist) {
let faces = vlist.faces();
for (let f of vlist.rotAxesClock().faces()) faces.push(f.rotAxesCounter())
// Draw the polygon
ctx.beginPath();
for (let d of faces) {
let x1 = d[0].p[0];
let y1 = d[0].p[1];
let x2 = d[1].p[0];
let y2 = d[1].p[1];
ctx.moveTo(x1,y1);
ctx.lineTo(x2,y2);
}
ctx.stroke();
}
Insert cell

// Converts a JSON representing a VList to a VList object
jsonToVlist = json =>
Object.assign(new VList, JSON.parse(json).map(obj => Object.assign (new Vertex, obj)))

Insert cell

class SquareArrangement {

constructor (center = [0,0], options = {heuristic:"first",
metric:"euclidean",
closeFreq : 1,
closeFactor:0.5}) {
this.center = center;
this.squares = [];
this.polygon = new VList();
Object.assign(this,options);
this.distance = this.metric == "chessboard" ? (
(p,q) => Math.max(Math.abs(p[0]-q[0]),Math.abs(p[1]-q[1]))
) : this.metric == "euclidean" ? (
(p,q) => Math.sqrt((p[0]-q[0])**2+(p[1]-q[1])**2)
): this.metric == "mahalanobis" ? (
mahalanobis
) : (
(p,q) => Math.abs(p[0]-q[0])+Math.abs(p[1]-q[1])
);
}
closePolygon (amount) {
this.polygon = topo(topo(this.polygon,amount),-amount)
}

addSquare (area) {
let [cx,cy] = this.center;
let side = Math.sqrt(area);
let d = side/Math.sqrt(2);
let s = undefined;
let poly;
if (this.squares.length == 0) {
s = square ([cx-d,cy-d],side)
}
else {
let distToCenter = Number.MAX_VALUE;
let smallestPerimeter;
let vtx = [...this.polygon].map(v=>{v.dist = this.distance(v.p,this.center); return v});
vtx.sort ((a,b) => a.dist - b.dist);
let rlist = new RectList(this.polygon)
for (let v of vtx) {
let [x,y] = v.p;
if (v.dist > distToCenter+d) continue; // Worse than the best so far
for (let [sx,sy,sign] of [[x,y,-1],[x-side,y,+1],[x,y-side,+1],[x-side,y-side,-1]]) {
if (Math.sign(v.w) != sign) continue; // Wrong sign
let candidate = square ([sx,sy],side)
let [scx,scy] = [sx+d,sy+d]; // Center of square
if (rlist.pointIntersection([scx,scy])) continue; // Center inside polygon
if (rlist.rectIntersection(candidate)) continue; // Polygon intersects square
let dist = this.distance([scx,scy],[cx,cy]);
if (!s || dist < distToCenter) {
s = candidate;
distToCenter = dist;
}
}
if (this.heuristic == "first" && s) break;
}
}
if (s == undefined) throw "Something went wrong : could not find a place for square";
this.squares.push (s);
this.polygon = union(this.polygon,s);
let factor = d*this.closeFactor;
if (this.squares.length % config.closeFreq == 0) this.closePolygon(factor);
}
}
Insert cell
Insert cell
import {Vertex, VList} from "@esperanc/vertex-lists"
Insert cell
d3 = require("d3@5")
Insert cell
colorScale = d3.scaleOrdinal(d3.schemeCategory10)
Insert cell
createIntervalTree = require('https://bundle.run/interval-tree-1d@1.0.3')
Insert cell
import {tabbed,paged,combo} from "@esperanc/aggregated-inputs"
Insert cell
import {select,button,slider} from "@jashkenas/inputs"
Insert cell
// Used to style one of Jeff Ashkenas input components
function styleInput(form,style) {
let input = form.querySelector("input");
for (let s in style) {
input.style[s] = style[s];
}
}
Insert cell
// Makes a slider with 80px width
function shortSlider (...args) {
let s = slider(...args);
styleInput(s,{width:"80px"});
return s;
}
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more