2e:null 2f:["$","title",null,{"children":"Point-Box Collision | Mike Bostock | Observable"}] 34:T5e4,{ const svg = d3.select(DOM.svg(width, height)); svg.append("rect") .attr("stroke", "black") .attr("fill", "none") .attr("x", b.x) .attr("y", b.y) .attr("width", b.width) .attr("height", b.height); const line = svg.append("g") .attr("stroke", "red") .selectAll("line") .data([0, 1, 2, 3]) .enter().append("line"); const point = svg.append("circle") .attr("r", 5) .attr("fill", "red") .attr("cursor", "move") .attr("stroke", "transparent") .attr("stroke-width", 20) .attr("pointer-events", "all") .call(d3.drag() .subject(() => (viewof p.value)) .on("drag", dragged)); function dragged(event) { viewof p.value = {x: event.x, y: event.y}; } function update() { const {x, y} = viewof p.value; const distances = [ [x, b.y, y - b.y], [b.x + b.width, y, b.x + b.width - x], [x, b.y + b.height, b.y + b.height - y], [b.x, y, x - b.x] ]; line.data(distances) .attr("stroke", d => d[2] >= 0 ? "red" : "none") .attr("x1", d => d[0]) .attr("y1", d => d[1]) .attr("x2", x) .attr("y2", y); point .attr("fill", distances.some(d => d[2] < 0) ? "black" : "red") .attr("cx", x) .attr("cy", y); } update(); viewof p.addEventListener("input", update); invalidation.then(() => viewof p.removeEventListener("input", update)); return svg.node(); }35:T6ed,{ const svg = d3.select(DOM.svg(width, height)); svg.append("rect") .attr("stroke", "black") .attr("fill", "none") .attr("x", b.x) .attr("y", b.y) .attr("width", b.width) .attr("height", b.height); const box = svg.append("rect") .attr("stroke", "blue") .attr("fill", "blue") .attr("fill-opacity", 0.1); const point = svg.append("circle") .attr("r", 5) .attr("fill", "red") .attr("cursor", "move") .attr("stroke", "transparent") .attr("stroke-width", 20) .attr("pointer-events", "all") .call(d3.drag() .subject(() => (viewof p.value)) .on("drag", dragged)); function dragged(event) { viewof p.value = {x: event.x, y: event.y}; } function update() { const {x, y} = viewof p.value; const top = y - b.y; const right = b.x + b.width - x; const bottom = b.y + b.height - y; const left = x - b.x; let minValue = top, minSide = TOP; if (right < minValue) minValue = right, minSide = RIGHT; if (bottom < minValue) minValue = bottom, minSide = BOTTOM; if (left < minValue) minValue = left, minSide = LEFT; let o = b; if (minValue > 0) switch (minSide) { case TOP: o = offset(b, {dy: minValue}); break; case RIGHT: o = offset(b, {dx: -minValue}); break; case BOTTOM: o = offset(b, {dy: -minValue}); break; case LEFT: o = offset(b, {dx: minValue}); break; } point.attr("cx", x).attr("cy", y); box.attr("x", o.x).attr("y", o.y) .attr("width", o.width).attr("height", o.height); } update(); viewof p.addEventListener("input", update); invalidation.then(() => viewof p.removeEventListener("input", update)); return svg.node(); }36:[] 32:{"id":"958f9a106f8808eb","slug":"point-box-collision","title":"Point-Box Collision","thumbnail":"665dcd4c00dabaeb0710e2d209ab73e68e039afaa637f046bfee69dfe033051c","access_level":"public","create_time":"$D2018-10-10T15:33:59.963Z","update_time":"$D2026-06-16T17:45:09.307Z","view_time":null,"first_public_time":"$D2018-10-10T16:48:48.086Z","has_unpublished_edits":null,"fork":false,"stars":7,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":310,"publish_version":310,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"6d94bdd16890def0","slug":"geometry","title":"Geometry","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"type":"notebook","body":{"title":"Point-Box Collision","cells":[{"id":0,"value":"md`# Point-Box Collision\n\nSay you have a point ${tex`p`} possibly inside an axis-aligned box ${tex`b`} . How do you move the box by the minimum amount so that it no longer contains the point? (You can drag the point ${tex`p`} below.)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"{\n const svg = d3.select(DOM.svg(width, height));\n\n svg.append(\"rect\")\n .attr(\"stroke\", \"black\")\n .attr(\"fill\", \"none\")\n .attr(\"x\", b.x)\n .attr(\"y\", b.y)\n .attr(\"width\", b.width)\n .attr(\"height\", b.height);\n\n const point = svg.append(\"circle\")\n .attr(\"r\", 5)\n .attr(\"fill\", \"red\")\n .attr(\"cursor\", \"move\")\n .attr(\"stroke\", \"transparent\")\n .attr(\"stroke-width\", 20)\n .attr(\"pointer-events\", \"all\")\n .call(d3.drag()\n .subject(() => (viewof p.value))\n .on(\"drag\", dragged));\n\n function dragged(event) {\n viewof p.value = {x: event.x, y: event.y};\n }\n\n function update() {\n const {x, y} = viewof p.value;\n point.attr(\"cx\", x).attr(\"cy\", y);\n }\n\n update();\n viewof p.addEventListener(\"input\", update);\n invalidation.then(() => viewof p.removeEventListener(\"input\", update));\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":137,"value":"md`Let’s represent the point ${tex`p`} and the box ${tex`b`} as objects:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"value":"p","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"md`First we’ll compute the [signed distances](https://en.wikipedia.org/wiki/Signed_distance_function) between the point and each of the four sides of the box. Since the box is axis-aligned, this is simple subtraction. If any of these signed distances is negative, the point is outside the box.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"top = p.y - b.y","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"right = b.x + b.width - p.x","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"bottom = b.y + b.height - p.y","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"left = p.x - b.x","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"md`Now we need to determine which side is closest: we iterate over each of the four sides, comparing each distance to the minimum distance seen so far, and recording the corresponding side.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"closest = {\n let value = top, side = TOP;\n if (right < value) value = right, side = RIGHT;\n if (bottom < value) value = bottom, side = BOTTOM;\n if (left < value) value = left, side = LEFT;\n if (value < 0) return null;\n return {value, side};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"md`Next we’ll need a function to compute a new box ${tex`o`} that is offset from the given box ${tex`b`} by a vector ${tex`\\langle \\delta x, \\delta y \\rangle`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"function offset({x, y, width, height}, {dx = 0, dy = 0}) {\n return {x: x + dx, y: y + dy, width, height};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"md`Using this function, we compute the offset box ${tex`o`}. If the closest side is the top, we push the box down; if the closest side is the bottom, we push the box up; and so on.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"o = {\n if (closest === null) return b;\n switch (closest.side) {\n case TOP: return offset(b, {dy: closest.value});\n case RIGHT: return offset(b, {dx: -closest.value});\n case BOTTOM: return offset(b, {dy: -closest.value});\n case LEFT: return offset(b, {dx: closest.value});\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"md`Try dragging the point ${tex`p`} around to see how it affects the offset box ${tex`o`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"md`---\n\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":231,"value":"viewof p = new View({x: width / 2, y: 150})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"b = ({x: width / 5, y: 120, width: width / 2, height: 100})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"TOP = Symbol(\"top\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"RIGHT = Symbol(\"right\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"BOTTOM = Symbol(\"bottom\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"LEFT = Symbol(\"left\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"height = 300","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":214,"value":"import {View} from \"@mbostock/synchronized-views\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 33:"$32:body"