31:T637,{ let a = [ { x: 0, y: 0 }, { x: 10, y: 0 } ]; let b = [ { x: 10, y: 0 }, { x: 20, y: 0 } ]; let c = getIntersections(a, b); let d = [ { y: 0, x: 30 }, { y: 10, x: 30 } ]; let e = [ { y: 10, x: 30 }, { y: 20, x: 30 } ]; let f = getIntersections(d, e); let g = [ { x: 35, y: 0 }, { x: 45, y: 10 } ]; let h = [ { x: 45, y: 10 }, { x: 55, y: 20 } ]; let i = getIntersections(g, h); return Plot.plot({ width: 200, height: 100, x: { ticks: 0, label: null }, y: { ticks: 0, label: null }, marks: [ Plot.line(a, { x: "x", y: "y", strokeWidth: 5, opacity: 0.5, stroke: "#fdc086" }), Plot.line(b, { x: "x", y: "y", stroke: "#beaed4", strokeWidth: 5, opacity: 0.5 }), Plot.dot(c, { x: "x", y: "y", stroke: "#1b9e77" }), Plot.line(d, { x: "x", y: "y", strokeWidth: 5, opacity: 0.5, stroke: "#fdc086" }), Plot.line(e, { x: "x", y: "y", stroke: "#beaed4", strokeWidth: 5, opacity: 0.5 }), Plot.dot(f, { x: "x", y: "y", stroke: "#1b9e77" }), Plot.line(g, { x: "x", y: "y", strokeWidth: 5, opacity: 0.5, stroke: "#fdc086" }), Plot.line(h, { x: "x", y: "y", stroke: "#beaed4", strokeWidth: 5, opacity: 0.5 }), Plot.dot(i, { x: "x", y: "y", stroke: "#1b9e77" }) ] }); }32:[] 2f:{"title":"Polyline Intersections","cells":[{"id":0,"value":"# Polyline Intersections\n\nI didn't find [kld-intersections](https://github.com/thelonious/kld-intersections) (or something else easy to use) until after I wrote this, and then it seems to have turned out a little faster. Use it like:\n\n~~~js\nimport {getIntersections} from \"@stringertheory/polyline-intersections\"\n~~~\n\n**`getIntersections(polyline1, polyline2)`** returns an array of points where the two polylines intersect. **`polyline1`** and **`polyline2`** are arrays of points. All points are in **`{x: Number, y: Number}`** format.\n\nIf there are segments that have a line as an intersection (collinear), it will return one points at the midpoint of the intersection (see below).","pinned":false,"hidden":false,"mode":"md"},{"id":712,"value":"// there are two versions of getIntersections in this notebook: one that only checks the bounding box instead of using an rtree (getIntersectionsBoundingBox), and another that uses an rtree (getIntersectionsIndex). This version that uses an index seems like the most versatile. It uses the flatbush package for the index. The getIntersectionsBoundingBox doesn't have dependencies.\ngetIntersections = getIntersectionsIndex","pinned":false,"hidden":false,"mode":"ojs"},{"id":754,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":758,"value":"### Uniform random lines\n\nMight not be the most realistic case, but good for testing to make sure results match.","pinned":false,"hidden":false,"mode":"md"},{"id":54,"value":"Plot.plot({\n x: { ticks: 0, label: null },\n y: { ticks: 0, label: null },\n marks: [\n Plot.line(a, { x: \"x\", y: \"y\", stroke: \"#fdc086\" }),\n Plot.line(b, { x: \"x\", y: \"y\", stroke: \"#beaed4\" }),\n Plot.dot(c, { x: \"x\", y: \"y\", stroke: \"#1b9e77\" })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":230,"value":"viewof nPoints = Inputs.range([10, 500], {\n label: \"n points\",\n step: 10,\n value: 50\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"viewof button = Inputs.button(\"generate new lines\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":209,"value":"{\n if (c.length !== d.length) {\n throw new Error(\"did not get the same number of points!\");\n } else {\n return html`✅ number of intersections (${c.length}) matches with kld library.`;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":269,"value":"viewof testSpeedUniform = Inputs.toggle({ label: \"test speed\", value: false })","pinned":false,"hidden":false,"mode":"ojs"},{"id":741,"value":"html`Speedup: ${runSpeedTest(a, b, testSpeedUniform).speedup}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"a = {\n button;\n return generateUniformRandom(nPoints, 1, 3);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":604,"value":"b = {\n button;\n return generateUniformRandom(nPoints, 0, 2);\n return generateRandomWalk(100, 1, 1, 0.1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"c = getIntersections(a, b)","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"d = kld.Intersection.intersectPolylinePolyline(a, b).points","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"function generateUniformRandom(nPoints, min = 0, max = 1) {\n const result = [];\n for (let i = 0; i < nPoints; i++) {\n result.push({\n x: _.random(min, max, true),\n y: _.random(min, max, true)\n });\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"function runSpeedTest(a, b, testSpeed = true, n = 6) {\n const result = {};\n if (testSpeed) {\n let i = performance.now();\n for (let i = 0; i < n; i++) {\n getIntersections(a, b);\n }\n const tThis = (performance.now() - i) / n;\n\n i = performance.now();\n for (let i = 0; i < n; i++) {\n kld.Intersection.intersectPolylinePolyline(a, b);\n }\n const tKLD = (performance.now() - i) / n;\n\n if (tThis === 0 || tKLD === 0) {\n result.speedup = \"? (ran too fast)\"; // could do this better\n } else {\n result.speedup =\n d3.format(\".0f\")(tKLD / tThis) +\n \"x \" +\n (tKLD > tThis ? \"faster\" : \"slower\");\n }\n } else {\n result.speedup = \"? (not checking speed)\";\n }\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":782,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":779,"value":"### Intersecting functions\n\nThis is more what I have in mind with using this.","pinned":false,"hidden":false,"mode":"md"},{"id":855,"value":"basicPlot(funcA, funcB)","pinned":false,"hidden":false,"mode":"ojs"},{"id":831,"value":"viewof testSpeedFunctions = Inputs.toggle({ label: \"test speed\", value: false })","pinned":false,"hidden":false,"mode":"ojs"},{"id":810,"value":"html`Speedup: ${runSpeedTest(funcA, funcB, testSpeedFunctions).speedup}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":793,"value":"funcA = _.range(0, 30, 0.02).map((x) => ({\n x,\n y: Math.sin(3 * x + 0.5) + 0.5\n}))","pinned":false,"hidden":false,"mode":"ojs"},{"id":795,"value":"funcB = _.range(0, 20, 0.02).map((x) => ({ x, y: Math.sin(x) }))","pinned":false,"hidden":false,"mode":"ojs"},{"id":687,"value":"function basicPlot(a, b, width = 400, strokeWidth = 3) {\n return Plot.plot({\n width: width,\n height: width / 2,\n x: { ticks: 0, label: null },\n y: { ticks: 0, label: null },\n marks: [\n Plot.line(a, {\n x: \"x\",\n y: \"y\",\n strokeWidth: strokeWidth,\n opacity: 0.5,\n stroke: \"#fdc086\"\n }),\n Plot.line(b, {\n x: \"x\",\n y: \"y\",\n stroke: \"#beaed4\",\n strokeWidth: strokeWidth,\n opacity: 0.5\n }),\n Plot.dot(getIntersections(a, b), {\n x: \"x\",\n y: \"y\",\n stroke: \"#1b9e77\"\n })\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":878,"value":"### Random walks","pinned":false,"hidden":false,"mode":"md"},{"id":858,"value":"basicPlot(rwA, rwB)","pinned":false,"hidden":false,"mode":"ojs"},{"id":866,"value":"viewof rwButton = Inputs.button(\"generate random walks\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":883,"value":"html`Speedup: ${runSpeedTest(rwA, rwB).speedup}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":837,"value":"rwA = {\n rwButton;\n return generateRandomWalk(50, 0, 0, 1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":844,"value":"rwB = {\n rwButton;\n return generateRandomWalk(50, 0, 0, 1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":601,"value":"function generateRandomWalk(nPoints, x0 = 0, y0 = 0, r = 1) {\n let x = x0;\n let y = y0;\n let values = [{ x, y }];\n for (let i = 0; i < nPoints; i++) {\n let angle = 2 * Math.PI * Math.random();\n x += r * Math.cos(angle);\n y += r * Math.sin(angle);\n values.push({ x, y });\n }\n return values;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":357,"value":"### Collinear line segments with overlap\n\nI made it so that when the intersection is actually another line, it takes the midpoint. I think this will be most useful for how I'm imagining using this.","pinned":false,"hidden":false,"mode":"md"},{"id":890,"value":"basicPlot(\n [\n { x: 0, y: 0 },\n { x: 10, y: 10 }\n ],\n [\n { x: 5, y: 5 },\n { x: 15, y: 15 }\n ],\n 200,\n 5\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":425,"value":"### Parallel line segments","pinned":false,"hidden":false,"mode":"md"},{"id":428,"value":"basicPlot(\n [\n { x: 0, y: 0 },\n { x: 10, y: 10 }\n ],\n [\n { x: 5, y: 0 },\n { x: 15, y: 10 }\n ],\n 200,\n 5\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":440,"value":"### Collinear line segments with only one point overlap","pinned":false,"hidden":false,"mode":"md"},{"id":436,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":452,"value":"### Collinear line segments without overlap","pinned":false,"hidden":false,"mode":"md"},{"id":450,"value":"basicPlot(\n [\n { x: 0, y: 0 },\n { x: 10, y: 10 }\n ],\n [\n { x: 15, y: 15 },\n { x: 25, y: 25 }\n ],\n 200,\n 5\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":906,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"function getIntersectionsCheckBounds(polyline1, polyline2) {\n let bbox1 = getBoundingBox(polyline1);\n let bbox2 = getBoundingBox(polyline2);\n let bboxIntersection = getBoundingBoxIntersection(bbox1, bbox2);\n if (!bboxIntersection) {\n return [];\n }\n\n let segments1 = getSegmentsTouchingBox(polyline1, bboxIntersection);\n let segments2 = getSegmentsTouchingBox(polyline2, bboxIntersection);\n\n let intersections = [];\n segments1.forEach(function (one) {\n segments2.forEach(function (two) {\n let intersect = checkIntersection(one, two);\n if (intersect) {\n intersections.push(intersect);\n }\n });\n });\n\n return intersections;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":399,"value":"function areCollinear(p1, p2, p3) {\n return (\n p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y) === 0\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":366,"value":"// adapted from https://stackoverflow.com/a/15812696/1431778, almost certainly way too complicated!\nfunction collinearIntersection([a, b], [c, d], x = \"x\") {\n if (!areCollinear(a, b, c)) {\n return null;\n }\n let aa, bb, cc, dd;\n if (a[x] < b[x]) {\n aa = a;\n bb = b;\n } else if (a[x] === b[x]) {\n return collinearIntersection([a, b], [c, d], \"y\");\n } else {\n aa = b;\n bb = a;\n }\n if (c[x] < d[x]) {\n cc = c;\n dd = d;\n } else {\n cc = d;\n dd = c;\n }\n\n if (bb[x] - cc[x] >= 0 && dd[x] - aa[x] >= 0) {\n let result = [];\n if (aa[x] > cc[x]) {\n result.push(aa);\n } else {\n result.push(cc);\n }\n if (bb[x] > dd[x]) {\n result.push(dd);\n } else {\n result.push(bb);\n }\n return {\n x: (result[0].x + result[1].x) / 2,\n y: (result[0].y + result[1].y) / 2\n };\n } else {\n return null;\n }\n return [aa, bb, cc, dd];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"// adapted from https://paulbourke.net/geometry/pointlineplane/\nfunction checkIntersection([a, b], [c, d]) {\n let x1 = a.x,\n y1 = a.y,\n x2 = b.x,\n y2 = b.y,\n x3 = c.x,\n y3 = c.y,\n x4 = d.x,\n y4 = d.y;\n\n // Check if any of the lines are of length 0\n if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {\n return null;\n }\n\n const denominator = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);\n\n // Lines are parallel\n if (denominator === 0) {\n return collinearIntersection([a, b], [c, d]);\n }\n\n let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator;\n let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator;\n\n // is the intersection along the segments\n if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {\n return null;\n }\n\n // Return x and y coordinates of the intersection\n return {\n x: x1 + ua * (x2 - x1),\n y: y1 + ua * (y2 - y1)\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"function getBoundingBox(polyline) {\n if (polyline.length === 0) {\n return null;\n }\n\n let minX = polyline[0].x;\n let maxX = polyline[0].x;\n let minY = polyline[0].y;\n let maxY = polyline[0].y;\n\n for (let i = 1; i < polyline.length; i++) {\n minX = Math.min(minX, polyline[i].x);\n maxX = Math.max(maxX, polyline[i].x);\n minY = Math.min(minY, polyline[i].y);\n maxY = Math.max(maxY, polyline[i].y);\n }\n\n return {\n minX: minX,\n maxX: maxX,\n minY: minY,\n maxY: maxY\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"function getSegmentsTouchingBox(polyline, box) {\n let segments = [];\n for (let i = 0; i < polyline.length - 1; i++) {\n let a = polyline[i];\n let b = polyline[i + 1];\n if (isSegmentTouchingBox(a, b, box)) {\n segments.push([a, b]);\n }\n }\n return segments;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":15,"value":"function getBoundingBoxIntersection(box1, box2) {\n let intersectMinX = Math.max(box1.minX, box2.minX);\n let intersectMaxX = Math.min(box1.maxX, box2.maxX);\n let intersectMinY = Math.max(box1.minY, box2.minY);\n let intersectMaxY = Math.min(box1.maxY, box2.maxY);\n\n if (intersectMinX <= intersectMaxX && intersectMinY <= intersectMaxY) {\n return {\n minX: intersectMinX,\n maxX: intersectMaxX,\n minY: intersectMinY,\n maxY: intersectMaxY\n };\n } else {\n return null;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":152,"value":"function isSegmentTouchingBox(a, b, box) {\n const lineBox = getBoundingBox([a, b]);\n return Boolean(getBoundingBoxIntersection(lineBox, box));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":527,"value":"function* iterSegments(polyline) {\n for (let i = 0; i < polyline.length - 1; i++) {\n yield [polyline[i], polyline[i + 1]];\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":539,"value":"function makeIndex(polyline) {\n const index = new Flatbush(polyline.length - 1);\n for (let segment of iterSegments(polyline)) {\n let bb = getBoundingBox(segment);\n index.add(bb.minX, bb.minY, bb.maxX, bb.maxY);\n }\n index.finish();\n return index;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":525,"value":"function getIntersectionsIndex(polyline1, polyline2) {\n let iterateOver, indexLine;\n if (polyline1.length < polyline2.length) {\n iterateOver = polyline1;\n indexLine = polyline2;\n } else {\n iterateOver = polyline2;\n indexLine = polyline1;\n }\n const index = makeIndex(indexLine);\n\n let intersections = [];\n for (let i = 0; i < iterateOver.length - 1; i++) {\n let one = [iterateOver[i], iterateOver[i + 1]];\n let bbOne = getBoundingBox(one);\n index\n .search(bbOne.minX, bbOne.minY, bbOne.maxX, bbOne.maxY)\n .forEach(function (j) {\n let two = [indexLine[j], indexLine[j + 1]];\n let intersect = checkIntersection(one, two);\n if (intersect) {\n intersections.push(intersect);\n }\n });\n }\n\n return intersections;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":634,"value":"// experimenting with whether it's useful to simplify lines\nfunction getPixelsInDomain(\n polyline,\n nPixels = 0.5,\n xPixels = 1200,\n yPixels = 800\n) {\n const xInverseScale = d3.scaleLinear(\n [0, xPixels],\n d3.extent(polyline, (d) => d.x)\n );\n const yInverseScale = d3.scaleLinear(\n [0, yPixels],\n d3.extent(polyline, (d) => d.y)\n );\n return {\n x: xInverseScale(nPixels) - xInverseScale(0),\n y: yInverseScale(nPixels) - yInverseScale(0)\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":918,"value":"### Imports","pinned":false,"hidden":false,"mode":"md"},{"id":25,"value":"kld = require(\"kld-intersections\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":520,"value":"Flatbush = require(\"flatbush\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":590,"value":"// simplify = require(\"simplify-js\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}