block by 1wheel cbd9053de9bb39231924

n-line intersection

Full Screen

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.

index.html

<!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>

n-line-intersection.js

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) })
// })