D3 Examples - Path-Line Intersection

Path-Line Intersection

This example presents a simple approximate solution to path-line intersection by subdividing the path (via the built-in svg path function .getPointAtLength) into an arbitrary number of straight line segments and testing for line-line intersections at each one. A more accurate solution would be to similarly walk through segments of the path, but instead using the points specified in the path's d definition, and computing the intersections with the lines, Bezier curves and arcs - that approach is forthcoming in another future example. See also Mike Bostock's related example on Line Segment Intersection.

The moveable intersecting line is based on this block.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
​
.polygon line {
  fill: none;
  stroke: #000;
}
​
.polygon circle {
  fill: #000;
  stroke: #fff;
  cursor: move;
}
​
.segment {
  stroke-width: 2px;
}
​
.checkbox {
  float: right;
  margin-top: 8px;
  margin-right: 4px;
}
​
.controls {
  position: absolute;
  width: 940px;
  padding: 10px;
  z-index: 1;
}
​
​
</style>
​
<body>
​
<div class="controls">
<input id="slider" type="range" min="10" max="200" value="100" step="10">
Number of path segments: <span id="n_segments_text">100</span>
​
<input class="checkbox" type="checkbox" id="cbox" value="checkbox"> 
<span class="checkbox">Show segments</span>
</div>
<svg width="960px" height="500px">
<path fill="none" stroke="#000000" stroke-miterlimit="10" d="M512.049,82.693c-8.46,3.561-5.522,11.094-5.522,20.17
    c0,7.092,0.71,14.147,4.609,20.213c9.838,15.304,21.579,22.363,35.181,33.957c22.201,18.925,20.957,44.126,20.957,70.669
    c0,47.12,0,94.24,0,141.36c0,18.958,0,37.916,0,56.874c0,5.832,2.606,22.086-7.904,22.086c-26.991,0-134.957,0-161.948,0
    c-10.51,0-7.904-16.254-7.904-22.086c0-18.958,0-37.916,0-56.874c0-47.12,0-94.24,0-141.36c0-26.544-1.244-51.745,20.957-70.669
    c13.601-11.594,25.343-18.654,35.181-33.957c3.899-6.066,4.609-13.121,4.609-20.213c0-9.077,2.938-16.609-5.522-20.17"/>
</svg>
​
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>
​
var n_segments = 100;
​
var svg = d3.select("svg");
var path = svg.select("path");
​
var color = d3.scale.category10();
​
var segments_g = svg.append("g");
​
var polygon = svg.append("g")
    .attr("class", "polygon")
    .datum([[300, 350], [660, 200]]);
​
var highlights = svg.append("g");
​
polygon.append("line")
    .call(positionLine);
​
polygon.selectAll("circle")
    .data(function(d) { return d; })
  .enter().append("circle")
    .call(positionCircle)
    .attr("r", 4.5)
    .call(d3.behavior.drag()
      .origin(function(d) { return {x: d[0], y: d[1]}; })
      .on("drag", function(d) {
        d[0] = d3.event.x, d[1] = d3.event.y;
        d3.select(this).call(positionCircle);
        polygon.select("line").call(positionLine);
        draw_intersections( path_line_intersections(pathEl, line) )
      }));
​
var pathEl = path.node();
var pathLength = pathEl.getTotalLength();
var line = polygon.select("line");
​
function positionCircle(circle) {
  circle
      .attr("cx", function(d) { return d[0]; })
      .attr("cy", function(d) { return d[1]; });
}
​
function positionLine(line) {
  line
      .attr("x1", function(d) { return d[0][0]; })
      .attr("y1", function(d) { return d[0][1]; })
      .attr("x2", function(d) { return d[1][0]; })
      .attr("y2", function(d) { return d[1][1]; });
}
​
function btwn(a, b1, b2) {
  if ((a >= b1) && (a <= b2)) { return true; }
  if ((a >= b2) && (a <= b1)) { return true; }
  return false;
}
​
function line_line_intersect(line1, line2) {
  var x1 = line1.x1, x2 = line1.x2, x3 = line2.x1, x4 = line2.x2;
  var y1 = line1.y1, y2 = line1.y2, y3 = line2.y1, y4 = line2.y2;
  var pt_denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
  var pt_x_num = (x1*y2 - y1*x2) * (x3 - x4) - (x1 - x2) * (x3*y4 - y3*x4);
  var pt_y_num = (x1*y2 - y1*x2) * (y3 - y4) - (y1 - y2) * (x3*y4 - y3*x4);
  if (pt_denom == 0) { return "parallel"; }
  else { 
    var pt = {'x': pt_x_num / pt_denom, 'y': pt_y_num / pt_denom}; 
    if (btwn(pt.x, x1, x2) && btwn(pt.y, y1, y2) && btwn(pt.x, x3, x4) && btwn(pt.y, y3, y4)) { return pt; }
    else { return "not in range"; }
  }
}
​
function path_line_intersections(pathEl, line) {
​
  var pts = []
  for (var i=0; i<n_segments; i++) {
    var pos1 = pathEl.getPointAtLength(pathLength * i / n_segments);
    var pos2 = pathEl.getPointAtLength(pathLength * (i+1) / n_segments);
    var line1 = {x1: pos1.x, x2: pos2.x, y1: pos1.y, y2: pos2.y};
    var line2 = {x1: line.attr('x1'), x2: line.attr('x2'), 
                 y1: line.attr('y1'), y2: line.attr('y2')};
    var pt = line_line_intersect(line1, line2);
    if (typeof(pt) != "string") {
      pts.push(pt);
    }
  }
  
  return pts;
​
}
​
function draw_intersections(pts) {
​
  highlights.selectAll("circle").remove();
​
  pts.forEach(function(pt){
    highlights.append("circle")
       .attr("cx", pt.x)
       .attr("cy", pt.y)
       .attr("r", 8)
       .attr("fill", "none")
       .attr("stroke", "steelblue");
​
    highlights.append("circle")
       .attr("cx", pt.x)
       .attr("cy", pt.y)
       .attr("r", 2)
       .attr("fill", "steelblue")
       .attr("stroke", "none");
  
  });
​
}
​
function draw_segments() {
​
  segments_g.selectAll("line").remove();
  for (var i=0; i<n_segments; i++) {
    var pos1 = pathEl.getPointAtLength(pathLength * i / n_segments);
    var pos2 = pathEl.getPointAtLength(pathLength * (i+1) / n_segments);
    segments_g.append("line")
       .attr("class", "segment")
       .attr("x1", pos1.x)
       .attr("y1", pos1.y)
       .attr("x2", pos2.x)
       .attr("y2", pos2.y)
       .attr("stroke", color(i));
  }
​
}
​
d3.select("#slider").on("change", function() {
  d3.select("#n_segments_text").text(this.value);
  n_segments = this.value;
  draw_intersections( path_line_intersections(pathEl, line) );
  if (d3.select("#cbox").property("checked")){ draw_segments(); }
});
​
d3.select("#cbox").on("change", function() {
  if (this.checked){ draw_segments(); }
  else { segments_g.selectAll("line").remove(); }
});
​
draw_intersections( path_line_intersections(pathEl, line) );
​
</script>
​
    