Skip to content

Instantly share code, notes, and snippets.

@bricof
Last active July 12, 2016 06:55
Show Gist options
  • Save bricof/f1f5b4d4bc02cad4dea454a3c5ff8ad7 to your computer and use it in GitHub Desktop.
Save bricof/f1f5b4d4bc02cad4dea454a3c5ff8ad7 to your computer and use it in GitHub Desktop.
Path-Line Intersection
license: gpl-3.0

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.

For uses of this functionality, see the Path-Line Reflection and Bottled Gas Animation blocks.

<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment