1wheel/index.html

## readme.md

      
    Raw
  

              readme.md
            
          
    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) })
// })


## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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>
	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(widthMath.random(), lineStarts[i2 + 0], color)
	var p1 = P(widthMath.random(), lineStarts[i2 + 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) })
	// })