Calculating the intersections between n line segments can be done in n log n
time. Here, segments are only checked for intersection when they are newly adjacent after a line start, end or intersection. The dots on the left show the order of the lines at each adjacency change, with newly adjacent pairs of lines connect by a black line.
Last active
August 21, 2016 06:22
-
-
Save 1wheel/cbd9053de9bb39231924 to your computer and use it in GitHub Desktop.
n-line intersection
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> | |
<meta charset="utf-8"> | |
<style> | |
.seg{ | |
stroke-width: 4px; | |
} | |
.q{ | |
stroke: black; | |
stroke-dasharray: 2 4 2 6; | |
} | |
.point{ | |
stroke: black; | |
} | |
.check{ | |
stroke: black; | |
} | |
html{ | |
width: 960px; | |
height: 500px; | |
} | |
</style> | |
<script src="/1wheel/raw/67b47524ed8ed829d021/d3-3.5.5.js"></script> | |
<script src="/1wheel/raw/67b47524ed8ed829d021/lodash-3.8.0.js"></script> | |
<script src='/1wheel/raw/1b6758978dc2d52d3a37/d3-jetpack.js'></script> | |
<script src='/1wheel/raw/1b6758978dc2d52d3a37/d3-starterkit.js'></script> | |
<script src='/1wheel/raw/5d32ecb8a54b42f53646/geometry.js'></script> | |
<script src='n-line-intersection.js'></script> |
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
var width = 600, | |
height = 500, | |
lWidth = 360, | |
numLines = 6 | |
var lineStarts = _.shuffle(d3.range(numLines*2).map(function(i){ | |
return i*height/numLines/2 + 10 | |
})) | |
var lines = d3.scale.category10().range() | |
.slice(0, numLines) | |
.map(function(color, i){ | |
var p0 = P(width*Math.random(), lineStarts[i*2 + 0], color) | |
var p1 = P(width*Math.random(), lineStarts[i*2 + 1], color) | |
var rv = [p0, p1].sort(d3.ascendingKey('y')) | |
rv.color = color | |
rv.i = i | |
p0.line = p1.line = rv | |
return rv | |
}) | |
var Q = _.flatten(lines) | |
.map(function(d, i){ | |
d.type = i % 2 ? 'stop' : 'start' | |
return d }) | |
.sort(d3.ascendingKey('y')) | |
var checkedPairs = {} | |
var checks = [] | |
var T = [] | |
var qBisect = d3.bisector(ƒ('y')).left | |
for (var i = 0; i < Q.length; i++){ | |
var p = Q[i] | |
var bisect = d3.bisector(function(d){ return -lineXatY(d, p.y) }).left | |
var rv = i ? _.last(T).slice() : [] | |
rv.checks = [] | |
console.log(p.type) | |
var j | |
if (p.type == 'start'){ | |
j = bisect(rv, -p.x) | |
rv.splice(j, 0, p.line) | |
checkPair(j-1, j) | |
checkPair(j, j+1) | |
} else if (p.type == 'intersection'){ | |
var aIndex = rv.indexOf(p.a) | |
if (isNaN(aIndex)) debugger | |
rv[aIndex] = p.b | |
rv[aIndex + 1] = p.a | |
checkPair(aIndex - 1, aIndex) | |
checkPair(aIndex + 1, aIndex + 2) | |
} else if (p.type == 'stop'){ | |
rv.forEach(function(d, i){ if (d == p.line) j = i }) | |
rv.splice(j, 1) | |
checkPair(j, j+1) | |
} | |
function checkPair(ai, bi){ | |
var a = rv[ai], b = rv[bi] | |
if (!a || !b) return | |
var str = [a.i, b.i].sort().join('-') | |
rv.checks.push({i: i, ai: ai}) | |
if (checkedPairs[str]) return | |
checkedPairs[str] = true | |
var iPoint = intersection(a[0], a[1], b[0], b[1]) | |
iPoint.type = 'intersection' | |
iPoint.a = a | |
iPoint.b = b | |
if (iPoint.isIntersection){ | |
var i = qBisect(Q, iPoint.y) | |
Q.splice(i, 0, iPoint) | |
} | |
} | |
rv.j = j | |
rv.p = p | |
T.push(rv) | |
} | |
var svg = d3.select('html') | |
.append('svg') | |
.attr({width: width + lWidth, height: height}) | |
var segG = svg.append('g') | |
.translate([lWidth, 0]) | |
segG.dataAppend(Q, 'path.q') | |
.attr('d', function(d){ return ['M', [-20, d.y], 'L', d].join('') }) | |
.style('stroke', function(d){ | |
return d.type == 'intersection' ? 'red' : 'black' }) | |
segG.dataAppend(Q, 'circle.point') | |
.attr('r', 5) | |
.translate(ƒ()) | |
.attr('fill', ƒ('color')) | |
segG.dataAppend(lines, 'path.seg') | |
.attr('d', toPathStr) | |
.style('stroke', ƒ('color')) | |
var dsG = svg.append('g') | |
.translate([10, 0]) | |
var qRows = dsG.dataAppend(T, 'g') | |
.translate(function(d){ return [0, d.p.y] }) | |
qRows.dataAppend(ƒ(), 'circle.line') | |
.attr('cx', function(d, i){ return 300 - i*15 }) | |
.attr('r', 5) | |
.attr('fill', ƒ('color')) | |
qRows.dataAppend(ƒ('checks'), 'path.check') | |
.attr('d', function(d){ return 'M' + [300-d.ai*15, 0] + 'h-15' }) | |
// var y = 200 | |
// segG.dataAppend(lines, 'circle.dot') | |
// .attr('cy', y) | |
// .attr('r', 10) | |
// .attr('cx', function(d){ return lineXatY(d, y) }) | |
// .attr('fill', ƒ('color')) | |
// d3.timer(function(t){ | |
// var y = t/2 % height | |
// d3.selectAll('.dot') | |
// .attr('cy', y) | |
// .attr('cx', function(d){ return lineXatY(d, y) }) | |
// }) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment