31:T411,toeplitz = { let min = 0; let solution = []; let candidates = []; let steps = 0; let k; for (let i = 0; i < points.length; i++) { for (let j = 0; j < i; j++) { k = (i * (i + 1) + (j + 1)) / 2; const a = points[i]; const b = points[j]; const dist2 = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2; if (dist2 <= min) continue; const m = [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2]; // center const n = [(b[1] - a[1]) / 2, (a[0] - b[0]) / 2]; // normal const c = [m[0] - n[0], m[1] - n[1]]; const d = [m[0] + n[0], m[1] + n[1]]; if (steps++ % 100000 === 0) yield { test: [a, c, b, d], solution, candidates, dist: Math.sqrt(min), k }; const t = testSquare(a, c, b, d); if (t) { min = dist2; candidates.push((solution = t)); yield { test: t, solution: t, candidates, dist: Math.sqrt(min), k }; } } } yield { test: [], solution, candidates, dist: Math.sqrt(min) }; }32:[] 2f:{"title":"Largest Inscribed Square","cells":[{"id":0,"value":"# Largest Inscribed Square\n\nThis notebook computes the largest square that has its four vertices on a curve. Our algorithm is rather brute-force: first, we sample the curve at a constant interval (${sample}px) along its length. Then, for each pair of points (A,B), we compute the two other vertices of the square with diagonal AB, then look up these vertices in the list of points (indexed in a [quadtree](https://github.com/d3/d3-quadtree)). This finds an approximate solution in ${tex`\\mathcal{O}(n^2\\log{n})`}, with ${tex`n`} the number of sampled points. For an application, see the [World of squares](https://observablehq.com/@fil/world-of-squares).\n","pinned":false,"hidden":false,"mode":"md"},{"id":163,"value":"viewof replay = html`