Computer Graphics & Visualization @ufrj.br
Published
Edited
Jan 2, 2022
Importers
3 stars
margin = 20
piece = letterImage
pieceImageData = binarizeImageData(getImageData(piece), 128)
function drawBoxes(ctx, boxes) {
ctx.strokeStyle = "black";
for (let b of boxes) {
let size = b.size();
ctx.fillRect(b.min.x, b.min.y, size.x, size.y);
ctx.strokeRect(b.min.x, b.min.y, size.x + 0.01, size.y + 0.01);
}
}
pieceRaTree = new RA(piecePoints)
pieceRaTreeHeight = pieceRaTree.height()
pieceRaCutTree = pieceRaTree.cutTree(raTreeCut).approxTree(nodeFillRate)
piecePoints = imageDataPoints(pieceImageData)
groundPoints = imageDataPoints(getImageData(zoomedShape))
//
// Rasterizes a rect pixel by pixel in an imageData object.
// Each pixel in the rect has its alpha set 255.
//
function rasterizeRect(imageData, x, y, w, h) {
const W = imageData.width;
for (let j = 0; j < h; j++) {
let k = (j + y) * W + x;
for (let i = 0; i < w; i++) {
imageData.data[(k + i) * 4 + 3] = 255;
}
}
}
function rasterizeBoxes(boxes, width, height, zoom) {
let raster = new ImageData(width, height);
for (let { min, max } of boxes) {
min = min.scale(zoom);
max = max.scale(zoom).add(Vec(zoom, zoom));
rasterizeRect(raster, min.x, min.y, max.x - min.x, max.y - min.y);
}
return raster;
}
//
// Draws two images with XOR, so black pixels are the different pixels
//
function errorImage(a, b) {
let ctx = DOM.context2d(a.width, a.height, 1);
ctx.canvas.style.cssText = `
image-rendering: crisp-edges;
image-rendering: pixelated;
-webkit-image-rendering: pixelated;
-webkit-image-rendering: crisp-edges;
`;
ctx.imageSmoothingEnabled = false;
ctx.drawImage(a, 0, 0);
ctx.globalCompositeOperation = "xor";
ctx.drawImage(b, 0, 0);
return ctx.canvas;
}
//
// Returns an image representing a text
//
function textImage(
text,
fontSize = 120,
fontFamily = "serif",
fontVariant = "normal",
zoom = 1
) {
let ctx = DOM.context2d(2 + fontSize * zoom, 2 + fontSize * zoom, 1);
ctx.scale(zoom, zoom);
ctx.textBaseline = "top";
const font = (ctx.font = `${fontVariant} ${fontSize}px ${fontFamily}`);
let w = ctx.measureText(text).actualBoundingBoxRight;
if (w > fontSize) {
ctx = DOM.context2d(2 + w * zoom, 2 + fontSize * zoom, 1);
ctx.scale(zoom, zoom);
ctx.textBaseline = "top";
ctx.font = font;
}
ctx.fillText(text, 0, 0);
return ctx.canvas;
}
//
// Retrieves an ImageData object associated with an image
//
function getImageData(image) {
let ctx = DOM.context2d(image.width, image.height, 1);
ctx.drawImage(image, 0, 0);
return ctx.getImageData(0, 0, image.width, image.height);
}
//
// Binarizes the alpha channel of an ImageData object. Pixels with alpha >= alphaThreshold are mapped to 255, otherwise to 0
//
function binarizeImageData(imageData, alphaThreshold = 128) {
let data = imageData.data;
for (let i = 0; i < data.length; i += 4) {
data[i + 3] = (data[i + 3] >= alphaThreshold) * 255;
}
return imageData;
}
gridPoints = useImageRACheckbox.length > 0
//
// A Rectangle approximation tree
//
RA = {
// Splits a point set wrt a vertical halfplane
function splitX(points, x) {
const inside = [],
outside = [];
for (let p of points) {
if (p.x <= x) inside.push(p);
else outside.push(p);
}
return { inside, outside };
}
// Splits a point set wrt a horizontal halfplane
function splitY(points, y) {
const inside = [],
outside = [];
for (let p of points) {
if (p.y <= y) inside.push(p);
else outside.push(p);
}
return { inside, outside };
}
// how to split a length in the middle? If gridPoints, makes sure to use integer division
const half = gridPoints ? (x) => ~~(x / 2) : (x) => x / 2;
class RA {
constructor(points = [], maxLevel = 20) {
this.box = new MBR(...points);
this.points = points;
this.left = this.right = null;
if (points.length == 0) return this; // An empty tree
const bsize = this.box.size();
if (
maxLevel == 0 ||
Math.max(bsize.x, bsize.y) <= Number.EPSILON ||
(gridPoints && (bsize.x + 1) * (bsize.y + 1) == points.length)
)
return;
let { inside, outside } =
bsize.x > bsize.y
? splitX(points, this.box.min.x + half(bsize.x))
: splitY(points, this.box.min.y + half(bsize.y));
this.left = new RA(inside, maxLevel - 1);
this.right = new RA(outside, maxLevel - 1);
}
// Height (number of levels) of the tree
height() {
if (!this.left) return 0;
return 1 + Math.max(this.left.height(), this.right.height());
}
// Iterates over internal nodes at level l or leaves if at shallower levels
*approximation(l) {
if (l == 0 || !this.left) yield this;
else {
yield* this.left.approximation(l - 1);
yield* this.right.approximation(l - 1);
}
}
// Return this tree cut at level l
cutTree(l) {
let result = new RA();
result.box = this.box;
result.points = this.points;
if (l > 0 && this.left) {
result.left = this.left.cutTree(l - 1);
result.right = this.right.cutTree(l - 1);
}
return result;
}
// Return this tree simplified so as to ignore splits
// for approximately full nodes
approxTree(fillRate = 0.99) {
let result = new RA();
result.box = this.box;
result.points = this.points;
const bsize = this.box.size();
if (
this.left &&
(bsize.x + 1) * (bsize.y + 1) * fillRate >= result.points.length
) {
result.left = this.left.approxTree(fillRate);
result.right = this.right.approxTree(fillRate);
}
return result;
}
// Returns the distance to a point p
distance(p) {
let best = null;
let bestDist = Number.POSITIVE_INFINITY;
this.distanceSteps = 0;
const traverse = (node) => {
if (bestDist == 0) return;
this.distanceSteps++;
if (!node.left) {
let d = node.box.pointDist(p);
if (d < bestDist) [best, bestDist] = [node, d];
return;
}
let dleft = node.left.box.pointDist(p);
let dright = node.right.box.pointDist(p);
if (dleft < dright) {
if (dleft < bestDist) traverse(node.left);
if (dright < bestDist) traverse(node.right);
} else {
if (dright < bestDist) traverse(node.right);
if (dleft < bestDist) traverse(node.left);
}
};
traverse(this);
return bestDist;
}
}
return RA;
}
//
// Returns an array of points from the opaque pixels in an ImageData object
//
function imageDataPoints(imgData) {
let { width, height } = imgData;
let points = [];
let i = 0;
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
if (imgData.data[i + 3] > 127) points.push(Vec(x, y));
i += 4;
}
}
return points;
}
import { Vec, Curve, MBR } from "@esperanc/2d-geometry-utils"
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.
