2b:null 2c:["$","title",null,{"children":"Line segment intersection | Torben Jansen | Observable"}] 31:Te4f,figure = { const viewbox = [0, 0, width, height], box = [margin, margin, width - margin, height - margin]; const svg = d3.select(DOM.svg(width, height)) .style('max-width', '100%') .style('height', 'auto'); svg.append("rect") .attr("x", margin) .attr("y", margin) .attr("width", width - margin * 2) .attr("height", height - margin * 2) .attr("fill", "none") .attr("stroke", "black") .attr("stroke-dasharray", "4 2"); // lines const line = svg.selectAll(".lines") .data(viewof data.value) .enter().append("line") .attr('stroke', "black"); // handles const point = svg.append("g") .selectAll(".points") .data(viewof data.value.reduce((acc, line) => acc.concat(line), [])) .enter().append("g") .style("cursor", "move") .style("pointer-events", "all") .on("mouseenter", (d, i, g) => hover(d, i, g, true)) .on("mouseleave", (d, i, g) => hover(d, i, g, false)) .call(d3.drag() .subject(([x, y]) => ({x, y})) .on("drag", drag)); const dot = point.append('circle').attr("r", 3) const overlay = point.append("circle") .classed("overlay", true) .style("opacity", 0.0) .attr("r", 8); // box intersections const intersection = svg.selectAll(".intersections") .data(viewof data.value) .enter().append("g"); const i1 = intersection.append("circle").attr("r", 4).attr("fill", "lightgray").attr("stroke", "black"); const i2 = intersection.append("circle").attr("r", 4).attr("fill", "white").attr("stroke", "black"); // line intersection const i3 = viewof data.value.length > 1 ? svg.append("circle").attr("r", 4).attr("fill", "red").attr("stroke", "black"): undefined; // event handling function drag(d) { d[0] = Math.max(0, Math.min(width, d3.event.x)); d[1] = Math.max(0, Math.min(height, d3.event.y)) viewof data.value = viewof data.value; // dispatch input event } function hover(d, i, g, hovering) { d3.select(g[i]).select(".overlay").style("opacity", hovering ? 0.1 : 0); } function update() { const intersectionVBox = viewof data.value.map((d, i) => intersectBox(viewof data.value[i], viewbox)); line .attr("x1", (d, i) => intersectionVBox[i][0][0]) .attr("y1", (d, i) => intersectionVBox[i][0][1]) .attr("x2", (d, i) => intersectionVBox[i][1][0]) .attr("y2", (d, i) => intersectionVBox[i][1][1]); const intersectionBox = viewof data.value.map((d, i) => intersectBox(viewof data.value[i], box)); i1 .attr("opacity", (d, i) => intersectionBox[i][0] ? 1 : 0) .attr("cx", (d, i) => intersectionBox[i][0] ? intersectionBox[i][0][0] : null) .attr("cy", (d, i) => intersectionBox[i][0] ? intersectionBox[i][0][1] : null); i2 .attr("opacity", (d, i) => intersectionBox[i][1] ? 1 : 0) .attr("cx", (d, i) => intersectionBox[i][1] ? intersectionBox[i][1][0] : null) .attr("cy", (d, i) => intersectionBox[i][1] ? intersectionBox[i][1][1] : null); const intersectionLine = i3 ? intersect(viewof data.value[0], viewof data.value[1]) : undefined; intersectionLine && i3 .attr("opacity", (d, i) => intersectionLine ? 1 : 0) .attr("cx", (d, i) => intersectionLine ? intersectionLine[0] : null) .attr("cy", (d, i) => intersectionLine ? intersectionLine[1] : null); point.attr("transform", d => `translate(${d[0]} ${d[1]})`); } // initialize update(); viewof data.addEventListener("input", update); return Generators.disposable(svg.node(), () => { viewof data.removeEventListener("input", update); }); }32:T695, ansatz = md`--- A line in the plane is often defined as the [set](https://en.wikipedia.org/wiki/Set_(mathematics)) of points whose coordinates satisfy a given linear equation, in our case the [two-point-form](https://en.wikipedia.org/wiki/Linear_equation#Two-point_form), with line ${tex`L_{1}`} being defined by two distinct points ${tex`(x_{1}, y_{1})`} and ${tex`(x_{2}, y_{2})`}, and line ${tex`L_{2}`} being defined by two distinct points ${tex`(x_{3}, y_{3})`} and ${tex`(x_{4}, y_{4})`}. Here are the equations for line ${tex`L_{1}`} and line ${tex`L_{2}`}: ${tex.block`y - y_{1} = \dfrac{y_{2} - y_{1}}{x_{2} - x_{1}}(x - x_{1}),`} ${tex.block`y - y_{3} = \dfrac{y_{4} - y_{3}}{x_{4} - x_{3}}(x - x_{3})`} When line ${tex`L_1`} and line ${tex`L_2`} intersect at a point ${tex`(x, y)`}, the equations are equal, because they resolve to the same point. To find the intersection point of line ${tex`L_{1}`} and line ${tex`L_{2}`} we could than write ${tex.block`\dfrac{y_{2} - y_{1}}{x_{2} - x_{1}}(x - x_{1}) + y_{1} = \dfrac{y_{4} - y_{3}}{x_{4} - x_{3}}(x - x_{3}) + y_{3}`} and solve the equation. But note that the intersection point of two [infinitely](https://en.wikipedia.org/wiki/Infinity) long lines is defined by the *given points*, rather than the [line segments](https://en.wikipedia.org/wiki/Line_segment) *between the points*, and can produce an intersection point beyond the lengths of the line segments. In order to find the position of the intersection in respect to the line segments, we define the lines ${tex`L_{1}`} and ${tex`L_{2}`} in terms of first degree [Bézier](https://en.wikipedia.org/wiki/B%C3%A9zier_curve) parameters instead.`33:T7ec,{ const svg = d3.select(DOM.svg(640, 220)) .style('max-width', '100%') .style('height', 'auto'); const interpolateX = d3.interpolateNumber(40, 600); const interpolateY = d3.interpolateNumber(40, 180); const format = d3.format(".3f") svg.append("line") .attr("x1", 40) .attr("y1", 40) .attr("x2", 600) .attr("y2", 180) .attr("stroke", "black") .attr("stroke-width", 1); svg.append("line") .attr("x1", 40) .attr("y1", 40) .attr("x2", 40) .attr("y2", 180) .attr("stroke", "black") .attr("stroke-width", 1) .attr("stroke-dasharray", "4 2"); svg.append("line") .attr("x1", 40) .attr("y1", 180) .attr("x2", 600) .attr("y2", 180) .attr("stroke", "black") .attr("stroke-width", 1) .attr("stroke-dasharray", "4 2"); svg.append("circle").attr("r", 4).attr("cx", 40).attr("cy", 40).attr("fill", "black").attr("stroke", "black"); svg.append("circle").attr("r", 4).attr("cx", 600).attr("cy", 180).attr("fill", "black").attr("stroke", "black"); svg.append("circle") .attr("r", 4) .attr("cx", interpolateX(t)) .attr("cy", 180) .attr("fill", "white") .attr("stroke", "black"); svg.append("text") .attr("x", interpolateX(t)) .attr("y", 180) .attr("dy", "1.5em") .attr("text-anchor", "middle") .attr("font-family", "sans-serif") .attr("font-size", 10) .text(format(t)) svg.append("circle") .attr("r", 4) .attr("cx", 40) .attr("cy", interpolateY(t)) .attr("fill", "white") .attr("stroke", "black"); svg.append("text") .attr("x", 40) .attr("y", interpolateY(t)) .attr("dx", "-0.85em") .attr("dy", "0.35em") .attr("text-anchor", "end") .attr("font-family", "sans-serif") .attr("font-size", 10) .text(format(t)) svg.append("circle") .attr("r", 4) .attr("cx", interpolateX(t)) .attr("cy", interpolateY(t)) .attr("fill", "#f30") .attr("stroke", "black"); return svg.node(); }34:Tdce,solution = md`--- When line ${tex`L_1`} and line ${tex`L_2`} intersect at some value of ${tex`t`} and some value of ${tex`u`}, the equations are equal, because they resolve to the same point. ${tex.block`L_1=L_2`} ${tex.block` \begin{pmatrix} x_1\\ y_1 \end{pmatrix} + t \begin{pmatrix} x_2 - x_1 \\ y_2 - y_1 \end{pmatrix} = \begin{pmatrix} x_3\\ y_3 \end{pmatrix} + u \begin{pmatrix} x_4 - x_3 \\ y_4 - y_3 \end{pmatrix} `} This gives us a [system of linear equations](https://en.wikipedia.org/wiki/System_of_linear_equations) with two unknowns ${tex`t`} and ${tex`u`}. ${tex.block`a_x + tb_x = c_x + ud_x,`} ${tex.block`a_y + tb_y = c_y + ud_y`} There are several ways to solve systems of linear equations, we'll use [matrices](https://en.wikipedia.org/wiki/Matrix_(mathematics)), since they make our life a lot easier. To do so we have to transform the equations to the general form: ${tex.block`b_xt - d_xu = c_x - a_x,`} ${tex.block`b_yt - d_yu = c_y - a_y`} Then we can fill the matrices: ${tex.block` \\ \begin{bmatrix} b_x & -d_x \\ b_y & -d_y \end{bmatrix} \begin{bmatrix} t \\ u \end{bmatrix} = \begin{bmatrix} c_x - a_x\\ c_y - a_y \end{bmatrix} \\ `}
Our matrices are in the form ${tex`AX = B`} but if we want to find ${tex`X`} we need them in the form ${tex`X = A^{-1}B`}. In other words: we can find the values of ${tex`t`} and ${tex`u`} (the ${tex`X`} matrix) by multiplying the [inverse](https://en.wikipedia.org/wiki/Invertible_matrix) of the ${tex`A`} matrix by the ${tex`B`} matrix. Sounds difficult? Don't worry, it's easier than you think. For a 2x2 matrix like ours the inverse simply is: ${tex.block` \begin{bmatrix} \color{darkblue}a & \color{darkred}b \\ \color{darkgreen}c & \color{darkorange}d \end{bmatrix}^{-1} = \dfrac{1}{\color{darkblue}a\color{darkorange}d \color{black} - \color{darkred}b\color{darkgreen}c} \begin{bmatrix} \color{darkorange}d & - \color{darkred}b \\ -\color{darkgreen}c & \color{darkblue}a \end{bmatrix} \\ `} After the inversion all that is left to do is to multiply the matrices and we're done. So let's go ahead and do that: ${tex.block` \begin{aligned} \\ \begin{bmatrix} t \\ u \end{bmatrix} &= \begin{bmatrix} b_x & -d_x \\ b_y & -d_y \end{bmatrix}^{-1} \begin{bmatrix} c_x - a_x\\ c_y - a_y \end{bmatrix} \\ \\ &= \dfrac{1}{b_x(-d_y) - (-d_x)b_y} \begin{bmatrix} -d_y & d_x \\ -b_y & b_x \end{bmatrix} \begin{bmatrix} c_x - a_x\\ c_y - a_y \end{bmatrix} \\ \\ &= \dfrac{1}{b_x(-d_y) - (-d_x)b_y} \begin{bmatrix} -d_y(c_x - a_x) + d_x(c_y - a_y)\\ -b_y(c_x - a_x) + b_x(c_y - a_y) \end{bmatrix} \end{aligned} \\ `}
Now replace ${tex`a`}, ${tex`b`}, ${tex`c`} and ${tex`d`} with the values from above, et voilà! ${tex.block` \begin{aligned} \\ t &= \dfrac{(x_1 - x_3)(y_3 - y_4) - (y_1 - y_3)(x_3 - x_4)} {(x_1 - x_2)(y_3 - y_4) - (y_1 - y_2)(x_3 - x_4)}, \\ \\ u &= -\dfrac{(x_1 - x_2)(y_1 - y_3) - (y_1 - y_2)(x_1 - x_3)} {(x_1 - x_2)(y_3 - y_4) - (y_1 - y_2)(x_3 - x_4)} \end{aligned} `} with ${tex.block` \begin{aligned} P_{(t)} &= (x_{1} + t(x_{2} - x_{1}), y_{1} + t(y_{2} - y_{1}), or \\ P_{(u)} &= (x_{3} + u(x_{4} - x_{3}), y_{3} + u(y_{4} - y_{3}) \end{aligned} `} Subsequently, one can check if the intersection points falls within the first line segment by testing if 0.0 ≤ ${tex`t`} ≤ 1.0, and check if it falls within the second line segment by testing if 0.0 ≤ ${tex`u`} ≤ 1.0. When the two lines are parallel or coincident the denominator is zero. `35:[] 2f:{"id":"15c1324b48ba4f4c","slug":"line-box-intersection","title":"Line segment intersection","thumbnail":"cd15e9123ae4c282d681361d83bb741af5889d66612fa1cac14316c7204aa673","access_level":"public","create_time":"$D2018-09-30T20:08:50.360Z","update_time":"$D2020-09-11T14:45:18.058Z","view_time":null,"first_public_time":"$D2018-10-01T00:27:51.083Z","fork":false,"stars":8,"starred":false,"owner":{"type":"team","id":"03836a98946da550","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":"starter_2024"},"version":1230,"publish_version":1230,"role":null,"authored":false,"authors":[{"type":"individual","id":"9334261743951ef0","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":null}],"members":[{"type":"individual","id":"9334261743951ef0","login":"toja","name":"Torben Jansen","avatar_url":"https://avatars-next.observableusercontent.com/f79c27ca86680a3a399f6eb78b22436d6dd665b49ad284ba1ccfb405bfc89fe0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"48442ce39f9dad7b","slug":"geometry","title":"Geometry","owner":{"id":"03836a98946da550","login":"toja","name":"Torben Jansen"}},"type":"notebook","body":{"title":"Line segment intersection","cells":[{"id":880,"value":"md`# Line segment intersection`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":711,"value":"problem_definition = md`\nLet's say we have two [lines](https://en.wikipedia.org/wiki/Line_(geometry)) ${tex`L_{1}`} and ${tex`L_{2}`} in 2-dimensional space, with each line being defined by two distinct points . How can we find the point , if any, where ${tex`L_{1}`} and ${tex`L_{2}`} [intersect](https://en.wikipedia.org/wiki/Intersection)?\n\nFurthermore, we want an easy way to find the points and where a line intersects a given bounding box, as shown in the interactive figure below.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":265,"value":"viewof margin = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":686,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":499,"value":"bezier_curves = md`---\nA Bézier curve is defined by a set of control points ${tex`P_{0}`} through ${tex`P_{n}`}, where the first and last control points are *always the end points* of the curve. A *linear* Bézier curve is simply a straight line segment between two distinct points ${tex`P_{0}`} and ${tex`P_{1}`} and has the following equation:\n\n${tex.block`B_{(t)} = P_{0} + t(P_{1} - P_{0}),`}\n\nwhere\n\n${tex.block`0 \\leq t \\leq 1`}\n\nThe ${tex`t`} in the function for a linear Bézier curve can be thought of as describing how far ${tex`B_{(t)}`} is from ${tex`P_{0}`} to ${tex`P_{1}`}. For example, when ${tex`t=0.25`}, ${tex`B_{(t)}`} is one quarter of the way from point ${tex`P_{0}`} to ${tex`P_{1}`}.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":887,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":897,"value":"viewof t = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":844,"value":"md`\nAs you can see from the figure above, the position (${tex`x, y`}) of ${tex`B_{(t)}`} is simply the result of simultaneously [interpolating](https://en.wikipedia.org/wiki/Linear_interpolation) between the x and y coordinates of ${tex`P_0`} and ${tex`P_1`} with\n\n${tex.block`x = x_1 + t(x_2 - x_1),`}\n${tex.block`y = y_1 + t(y_2 - y_1)`}\n\nwhich gives us the following equations for line ${tex`L_{1}`} and line ${tex`L_{2}`} in terms of Bézier parameters:\n\n${tex.block`L_{1} = \n \\begin{pmatrix}\n x_1\\\\\n y_1\n \\end{pmatrix}\n + t\n \\begin{pmatrix}\n x_2 - x_1 \\\\\n y_2 - y_1\n \\end{pmatrix}\n,`}\n${tex.block`L_{2} = \n \\begin{pmatrix}\n x_3\\\\\n y_3\n \\end{pmatrix}\n + u\n \\begin{pmatrix}\n x_4 - x_3 \\\\\n y_4 - y_3\n \\end{pmatrix}\n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":678,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":509,"value":"implementation = md`---\n## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":293,"value":"function intersect([[x1, y1], [x2, y2]], [[x3, y3], [x4, y4]], sa = false, sb = false ) {\n \n const x1x2 = x1 - x2, y1y2 = y1 - y2,\n x1x3 = x1 - x3, y1y3 = y1 - y3,\n x3x4 = x3 - x4, y3y4 = y3 - y4;\n \n const d = x1x2 * y3y4 - y1y2 * x3x4;\n\n // parallel or coincident\n if (d === 0) return undefined;\n \n const t = (x1x3 * y3y4 - y1y3 * x3x4) / d,\n u = -(x1x2 * y1y3 - y1y2 * x1x3) / d;\n \n const ist = t >= 0 && t <= 1,\n isu = u >= 0 && u <= 1;\n \n return sa && sb && ist && isu\n || sa && !sb && ist\n || !sa && sb && isu\n || !sa && !sb\n ? [\n x1 + t * (x2 - x1),\n y1 + t * (y2 - y1)\n ]\n : undefined;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4,"value":"function intersectBox([[x1, y1], [x2, y2]], [b1, b2, b3, b4]) {\n \n const _i1 = intersect([[x1, y1], [x2, y2]], [[b1, b2], [b1, b4]], false, true), // left\n _i2 = intersect([[x1, y1], [x2, y2]], [[b1, b2], [b3, b2]], false, true), // top\n _i3 = intersect([[x1, y1], [x2, y2]], [[b3, b2], [b3, b4]], false, true), // right\n _i4 = intersect([[x1, y1], [x2, y2]], [[b1, b4], [b3, b4]], false, true); // bottom\n \n const dx = x2 - x1;\n const dy = y2 - y1;\n \n let i1, i2;\n \n if (_i1) {\n if (dx > 0) i1 = _i1;\n if (dx < 0) i2 = _i1;\n }\n\n if (_i2) {\n if (dy > 0) i1 = _i2;\n if (dy < 0) i2 = _i2;\n }\n \n if (_i3) {\n if (dx < 0) i1 = _i3;\n if (dx > 0) i2 = _i3;\n }\n \n if (_i4) {\n if (dy < 0) i1 = _i4;\n if (dy > 0) i2 = _i4;\n }\n \n return [i1, i2];\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":410,"value":"width = 640","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":412,"value":"height = 420","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":35,"value":"lines = [\n [[240, 200], [320, 160]],\n [[620, 400], [180, 150]]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":42,"value":"viewof data = new View(lines)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1166,"value":"class View {\n constructor(value) {\n Object.defineProperties(this, {\n _list: { value: [], writable: true },\n _value: { value: value, writable: true }\n });\n }\n\n get value() {\n return this._value;\n }\n set value(value) {\n this._value = value;\n this.dispatchEvent({ type: \"input\", value });\n }\n \n addEventListener(type, listener) {\n if (type != \"input\" || this._list.includes(listener)) return;\n this._list = [listener].concat(this._list);\n }\n removeEventListener(type, listener) {\n if (type != \"input\") return;\n this._list = this._list.filter(l => l !== listener);\n }\n dispatchEvent(event) {\n const p = Promise.resolve(event);\n this._list.forEach(l => p.then(l));\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":23,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"