Visualization toolmaker. Founder @observablehq. Creator @d3. Former @nytgraphics. Pronounced BOSS-tock.
Circular SegmentPacking Circles inside a RectangleRadical AxisPoint-Box CollisionUrquhart GraphRandom Points on a SphereSpherical Fibonacci LatticeApollonian GasketSoddy Circles19-CircleCircle Offset Along LineClosest Point on LineCircumcircleTangent to Two CirclesCircle Tangent to Three LinesAngle Bisector of Two LinesConvex Polygon Incircle
Rounded Convex Polygon
{
const context = DOM.context2d(width, height);
context.beginPath();
context.moveTo(...polygon[0]);
for (let i = 1, n = polygon.length - 1; i < n; ++i) context.lineTo(...polygon[i]);
context.closePath();
context.strokeStyle = "black";
context.stroke();
context.beginPath();
drawRoundedPolygon(context, polygon, radius);
context.strokeStyle = "red";
context.stroke();
return context.canvas;
}
function drawRoundedPolygon(context, points, r) {
points = cleanPolygon(points);
// The rounding radius can’t be bigger than the polygon’s incircle.
// TODO Abort the search for the incircle if one is found larger than r.
const [cx, cy, cr] = polygonIncircle(points);
r = Math.min(r, cr);
if (r <= 0) return;
// Build a linked list from the array of vertices so we can splice.
let n = points.length - 1, p0, p1, p2, p3;
points = points.slice(1).map(([x, y]) => [x, y]);
p1 = points[n - 2], p2 = points[n - 1];
for (let i = 0; i < n; ++i) {
p0 = p1, p1 = p2, p2 = points[i];
p1.previous = p0;
p1.next = p2;
}
// TODO do we need to make all these extra passes?
p3 = p2.next;
for (let i = 0; i <= n; ++i) {
p0 = p1, p1 = p2, p2 = p3, p3 = p3.next;
const t012 = cornerTangent(p0, p1, p2, r);
const t123 = 1 - cornerTangent(p3, p2, p1, r);
// If the following corner’s tangent is before this corner’s tangent,
// replace p1 and p2 with the intersection of the lines 01 and 23.
if (!(t012 + 1e-6 < t123)) {
p2 = p0.next = p3.previous = lineLineIntersect(p0, p1, p2, p3);
p2.previous = p0;
p2.next = p3;
p3 = p2;
p2 = p3.previous;
p1 = p2.previous;
p0 = p1.previous;
if (--n < 3) break;
i = 0;
}
}
// If we removed too many points, just draw the previously computed incircle.
if (n < 3) {
context.moveTo(cx + cr, cy);
context.arc(cx, cy, cr, 0, 2 * Math.PI);
return;
}
// Draw the rounded polygon, compting the corner tangents.
for (let i = 0, moved = false; i <= n; ++i) {
p0 = p1, p1 = p2, p2 = p3, p3 = p3.next;
const t012 = cornerTangent(p0, p1, p2, r);
const t123 = 1 - cornerTangent(p3, p2, p1, r);
const x21 = p2[0] - p1[0], y21 = p2[1] - p1[1];
const x4 = p1[0] + t012 * x21, y4 = p1[1] + t012 * y21;
const x5 = p1[0] + t123 * x21, y5 = p1[1] + t123 * y21;
if (moved) context.arcTo(p1[0], p1[1], x4, y4, r);
else moved = true, context.moveTo(x4, y4);
context.lineTo(x5, y5);
}
}
// Remove coincident points.
function cleanPolygon(polygon) {
const n = polygon.length - 1;
let p0, p1 = polygon[n - 1];
const cleaned = [p1];
for (let i = 0; i < n; ++i) {
p0 = p1, p1 = polygon[i];
const dx = p1[0] - p0[0];
const dy = p1[1] - p0[1];
if (dx * dx + dy * dy > 1e-6) cleaned.push(p1);
else p1 = p0;
}
return cleaned;
}
function polygonIncircle(polygon) {
let circle = [NaN, NaN, 0];
for (let i = 0, n = polygon.length - 1; i < n; ++i) {
const pi0 = polygon[i], pi1 = polygon[i + 1];
for (let j = i + 1; j < n; ++j) {
const pj0 = polygon[j], pj1 = polygon[j + 1];
search: for (let k = j + 1; k < n; ++k) {
const pk0 = polygon[k], pk1 = polygon[k + 1];
const c = circleTangent(pi0, pi1, pj0, pj1, pk0, pk1);
if (!c || !(c[2] > circle[2])) continue;
for (let l = 0; l < n; ++l) {
if (l === i || l === j || l === k) continue;
const d = pointLineDistance(c, polygon[l], polygon[l + 1]);
if (d + 1e-6 < c[2]) continue search;
}
circle = c;
}
}
}
return circle;
}
polygon = {
replay;
const points = Array.from({length: 15}, () => [
(Math.random() * 3 + 1) / 5 * width,
(Math.random() * 3 + 1) / 5 * height
]);
const hull = d3.polygonHull(points);
return hull.concat([hull[0].slice()]).reverse(); // Closed, clockwise.
}
// Given a circle of radius r that is tangent to the line segments 01 and 12,
// returns the parameter t of the tangent along the line segment 12.
function cornerTangent([x0, y0], [x1, y1], [x2, y2], r) {
const theta = innerAngle([x0, y0], [x1, y1], [x2, y2]);
const x21 = x2 - x1, y21 = y2 - y1;
const l21 = Math.sqrt(x21 * x21 + y21 * y21);
const l14 = r / Math.tan(theta / 2);
return l14 / l21;
}
// Returns the angle between segments 01 and 12.
function innerAngle([x0, y0], [x1, y1], [x2, y2]) {
const x01 = x0 - x1, y01 = y0 - y1, l01_2 = x01 * x01 + y01 * y01;
const x12 = x1 - x2, y12 = y1 - y2, l12_2 = x12 * x12 + y12 * y12;
const x02 = x0 - x2, y02 = y0 - y2, l02_2 = x02 * x02 + y02 * y02;
return Math.acos((l12_2 + l01_2 - l02_2) / (2 * Math.sqrt(l12_2 * l01_2)));
}
function lineLineIntersect([x0, y0], [x1, y1], [x2, y2], [x3, y3]) {
const x02 = x0 - x2, y02 = y0 - y2;
const x10 = x1 - x0, y10 = y1 - y0;
const x32 = x3 - x2, y32 = y3 - y2;
const t = (x32 * y02 - y32 * x02) / (y32 * x10 - x32 * y10);
return [x0 + t * x10, y0 + t * y10];
}
function circleTangent(p0, p1, p2, p3, p4, p5) {
const b0 = lineLineBisect(p0, p1, p3, p2);
const b1 = lineLineBisect(p2, p3, p5, p4);
if (!b0 || !b1) return; // Parallel!
const i = lineLineIntersect(...b0, ...b1);
return [...i, pointLineDistance(i, p0, p1)];
}
function pointLineDistance([x0, y0], [x2, y2], [x1, y1]) {
const x21 = x2 - x1, y21 = y2 - y1;
return (y21 * x0 - x21 * y0 + x2 * y1 - y2 * x1) / Math.sqrt(y21 * y21 + x21 * x21);
}
function lineLineBisect([x0, y0], [x1, y1], [x2, y2], [x3, y3]) {
const x02 = x0 - x2, y02 = y0 - y2;
const x10 = x1 - x0, y10 = y1 - y0;
const x32 = x3 - x2, y32 = y3 - y2;
const l = y32 * x10 - x32 * y10;
if (Math.abs(l) < 1e-3) return; // Parallel!
const l10 = Math.sqrt(x10 ** 2 + y10 ** 2);
const l32 = Math.sqrt(x32 ** 2 + y32 ** 2);
const ti = (x32 * y02 - y32 * x02) / l;
const xi = x0 + ti * x10, yi = y0 + ti * y10;
return [[xi, yi], [xi + x10 / l10 + x32 / l32, yi + y10 / l10 + y32 / l32]];
}
height = 600
d3 = require("d3-polygon@1")
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.
