| license: gpl-3.0 |
This block is a continuation on my reflexions on Distance-Limited Vornoi Interaction (see 2, and 1).
This block experiments how to compute the path of a distance limited vironoï cell, which is the intersection area of a d3 Voronoï cell and a circle.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| #under-construction { | |
| display: none; | |
| position: absolute; | |
| top: 200px; | |
| left: 300px; | |
| font-size: 40px; | |
| } | |
| .seed { | |
| fill: grey; | |
| stroke: black; | |
| } | |
| .seed.draggable:hover, .seed.dragging { | |
| cursor: all-scroll; | |
| } | |
| .radius { | |
| fill: pink; | |
| stroke: red; | |
| } | |
| .radius.draggable:hover, .radius.dragging { | |
| cursor: ew-resize; | |
| } | |
| .max-cell-distance { | |
| fill: none; | |
| stroke: pink; | |
| } | |
| .cell { | |
| fill: none; | |
| stroke: lightBlue; | |
| } | |
| .limited-cell { | |
| fill: lightBlue; | |
| stroke: lightBlue | |
| } | |
| </style> | |
| <body> | |
| <div id="under-construction"> | |
| UNDER CONSTRUCTION | |
| </div> | |
| <script src="https://d3js.org/d3.v3.min.js"></script> | |
| <script> | |
| var margin = {left: 20, top: 20, right: 20, bottom: 20}, | |
| legendHeight = 20, | |
| width = 960 - margin.left - margin.right, | |
| height = 500 - margin.top - legendHeight - margin.bottom; | |
| var seedCount = 5; | |
| var seeds = d3.range(seedCount).map(function(d,i) { | |
| return [width/2+150*Math.cos(d*2*Math.PI/seedCount), | |
| height/2+150*Math.sin(d*2*Math.PI/seedCount)]; | |
| }); | |
| seeds[0] = [width/2, height/2]; | |
| var xAccessor = function(d) { return d[0]; }; | |
| var yAccessor = function(d) { return d[1]; }; | |
| var maxCellDistance = 100; | |
| //begin: drag behaviors | |
| var dragSeed = d3.behavior.drag() | |
| .origin(function(d) { return d; }) | |
| .on("dragstart", dragStarted) | |
| .on("drag", seedDragged) | |
| .on("dragend", dragEnded); | |
| var dragRadius = d3.behavior.drag() | |
| .origin(function(d) { return d; }) | |
| .on("dragstart", dragStarted) | |
| .on("drag", radiusDragged) | |
| .on("dragend", dragEnded); | |
| //end: drag behaviors | |
| //begin: define and compute voronoi layout | |
| var voronoi = d3.geom.voronoi() | |
| .x(xAccessor) | |
| .y(yAccessor) | |
| .clipExtent([[0, 0], [width, height]]); | |
| var voronoiLayout, cellOfConcern; | |
| (updateVoronoiLayout = function() { | |
| voronoiLayout = voronoi(seeds); | |
| cellOfConcern = voronoiLayout[0]; | |
| })() | |
| //end: define and compute voronoi layout | |
| var svg = d3.select("body").append("svg") | |
| .attr("width", width + margin.left + margin.right) | |
| .attr("height", height + margin.top + legendHeight + margin.bottom); | |
| var drawingArea = svg.append("g").attr("transform", "translate("+[margin.left,margin.top]+")"); | |
| //begin: redraw() | |
| (redraw = function () { | |
| // draw cells of the voronoi layout in lightblue dashed | |
| var drawnCells = drawingArea.selectAll(".cell") | |
| .data(voronoiLayout); | |
| drawnCells.enter() | |
| .append("path") | |
| .classed("cell", true); | |
| drawnCells.attr("d", function(d) { return d3.svg.line()(d)+"z" }); | |
| // draw distance limited vornoi cell in lightgrey | |
| var drawnLimitedCell = drawingArea.selectAll(".limited-cell") | |
| .data([cellOfConcern]); | |
| drawnLimitedCell.enter() | |
| .append("path") | |
| .classed("limited-cell", true); | |
| drawnLimitedCell.attr("d", function(d) { return distanceLimitedCell(d, maxCellDistance) }); | |
| // draw circle representing max distance | |
| var drawnMaxCellDistance = drawingArea.selectAll(".max-cell-distance") | |
| .data([cellOfConcern]); | |
| drawnMaxCellDistance.enter() | |
| .append("circle") | |
| .classed("max-cell-distance", true); | |
| drawnMaxCellDistance.attr({ | |
| cx: function(d) { return xAccessor(d.point); }, | |
| cy: function(d) { return yAccessor(d.point); }, | |
| r: maxCellDistance | |
| }); | |
| // draw seeds | |
| var drawnSeeds = drawingArea.selectAll(".seed") | |
| .data(seeds); | |
| drawnSeeds.enter() | |
| .append("circle") | |
| .classed("seed draggable", true) | |
| .attr("r", 4) | |
| .call(dragSeed); | |
| drawnSeeds.attr({ | |
| cx: function(d) { return xAccessor(d); }, | |
| cy: function(d) { return yAccessor(d); } | |
| }); | |
| // draw max distance anchor | |
| var drawnRadius = drawingArea.selectAll(".radius") | |
| .data([cellOfConcern]); | |
| drawnRadius.enter() | |
| .append("circle") | |
| .classed("radius draggable", true) | |
| .attr("r", 4) | |
| .call(dragRadius); | |
| drawnRadius.attr({ | |
| cx: function(d) { return xAccessor(d.point)+maxCellDistance; }, | |
| cy: function(d) { return yAccessor(d.point); } | |
| }); | |
| })() | |
| //end: redraw() | |
| insertLegend(); | |
| //////////////////////// | |
| // bl.ocks' utilities // | |
| //////////////////////// | |
| function dragStarted(d) { | |
| d3.select(this).classed("dragging", true); | |
| } | |
| function dragEnded(d) { | |
| d3.select(this).classed("dragging", false); | |
| } | |
| function seedDragged(d) { | |
| d[0] += d3.event.dx; | |
| d[1] += d3.event.dy; | |
| updateVoronoiLayout(); | |
| redraw(); | |
| } | |
| function radiusDragged(d) { | |
| maxCellDistance += d3.event.dx; | |
| if (maxCellDistance<0) { maxCellDistance=0; } | |
| redraw(); | |
| } | |
| function insertLegend () { | |
| var legendContainer = drawingArea.append("g"); | |
| legendContainer.classed("legend", true) | |
| .attr("transform", "translate("+[0,height+legendHeight/2]+")"); | |
| var legends = [{symbol: "circle", class: "seed", text: "seed (draggable)"}, | |
| {symbol: "square", class: "cell", text: "voronoï cell"}, | |
| {symbol: "circle", class: "radius", text: "max distance (draggable)"}, | |
| {symbol: "square", class: "limited-cell", text: "distance-limited Voronoï cell"}] | |
| var drawnLegend = legendContainer.selectAll("g").data(legends).enter(); | |
| var currentLegend = drawnLegend.append("g") | |
| .attr("transform", function(d, i) { return "translate("+[20+200*i,0]+")"; }) | |
| .classed("legend-item", true); | |
| currentLegend.append("path") | |
| .attr({ | |
| d: d3.svg.symbol() | |
| .type(function(d) { return d.symbol; }) | |
| .size(function(d) { return (d.symbol==="circle")? 40 : 80; }), | |
| transform: function(d) { return "translate("+[-10,0]+")"}, | |
| class: function(d) { return d.class; } | |
| }) | |
| currentLegend.append("text") | |
| .attr({ | |
| "text-anchor": "start", | |
| "transform": "translate("+[0, legendHeight/4]+")" | |
| }) | |
| .text(function(d) { return d.text; }) | |
| } | |
| //////////////////////// | |
| /// Distance Limited /// | |
| ///// Voronoi Cell ///// | |
| //////////////////////// | |
| function distanceLimitedCell (cell, r) { | |
| var seed = [xAccessor(cell.point), yAccessor(cell.point)]; | |
| if (allVertecesInsideMaxDistanceCircle(cell, seed, maxCellDistance)) { | |
| return "M"+cell.join("L")+"Z"; | |
| } else { | |
| var path = ""; | |
| var p0TooFar = firstPointTooFar = pointTooFarFromSeed(cell[0], seed, maxCellDistance); | |
| var p0, p1, intersections; | |
| var openingArcPoint, lastClosingArcPoint; | |
| //begin: loop through all segments to compute path | |
| for (var iseg=0; iseg<cell.length; iseg++) { | |
| p0 = cell[iseg]; | |
| p1 = cell[(iseg+1)%cell.length]; | |
| // compute intersections between segment and maxDistance circle | |
| intersections = segmentCircleIntersections (p0, p1, seed ,maxCellDistance); | |
| // complete the path (with lines or arc) depending on: | |
| // intersection count (0, 1, or 2) | |
| // if the segment is the first to start the path | |
| // if the first point of the segment is inside or outside of the maxDistance circle | |
| if (intersections.length===2) { | |
| if (p0TooFar) { | |
| if (path==="") { | |
| // entire path will finish with an arc | |
| // store first intersection to close last arc | |
| lastClosingArcPoint = intersections[0]; | |
| // init path at 1st intersection | |
| path += "M"+intersections[0]; | |
| } else { | |
| //close arc at first intersection | |
| path += largeArc(openingArcPoint, intersections[0], seed)+" 0 "+intersections[0]; | |
| } | |
| // then line to 2nd intersection, then initiliaze an arc | |
| path += "L"+intersections[1]; | |
| path += "A "+r+" "+r+" 0 "; | |
| openingArcPoint = intersections[1]; | |
| } else { | |
| // THIS CASE IS IMPOSSIBLE AND SHOULD NOT ARISE | |
| console.error("What's the f**k"); | |
| } | |
| } else if (intersections.length===1) { | |
| if (p0TooFar) { | |
| if (path==="") { | |
| // entire path will finish with an arc | |
| // store first intersection to close last arc | |
| lastClosingArcPoint = intersections[0]; | |
| // init path at first intersection | |
| path += "M"+intersections[0]; | |
| } else { | |
| // close the arc at intersection | |
| path += largeArc(openingArcPoint, intersections[0], seed)+" 0 "+intersections[0]; | |
| } | |
| // then line to next point (1st out, 2nd in) | |
| path += "L"+p1; | |
| } else { | |
| if (path==="") { | |
| // init path at p0 | |
| path += "M"+p0; | |
| } | |
| // line to intersection, then initiliaze arc (1st in, 2nd out) | |
| path += "L"+intersections[0]; | |
| path += "A "+r+" "+r+" 0 "; | |
| openingArcPoint = intersections[0]; | |
| } | |
| p0TooFar = !p0TooFar; | |
| } else { | |
| if (p0TooFar) { | |
| // entire segment too far, nothing to do | |
| } else { | |
| // entire segment in maxDistance | |
| if (path==="") { | |
| // init path at p0 | |
| path += "M"+p0; | |
| } | |
| // line to next point | |
| path += "L"+p1; | |
| } | |
| } | |
| }//end: loop through all segments | |
| if (path === '') { | |
| // special case: no segment intersects the maxDistance circle | |
| // cell perimeter is entirely outside the maxDistance circle | |
| // path is the maxDistance circle, drawing 2 1/2-circles as mbostock does for its d3.svg.symbol.type("circle") | |
| path = "M"+[seed[0]+r,seed[1]]+"A "+r+" "+r+" 0 0 0 "+[seed[0]-r,seed[1]]+"A "+r+" "+r+" 0 0 0 "+[seed[0]+r,seed[1]]+"Z"; | |
| } else { | |
| // if final segment ends with an opened arc, close it | |
| if (firstPointTooFar) { | |
| path += largeArc(openingArcPoint, lastClosingArcPoint, seed)+" 0 "+lastClosingArcPoint; | |
| } | |
| path+="Z"; | |
| } | |
| return path; | |
| } | |
| function allVertecesInsideMaxDistanceCircle (cell, seed, r) { | |
| var result = true; | |
| var p; | |
| for (var ip=0; ip<cell.length; ip++) { | |
| result &= !pointTooFarFromSeed(cell[ip], seed, r); | |
| } | |
| return result; | |
| } | |
| function pointTooFarFromSeed(p, seed, r) { | |
| return (Math.pow(p[0]-seed[0],2)+Math.pow(p[1]-seed[1],2)>Math.pow(r, 2)); | |
| } | |
| function largeArc(p0, p1, seed) { | |
| var v1 = [p0[0] - seed[0], p0[1] - seed[1]], | |
| v2 = [p1[0] - seed[0], p1[1] - seed[1]]; | |
| // from http://stackoverflow.com/questions/2150050/finding-signed-angle-between-vectors | |
| var angle = Math.atan2( v1[0]*v2[1] - v1[1]*v2[0], v1[0]*v2[0] + v1[1]*v2[1] ); | |
| return (angle<0)? 0 : 1; | |
| } | |
| }; | |
| function segmentCircleIntersections (A, B, C, r) { | |
| /* | |
| from http://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm | |
| */ | |
| var Ax = A[0], Ay = A[1], | |
| Bx = B[0], By = B[1], | |
| Cx = C[0], Cy = C[1]; | |
| // compute the euclidean distance between A and B | |
| LAB = Math.sqrt(Math.pow(Bx-Ax, 2)+Math.pow(By-Ay, 2)); | |
| // compute the direction vector D from A to B | |
| var Dx = (Bx-Ax)/LAB; | |
| var Dy = (By-Ay)/LAB; | |
| // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1. | |
| // compute the value t of the closest point to the circle center (Cx, Cy) | |
| var t = Dx*(Cx-Ax) + Dy*(Cy-Ay); | |
| // This is the projection of C on the line from A to B. | |
| // compute the coordinates of the point E on line and closest to C | |
| var Ex = t*Dx+Ax; | |
| var Ey = t*Dy+Ay; | |
| // compute the euclidean distance from E to C | |
| var LEC = Math.sqrt(Math.pow(Ex-Cx, 2)+Math.pow(Ey-Cy, 2)); | |
| // test if the line intersects the circle | |
| if( LEC < r ) | |
| { | |
| // compute distance from t to circle intersection point | |
| var dt = Math.sqrt(Math.pow(r, 2)-Math.pow(LEC, 2)); | |
| var tF = (t-dt); // t of first intersection point | |
| var tG = (t+dt); // t of second intersection point | |
| var result = []; | |
| if ((tF>0)&&(tF<LAB)) { // test if first intersection point in segment | |
| // compute first intersection point | |
| var Fx = (t-dt)*Dx + Ax; | |
| var Fy = (t-dt)*Dy + Ay; | |
| result.push([Fx, Fy]) | |
| } | |
| if ((tG>0)&&(tG<LAB)) { // test if second intersection point in segment | |
| // compute second intersection point | |
| var Gx = (t+dt)*Dx + Ax; | |
| var Gy = (t+dt)*Dy + Ay; | |
| result.push([Gx, Gy]) | |
| } | |
| return result; | |
| } else { | |
| // either (LEC === r), tangent point to circle is E | |
| // or (LEC < r), line doesn't touch circle | |
| // in both cases, returning nothing is OK | |
| return []; | |
| } | |
| } | |
| </script> | |
| </body> |
