This example shows how to compute the intersection point between two line segments, using an algorithm derived from this in-depth StackOverflow discussion. Drag the gray nodes to see the algorithm at work.
(function() {
var drag, get_intersection, height, intersection, lines_data, points_data, redraw, svg, width;
get_intersection = function(p0, p1, p2, p3) {
var s, s1_x, s1_y, s2_x, s2_y, t;
s1_x = p1.x - p0.x;
s1_y = p1.y - p0.y;
s2_x = p3.x - p2.x;
s2_y = p3.y - p2.y;
s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
t = (s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
return {
x: p0.x + (t * s1_x),
y: p0.y + (t * s1_y)
};
}
return null;
};
points_data = [
{
x: -200,
y: 200
}, {
x: 200,
y: -200
}, {
x: -200,
y: -200
}, {
x: 200,
y: 200
}
];
lines_data = [
{
start: points_data[0],
end: points_data[1]
}, {
start: points_data[2],
end: points_data[3]
}
];
svg = d3.select('svg');
width = svg.node().getBoundingClientRect().width;
height = svg.node().getBoundingClientRect().height;
svg.attr({
viewBox: "" + (-width / 2) + " " + (-height / 2) + " " + width + " " + height
});
drag = d3.behavior.drag().origin(function(d) {
return d;
});
drag.on('drag', function(d) {
d.x = d3.event.x;
d.y = d3.event.y;
return redraw();
});
redraw = function() {
var intersection_data, lines, points;
lines = svg.selectAll('.line').data(lines_data);
lines.enter().append('line').attr({
"class": 'line'
});
lines.attr({
x1: function(l) {
return l.start.x;
},
y1: function(l) {
return l.start.y;
},
x2: function(l) {
return l.end.x;
},
y2: function(l) {
return l.end.y;
}
});
points = svg.selectAll('.point').data(points_data);
points.enter().append('circle').call(drag).attr({
"class": 'point',
r: 8
});
points.attr({
cx: function(p) {
return p.x;
},
cy: function(p) {
return p.y;
}
});
intersection_data = get_intersection(points_data[0], points_data[1], points_data[2], points_data[3]);
if (typeof intersection !== "undefined" && intersection !== null) {
return intersection.attr({
cx: intersection_data != null ? intersection_data.x : 0,
cy: intersection_data != null ? intersection_data.y : 0,
display: intersection_data != null ? 'inline' : 'none'
});
}
};
redraw();
intersection = svg.append('circle').attr({
"class": 'intersection',
r: 4
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="description" content="Intersection of two line segments" />
<title>Intersection of two line segments</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="//d3js.org/d3.v3.min.js"></script>
</head>
<body>
<svg height="500" width="960"></svg>
<script src="index.js"></script>
</body>
</html>get_intersection = (p0, p1, p2, p3) ->
s1_x = p1.x - p0.x
s1_y = p1.y - p0.y
s2_x = p3.x - p2.x
s2_y = p3.y - p2.y
s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y)
t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y)
if s >= 0 and s <= 1 and t >= 0 and t <= 1
# intersection
return {x: p0.x + (t * s1_x), y: p0.y + (t * s1_y)}
# else
return null # no intersection
points_data = [{x: -200, y: 200},{x: 200, y: -200},{x: -200, y: -200},{x: 200, y: 200}]
lines_data = [{start: points_data[0], end: points_data[1]},{start: points_data[2], end: points_data[3]}]
svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height
# translate the viewBox to have (0,0) at the center of the vis
svg
.attr
viewBox: "#{-width/2} #{-height/2} #{width} #{height}"
# define a drag behavior
drag = d3.behavior.drag()
.origin((d) -> d)
drag.on 'drag', (d) ->
# update the datum of the dragged node
d.x = d3.event.x
d.y = d3.event.y
# update the representation
redraw()
redraw = () ->
lines = svg.selectAll('.line')
.data(lines_data)
lines.enter().append('line')
.attr
class: 'line'
lines
.attr
x1: (l) -> l.start.x
y1: (l) -> l.start.y
x2: (l) -> l.end.x
y2: (l) -> l.end.y
points = svg.selectAll('.point')
.data(points_data)
points.enter().append('circle')
.call(drag)
.attr
class: 'point'
r: 8
points
.attr
cx: (p) -> p.x
cy: (p) -> p.y
intersection_data = get_intersection(points_data[0], points_data[1], points_data[2], points_data[3])
if intersection?
intersection
.attr
cx: if intersection_data? then intersection_data.x else 0
cy: if intersection_data? then intersection_data.y else 0
display: if intersection_data? then 'inline' else 'none'
redraw()
intersection = svg.append('circle')
.attr
class: 'intersection'
r: 4
svg {
background: white;
}
.point {
fill: #DDD;
stroke: gray;
stroke-width: 2;
}
.line {
stroke: #DDD;
stroke-width: 2;
}
.intersection {
pointer-events: none;
}