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.
Last active
August 29, 2015 14:07
-
-
Save nitaku/fdbb70c3baa36e8feb4e to your computer and use it in GitHub Desktop.
Intersection of two line segments
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| svg { | |
| background: white; | |
| } | |
| .point { | |
| fill: #DDD; | |
| stroke: gray; | |
| stroke-width: 2; | |
| } | |
| .line { | |
| stroke: #DDD; | |
| stroke-width: 2; | |
| } | |
| .intersection { | |
| pointer-events: none; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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="http://d3js.org/d3.v3.min.js"></script> | |
| </head> | |
| <body> | |
| <svg height="500" width="960"></svg> | |
| <script src="index.js"></script> | |
| </body> | |
| </html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment