${i}

29:null 2a:["$","title",null,{"children":"Union polygon and area of rectangles (line sweep algorithm) | Mathieu Jouhet | Observable"}] 2f:T4a3,md` # Union polygon and area of rectangles (line sweep algorithm) Given a set of unrotated and potentially overlapping rectangles, we want to compute the total area covered by their union and get their union polygon(s). One way to proceed is to first use a _line sweep algorithm_ in order to _subdivide the surface of the rectangles to a set of non-overlaping rectangles_ covering the same area. In other words, we want the resulting rectangles to be either _contiguous_ or _completely separated_. Computing the total surface area is then as trivial as suming all the resulting rectangles areas. We can finally sort and remove duplicate vertices and connect the edges together to form the desired union polygon(s). Once we get the polygon, we can post-process it as much as we want, I've added a setting to round the corners, but the rest is entirely up to you! Note that this implementation will produce self-intersecting paths if two rectangles meet only at one of their respective corners and don't share any common edge. See after demo for more explanations and the actual code implementation, click on the left gutter of any cell to open the underlying code. `30:T120a,demo = { let t0, t1; const perfs = []; const margin = 4; const boxHeight = width / 3.5; const boxWidth = boxHeight * 3.49; const boxHeightRatio = boxHeight / width; const bboxHeightRatio = (bbox.height + margin * 2) / boxHeight; const scale = boxHeightRatio * bboxHeightRatio; const xmlns = 'http://www.w3.org/2000/svg'; // Prepare our svg const s = document.createElementNS(xmlns, 'svg'); s.setAttributeNS( null, 'viewBox', `${ bbox.x1 - margin } ${ bbox.y1 - margin } ${ bbox.width * 2 + margin * 4 } ${ bbox.height + margin * 2 }` ); s.setAttributeNS(null, 'width', boxWidth); s.setAttributeNS(null, 'height', boxHeight); s.setAttributeNS(null, 'style', `padding: 20px 0; background-color: ${theme.background}`); // Draw options const showRects = drawOptions.includes('rect'); const showSubdivision = drawOptions.includes('subdivision'); const showPoints = drawOptions.includes('points'); // Round path corners if needed; t0 = performance.now(); const roundedPolygon = union.polygons.map( poly => roundSvgPath( // Non rounded path to be rounded poly.map( (point, i) => `${i === 0 ? 'M' : 'L'}${point.join(' ')}${i === poly.length - 1 ? 'z' : ''}` ).join( ' ' ), scale * radius * 2 ) ).join(' '); t1 = performance.now(); const roundingTime = t1 - t0; // Draw original rectangles t0 = performance.now(); showRects && rects.forEach((r, i) => s.appendChild( svg` ` )); // Position on the x-axis of the resulting polygon const polygonOffset = p( (showRects ? 1 : 0.5) * (bbox.width + margin * 2 - (showRects ? margin / 3 : 0)) ); // Draw the subdivisions from the first step if (showSubdivision) { // Keep an index of the x positions we already drawn to avoid duplicates const alreadyDrawn = {}; // Polygon to use as a mask s.appendChild( svg` `); // The subdivision lines as a group, masked using the polygon // we need -webkit-clip-path to get the mask to work in safari const g = svg``; s.appendChild(g); subdivision.result.forEach( (r, i) => { if (!alreadyDrawn[r[1][0]] && i !== subdivision.result.length - 1) { alreadyDrawn[r[1][0]] = true; g.appendChild( svg`` ) } } ); } // Draw final polygon s.appendChild( svg` `); // Draw circles at points coordinates showPoints && union.polygons.forEach( poly => poly.forEach( (point, i) => s.appendChild( svg` ${i} ` ) ) ) // All done, measure and store perfs t1 = performance.now(); perfs.push({event: 'Drawing', time: t1 - t0}); perfs.push({event: 'Subdivision', time: subdivision.totalTime}); perfs.push({event: 'Union', time: union.totalTime}); perfs.push({event: 'Round polygon path', time: roundingTime}) s.totalTime = perfs.reduce((acc, v) => acc + v.time, 0); s.perfs = perfs; // Return the svg return s; }31:T610,md` ### Subdivide into non-overlapping rectangles and get the area Line sweep algorithms are very useful and efficient in computational geometry and are helpful in solving a variety of problems within the euclidian space. How it works is we first identify and sort _“events”_ along the axis we're concerned with. Here we want to sweep along both the **_horizontal axis_** (thus dealing with **_vertical events_**), and then along the **_vertical axis_** (thus dealing with **_horizontal events_**). But what are these events? Well if you think in terms of rectangle, there are only two possible events hapening along each axis we'll sweep over: 1. a rectangle **opens** 2. a rectangle **closes** Once we've identified and sorted our events, we start sweeping along the primary axis, going from event to event (so long as the event coordinate is the same) and keeping track of which rectangles are currently opened at any given point. We then sweep along the secondary axis to find the corresponding events that are related to the currently opened rectangles we identified on the primary axis. We then merge any overlaping rectangles into a single one. We keep repeating this and move further along the primary axis until we processed all the events, _et voilà_, we get the area, which is **\`${subdivision.area}\`** for the current set of rectangles, and the set of non-overlaping rectangles to work on for the next step: generating the resulting union polygon. **Click on the left gutter to open** the \`subdivide\` function code below: `32:Tb59,function subdivide(rects) { resetDemo; reset; const s ={}; const perfs = []; let t0, t1; const sortEvents = (axis, prop, axis2, prop2, order = 1, order2 = 1) => (w) => w.reduce( (acc, r, ind) => { acc.push(...r.map((e, i) => ({ ind, type: i, [prop]: e[axis], [prop2]: e[axis2], length: i === OPENING ? r[CLOSING][axis2] - e[axis2] : e[axis2] - r[OPENING][axis2] }))); return acc; }, [] ).sort( (a, b) => order2 * (a[prop2] - b[prop2]) ).sort( (a, b) => order * (a[prop] - b[prop]) ); t0 = performance.now(); const events_v = sortEvents(X, 'x', Y, 'y', 1, 1)(rects); const events_h = sortEvents(Y, 'y', X, 'x', 1, 1)(rects); t1 = performance.now(); // console.log(`Sorting events took ${t1-t0} ms`); perfs.push({event: 'Sort events', time: t1 - t0}); t0 = performance.now(); // First event is always in set let in_set = []; in_set[events_v[0].ind] = true; let union = []; let steps = []; let area = 0; for (let i = 0; i < events_v.length - 1; i++) { const event_v = events_v[i]; // console.log('-----\n', event_v.ind, 'Event_v', event_v); in_set[event_v.ind] = event_v.type === OPENING; const next = events_v[i + 1]; const delta_x = next && next.x - event_v.x; if (!delta_x){ // console.log('Next event has same x, skipping second scan', next); continue; } const in_set_only = in_set.reduce((acc, v, i) => {if(v) {acc.push(i)}; return acc}, []); // console.log(in_set_only); let opened = 0; const begin_x = event_v.x; const end_x = next.x let begin_y, end_y; let prev; for (let j = 0; j < events_h.length; j++) { // Horizontal sweep line for active rectangle const event_h = events_h[j]; if (in_set[events_h[j].ind]) { // console.log('Event_h', event_h); if (event_h.type === OPENING) { opened++; if (opened === 1) { begin_y = event_h.y; } } else { opened--; const nextInd = in_set_only[in_set_only.findIndex(r => r === event_h.ind) + 1]; let n = 1; let next = events_h[j + n]; while(j + n < events_h.length && !in_set[events_h[j + n].ind]) { n++; next = events_h[j + n]; } if (!next || opened === 0 && next.y !== event_h.y) { end_y = event_h.y; area += (end_x - begin_x) * (end_y - begin_y); union.push([ [begin_x, begin_y], [end_x, end_y] ]); } } prev = event_h; } } } t1 = performance.now(); perfs.push({event: 'Compute', time: t1 - t0}); s.totalTime = perfs.reduce((acc, v) => acc + v.time, 0); s.perfs = perfs; s.area = area; s.result = union; return s; }33:Td7d,function unionPolygon(rects) { // console.table(bbox); reset2; const s = {}; const perfs = []; let t0, t1; t0 = performance.now(); // Remove duplicate vertices const set = new Set(); rects.forEach(r => { const pts = [ [r[OPENING][X], r[OPENING][Y]], [r[CLOSING][X], r[OPENING][Y]], [r[CLOSING][X], r[CLOSING][Y]], [r[OPENING][X], r[CLOSING][Y]] ]; pts.forEach(p => { const s = p.join(','); if (set.has(s)) { set.delete(s); } else { set.add(s); } }) }); // Convert the set back to an array of points [[x, y], ...] const points = [...set].map(p => p.split(',').map(pp => +pp)); t1 = performance.now(); perfs.push({event: 'Remove duplicate vertex', time: t1 - t0}); // console.log(points); const sortPoints = (prop1, prop2) => (w) => w.sort( (a, b) => a[prop1] - b[prop1] ).sort( (a, b) => a[prop2] - b[prop2] ); t0 = performance.now(); const xThenY = (a,b) => a[0] a[1] p[0])); } t1 = performance.now(); perfs.push({event: 'Build polygon', time: t1 - t0}); s.totalTime = perfs.reduce((acc, v) => acc + v.time, 0); s.perfs = perfs; s.polygons = polys; return s; }34:T966,function createPerfGauge(obj, left, right) { // Performance.now used to give microseconds resolution, but now some browsers limit // the timer resolution to avoid fingerprinting // Filter out 0ms events, // but save their original index for color consistency const perfs = obj.perfs.filter( (e, i) => { e.originalIndex = i return e.time } ); return html`

${left}

Execution time lower than your browser's performance.now resolution setting ${perfs.map( (entry, i) => html` ${entry.time.toFixed(entry.time < 10 ? 2 :1)} ms ` )}

${right}

`; }35:Tfa7,function roundSvgPath(pathData, radius) { if (!pathData) { return; } // Get path coordinates as array of {x, y} objects let pathCoords = pathData .split(/[a-zA-Z]/) .reduce(function(parts, part){ var match = part.match(/(-?[\d]+(\.\d+)?)/g);; if (match) { // Cast to number before pushing coordinate parts.push({ x: +match[0], y: +match[1] }); } return parts; }, []).filter((e, i, arr) => { // Remove consecutive duplicates const prev = arr[ (i === 0 ? arr.length - 1 : i - 1) ]; return e.x !== prev.x || e.y !== prev.y; }); const path = []; const curveRadius = radius; for (let i = 0; i < pathCoords.length; i++) { // Get current point and the next two (start, corner, end) const c2Index = (i + 1) % pathCoords.length; const c3Index = (i + 2) % pathCoords.length; const c1 = pathCoords[i]; const c2 = pathCoords[c2Index]; const c3 = pathCoords[c3Index]; // Vector going from C2 to C1 and from C2 to C3 const c1c2dx = c1.x - c2.x; const c1c2dy = c1.y - c2.y; const c3c2dx = c3.x - c2.x; const c3c2dy = c3.y - c2.y; const angle = Math.abs(Math.atan2( c1c2dx * c3c2dy - c1c2dy * c3c2dx, c1c2dx * c3c2dx + c1c2dy * c3c2dy )); // Divide distance by two to allow rounding the next corner as much as this one const c2c1Dist = Math.hypot(c1c2dx, c1c2dy) / 2; const c2c3Dist = Math.hypot(c3c2dx, c3c2dy) / 2; // Clamp radius the the max available const clampedRadius = Math.min(radius, c2c1Dist, c2c3Dist); // Compute ideal control point distance to create a circle with quadratic bezier curves // const idealControlPointDistance = (4 / 3) * Math.tan(Math.PI / (2 * 4)) * clampedRadius; const idealControlPointDistance = (4 / 3) * Math.tan( Math.PI / (2 * ((2 * Math.PI) / angle ) ) ) * clampedRadius * ( angle < Math.PI / 2 ? 1 + Math.cos(angle) : 1 ); // Start of the curve let c1c2curvePoint = { x: c2.x + c1c2dx * clampedRadius / c2c1Dist / 2, y: c2.y + c1c2dy * clampedRadius / c2c1Dist / 2, } // First control point let c1c2curveCP = { x: c2.x + c1c2dx * (clampedRadius - idealControlPointDistance) / c2c1Dist / 2, y: c2.y + c1c2dy * (clampedRadius - idealControlPointDistance) / c2c1Dist / 2 } // End of the curve let c3c2curvePoint = { x: c2.x + c3c2dx * clampedRadius / c2c3Dist / 2, y: c2.y + c3c2dy * clampedRadius / c2c3Dist / 2, } // Second control point let c3c2curveCP = { x: c2.x + c3c2dx * (clampedRadius - idealControlPointDistance) / c2c3Dist / 2, y: c2.y + c3c2dy * (clampedRadius - idealControlPointDistance) / c2c3Dist / 2, } // Limit number after floating point const limit = point => ({ x: limitPrecision(point.x, 3), y: limitPrecision(point.y, 3) }); c1c2curvePoint = limit(c1c2curvePoint); c1c2curveCP = limit(c1c2curveCP); c3c2curvePoint = limit(c3c2curvePoint); c3c2curveCP = limit(c3c2curveCP) // If at last coordinate of polygon, use the end of the curve as // the polygon starting point if (i === pathCoords.length - 1) { path.unshift('M' + c3c2curvePoint.x + ' ' + c3c2curvePoint.y); } // Draw line from previous point to the start of the curve path.push('L' + c1c2curvePoint.x + ' ' + c1c2curvePoint.y); // Cubic bezier to draw the actual curve path.push('C' + c1c2curveCP.x + ' ' + c1c2curveCP.y + ',' + c3c2curveCP.x + ' ' + c3c2curveCP.y + ',' + c3c2curvePoint.x + ' ' + c3c2curvePoint.y); } // Close path path.push('Z'); return path.join(' '); }36:T9b0,rectsPredef = [ [ [[0, 0], [4, 4]], [[-3, 3], [1, 7]], [[3, 3], [7, 7]], [[0, 6], [4, 10]], ], [ [[1*2.5, 1*2.5], [2*2.5, 2*2.5]], [[0*2.5, 0*2.5], [1*2.5, 1*2.5]], [[2*2.5, 0*2.5], [3*2.5, 1*2.5]], [[0*2.5, 2*2.5], [1*2.5, 3*2.5]], [[2*2.5, 2*2.5], [3*2.5, 3*2.5]], ], [ [[0, 0], [4, 4]], [[-3, 3], [1, 7]], [[3, 3], [7, 7]], [[0, 6], [4, 10]], [[0+9, 0], [4+9, 4]], [[-3+9, 3], [1+9, 7]], [[3+9, 3], [7+9, 7]], [[0+9, 6], [4+9, 10]], [[0+9, 0+9], [4+9, 4+9]], [[-3+9, 3+9], [1+9, 7+9]], [[3+9, 3+9], [7+9, 7+9]], [[0+9, 6+9], [4+9, 10+9]], [[0, 0+9], [4, 4+9]], [[-3, 3+9], [1, 7+9]], [[3, 3+9], [7, 7+9]], [[0, 6+9], [4, 10+9]], ], [ [[3*2, -1*2], [4*2, 8*2]], [[0*2, 2*2], [7*2, 3*2]], [[1*2, 1*2], [2*2, 4*2]], [[5*2, 1*2], [6*2, 4*2]], [[2*2, 6*2], [5*2, 7*2]], [[2*2, 0*2], [5*2, 1*2]], ], [ [[1+0, 1-5+5], [1+3, 4-5+5]], [[1+1, 1-6+5], [1+3.5, 4-5+5]], [[1+4, 1-4+5], [1+4 + 3, 4-4+5]], [[1+5, 1-3+5], [1+4 + 4, 4-3+5]], [[1+-1, -1+5], [1+5, 5+5]], [[1+1, 0+5], [1+4, 3+5]], [[1+2, 2+5], [1+6, 6+5]], [[1+1, 5+5], [1+5, 7+5]], [[1+0, 6+5], [1+4, 8+5]] ], [ [[10,0], [47,4]], [[0,3], [30,7]], [[5,6], [37,10]], [[15,3.5], [29,6.5]], [[10,9], [42,13]], [[0,12], [30,16]], [[5,15], [35,19]], [[2,11], [20,15.5]], [[0+2,3+15], [30+6,7+15]], [[5+2,6+15], [35+3,10+15]], [[15+2,3.5+15], [29+4,6.5+15]], [[10+2,9+15], [40+5,13+15]], [[0+2,12+15], [30+3,16+15]], [[5+2,15+15], [35,19+15]], [[2+2,11+15], [20+4,15.5+15]], ], [ [[2, 0*1.2], [7, 2*1.2]], [[1, 1*1.2], [2, 2*1.2]], [[4, 1*1.2], [5, 4*1.2]], [[7, 1*1.2], [8, 5*1.2]], [[0, 2*1.2], [2, 7*1.2]], [[1, 3*1.2], [3, 5*1.2]], [[4, 3*1.2], [6, 5*1.2]], [[0, 5*1.2], [1, 8*1.2]], [[2, 6*1.2], [3, 8*1.2]], [[4, 7*1.2], [5, 8*1.2]], [[6, 6*1.2], [7, 8*1.2]], [[8, 4*1.2], [9, 8*1.2]], [[2, 4*1.2], [7, 7*1.2]], [[7, 2*1.2], [9, 7*1.2]], ], [ [[0, 1], [1, 3]], [[0, 5], [2, 6]], [[1, 2], [2, 5]], [[1, 3], [4, 4]], [[2, 1], [3, 4]], [[3, 0], [4, 2]], [[3, 1], [6, 2]], [[5, 0], [6, 1]], [[6, 1], [7, 3]], [[6, 2], [8, 4]], [[7, 3], [8, 6]], [[8, 1], [9, 3]], [[8, 5], [9, 6]], [[4, 2], [5, 3]], [[4, 3], [6, 4]], [[3, 4], [4, 5]], [[5, 4], [6, 5]] ], ]37:T8a1,function input(config) { let { form, type = "text", attributes = {}, action, getValue, title, description, format, display, submit, options } = config; const wrapper = html`

`; if (!form) form = html``; Object.keys(attributes).forEach(key => { const val = attributes[key]; if (val != null) form.input.setAttribute(key, val); }); if (submit) form.append( html`` ); if (title) form.append( html`${title}` ); form.append( html`` ); if (description) form.append( html`

${description}

` ); if (action) { action(form); } else { const verb = submit ? "onsubmit" : type == "button" ? "onclick" : type == "checkbox" || type == "radio" ? "onchange" : "oninput"; form[verb] = e => { e && e.preventDefault(); const value = getValue ? getValue(form.input) : form.input.value; if (form.output) { const out = display ? display(value) : format ? format(value) : value; if (out instanceof window.Element) { while (form.output.hasChildNodes()) { form.output.removeChild(form.output.lastChild); } form.output.append(out); } else { form.output.value = out; } } form.value = value; if (verb !== "oninput") form.dispatchEvent(new CustomEvent("input", { bubbles: true })); }; if (verb !== "oninput") wrapper.oninput = e => e && e.stopPropagation() && e.preventDefault(); if (verb !== "onsubmit") form.onsubmit = e => e && e.preventDefault(); form[verb](); } while (form.childNodes.length) { wrapper.appendChild(form.childNodes[0]); } form.append(wrapper); return form; }38:T1aa2,html`

CSS is form,
form follows function[s],
indeed, that is a pun

`39:[] 2d:{"id":"bf5e6fcc5485df7d","slug":"union-polygon-and-area-of-rectangles-line-sweep-algorithm","title":"Union polygon and area of rectangles (line sweep algorithm)","thumbnail":"f9fda5ccf9f74dcd190e79d06fdbffe75b0fdf376669aafd6946dc10d9d00e9f","access_level":"public","create_time":"$D2021-03-18T20:12:29.810Z","update_time":"$D2022-07-04T05:18:24.809Z","view_time":null,"first_public_time":"$D2021-03-22T17:06:38.690Z","has_unpublished_edits":null,"fork":false,"stars":61,"starred":false,"owner":{"type":"team","id":"56478bd83f2190f0","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":"starter_2024"},"version":3926,"publish_version":3926,"role":null,"authored":false,"authors":[{"type":"individual","id":"e5f68da25a5a2366","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":null}],"members":[{"type":"individual","id":"e5f68da25a5a2366","login":"daformat","name":"Mathieu Jouhet","avatar_url":"https://avatars-next.observableusercontent.com/c16e6bd08b4b833b3760138d4467214b19161a15acf138c3d1809c74485979ec","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":11,"collection":{"id":"3bb657500226a15a","slug":"doodles","title":"Doodles","owner":{"id":"56478bd83f2190f0","login":"daformat","name":"Mathieu Jouhet"}},"type":"notebook","body":{"title":"Union polygon and area of rectangles (line sweep algorithm)","cells":[{"id":0,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3715,"value":"md`\n#### Surface area: ${\n limitPrecision(subdivision.area, 2)\n} unit² - ${\n union.polygons.reduce((acc, v, i) => acc + v.length, 0)\n} points in union polygon${union.polygons.length > 1 ?'s' : ''}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2395,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2703,"value":"demoPerfs = createPerfGauge(\n demo,\n `${rects.length} rects`,\n `${demo.totalTime.toFixed(demo.totalTime < 10 ? 2 : 1)} ms`\n)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3201,"value":"viewof resetDemo = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2910,"value":"viewof activeTheme = radio({\n title: 'Theme',\n options: [\n { label: 'Tracing paper (light)', value: 'light' },\n { label: 'Blueprint (dark)', value: 'dark' }\n ],\n value: 'dark'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":640,"value":"viewof activeSet = slider({\n min: 0,\n max: rectsPredef.length + maxRandomSets,\n step: 1,\n title: \"Active Set\",\n value: current\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3112,"value":"viewof radius = slider({\n min: 0,\n max: 30,\n step: 1,\n title: \"Round corners\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2170,"value":"viewof stroke = slider({\n min: 0,\n max: 20,\n step: 1,\n value: 6,\n title: \"Stroke width\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1483,"value":"viewof maxRandomRects = slider({\n min: 5,\n max: 1000,\n step: 1,\n value: 200,\n title: \"Max random rects\",\n description: `Maximum amount of random rects generated. Doesn't affect the first sets which are predefined`,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3000,"value":"viewof drawOptions = checkbox({\n title: 'Draw options',\n description: \"Drawing a lot of rects can be slow (the red bar), deactivate to test the algorithm perfs\",\n options: [\n { value: \"rect\", label: \"Draw input rectangles\" },\n { value: \"subdivision\", label: \"Draw subdivisions\" },\n { value: \"points\", label: `Draw union polygon points` },\n ],\n value: [\"rect\", \"subdivision\", \"auto\"]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3600,"value":"viewof animate = checkbox({\n options: [\n { value: \"auto\", label: `Play - cycle through available sets of rectangles` },\n ],\n value: [\"auto\"]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2446,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2678,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2642,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1070,"value":"subdivision = {\n return subdivide(rects);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1477,"value":"subdivPerfs = createPerfGauge(\n subdivision,\n `${rects.length} rects`,\n `${subdivision.totalTime.toFixed(union.totalTime < 10 ? 2 :1)} ms`\n)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1515,"value":"viewof reset = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2477,"value":"md`---\n### Get the union polygon`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2683,"value":"md`\nNext up, we want to find the union polygon of our non-overlaping rectangles, so what we do is we _sweep_ both axis again to list all of the edges by axis and build an _undirected graph_ of them.\n\nWe can then start with one edge and go from there, adding the next edge until the polygon is complete. We keep doing this until all of the edges have been visited and get as many polygons as necessary depending on the layout of the rectangles.\n\n**Click on the left gutter to open** the \\`unionPolygon\\` function code below:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2650,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1812,"value":"union = {\n return unionPolygon(subdivision.result)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2187,"value":"unionPerfs = createPerfGauge(\n union,\n `${subdivision.result.length} rects`,\n `${union.totalTime.toFixed(union.totalTime < 10 ? 2 :1)} ms`\n)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1814,"value":"viewof reset2 = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2503,"value":"md`---\n### Details`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3867,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3160,"value":"md`#### Round corners\nUsing cubic bezier curve to approximate a circle with a radius max up to half the distance between points\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3920,"value":"See a more thorough explanation of the corner rounding algorithm using javascript and svg on the [rounding polygon corners notebook](https://observablehq.com/@daformat/rounding-polygon-corners)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3104,"value":"function sign(x) {\n return ((x > 0) - (x < 0));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3087,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3916,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3441,"value":"md`\n#### Svg precision\nLimit the floating point precision to avoid yielding unecessarily precise coordinates\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3422,"value":"precision = 4","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3417,"value":"function limitPrecision(num, precision) {\n return +( (+num).toFixed(precision).replace(/\\.?0+$/, '') );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3450,"value":"p = coord => limitPrecision(coord, precision)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"md`#### Rectangles\nRectangles are represented by their top left and bottom right coordinates, we provide a few presets and some random generated sets for testing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1386,"value":"viewof maxRandomSets = slider({\n min: 0,\n max: 500,\n step: 1,\n value: 7,\n title: \"Random sets\",\n description: \"Number of random sets to add to the presets\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3563,"value":"current = {\n let i = 0;\n yield i;\n while (animate && animate.includes('auto')) {\n i = (++i) % (rectsPredef.length + maxRandomSets + 1);\n yield Promises.delay(1250, i);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1171,"value":"function generateRandomRects(sets) {\n const set = []\n for (let j = 0; j <= sets; j++) {\n const r = [];\n const limit = 5 + (Math.random() * (maxRandomRects - 5))\n for (let i = 0; i < limit; i++) {\n const x1 = ~~(Math.random() * 50) / 8;\n const y1 = ~~(Math.random() * 50) / 8;\n const x2 = x1 + 2 + ~~(Math.random() * 50 ) / 8;\n const y2 = y1 + 2 + ~~(Math.random() * 50 ) / 8;\n r.push([[x1, y1], [x2, y2]]);\n }\n set.push(r);\n }\n return set;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3480,"value":"sets = [\n ...rectsPredef, \n ...generateRandomRects(maxRandomSets) // add random rects\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1384,"value":"rects = sets[activeSet]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":589,"value":"bbox = {\n const b = rects.reduce((acc, v) => ({\n x1: (acc.x1 == null || v[OPENING][X] < acc.x1) ? v[OPENING][X] : acc.x1,\n y1: (acc.y1 == null || v[OPENING][Y] < acc.y1) ? v[OPENING][Y] : acc.y1,\n x2: (acc.x2 == null || v[CLOSING][X] > acc.x2) ? v[CLOSING][X] : acc.x2,\n y2: (acc.y2 == null || v[CLOSING][Y] > acc.y2) ? v[CLOSING][Y] : acc.y2,\n }), {});\n b.width = b.x2 - b.x1;\n b.height = b.y2 - b.y1;\n return b;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":592,"value":"OPENING = 0; // top-left","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":593,"value":"CLOSING = 1; // bottom-right","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":596,"value":"X = 0;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":597,"value":"Y = 1;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2516,"value":"md`#### Style parameters`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2831,"value":"theme = themes[activeTheme]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2826,"value":"themes = {\n return {\n light: {\n background: '#fff',\n rects: {\n fill: 'rgba(198, 199, 255, 0.2)',\n stroke: '#3f51b5'\n },\n polygon: {\n fill: 'rgba(50,0,200, 0.05)',\n stroke: 'rgb(200, 0, 200)',\n points: 'rgba(50, 50, 70, 0.8)',\n subdivision: 'rgba(100, 80, 155, 0.75)'\n }\n },\n dark: {\n background: '#283593',\n rects: {\n fill: 'rgba(185, 210, 245, 0.15)',\n stroke: '#f5f5ff'\n },\n polygon: {\n fill: 'rgba(255, 255, 255, 0.05)',\n stroke: 'rgb(255, 255, 255)',\n points: 'rgba(255, 255, 255, 1)',\n subdivision: 'rgba(255, 255, 255, 0.5)'\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1556,"value":"colors = [\"#ef476f\", \"#ffd166\", \"#06d6a0\", \"#118ab2\", \"#073b4c\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1595,"value":"textColors = [\"#fff\", \"#111\", \"#fff\", \"#fff\", \"#fff\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2499,"value":"md`#### Input helpers`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":609,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":611,"value":"function slider(config = {}) {\n let {\n min = 0,\n max = 1,\n value = (max + min) / 2,\n step = \"any\",\n precision = 2,\n title,\n description,\n disabled,\n getValue,\n format,\n display,\n submit\n } = typeof config === \"number\" ? { value: config } : config;\n precision = Math.pow(10, precision);\n if (!getValue)\n getValue = input => Math.round(input.valueAsNumber * precision) / precision;\n return input({\n type: \"range\",\n title,\n description,\n submit,\n format,\n display,\n attributes: { min, max, step, disabled, value },\n getValue\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2907,"value":"import {radio, checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":618,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 2e:"$2d:body"