1wheel/disjoint-sections.js

## readme.md

      
    Raw
  

              readme.md
            
          
    Let S be a set of n disjoint line segments whose upper endpoints lie on the line y = 1 and whose lower endpoints lie on the line y = 0. These segments partition the horizontal strip [−∞ : ∞] × [0 : 1] into n + 1 regions. Give an O(nlogn) time algorithm to build a binary search tree on the segments in S such that the region containing a query point can be determined in O(log n) time. Also describe the query algorithm in detail.

  
## disjoint-sections.js
var m = 10
    width  = 960 - m*2,
    height = 500 - m*2,
    numLines = 15


function randomWidth(d){ return Math.floor(Math.random()*width/15)*15 }

var topPoints = _.uniq(d3.range(numLines*2).map(randomWidth)).slice(0, numLines).sort(d3.ascending)
var botPoints = _.uniq(d3.range(numLines*2).map(randomWidth)).slice(0, numLines).sort(d3.ascending)

var lines = topPoints.map(function(d, i){
  return [d, botPoints[i]]
})


//draw top regions
var svg = d3.select('html')
  .append('svg')
    .attr({width: width + m*2, height: height + m*2})
  .append('g')
    .translate([m, m])

svg.dataAppend([0, 100], 'path.q')
    .attr('d', function(d){ return 'M0,' + d + 'h' + width })

svg.dataAppend(lines, 'path.connection')
    .attr('d', function(d){
      return ['M', [d[0], 0], 'L', [d[1], 100]].join('') })

svg.dataAppend([topPoints, botPoints], 'g')
    .translate(function(d, i){ return [0, i ? 100 : 0] })
  .dataAppend(ƒ(), 'circle')
    .attr('cx', ƒ())
    .attr('r', 5)


var depth = Math.max(Math.log2(numLines))

var x = d3.scale.linear().domain([0, numLines]).range([0, width])
var y = d3.scale.linear().domain([0, depth - 1]).range([height, 150])

function balanceTree(array, depth){
  var l = array.length
  if (!l) return {}
  var mI = Math.floor(l/2)
  console.log(depth)
  return {
    val:    array[mI],
    left:   balanceTree(array.slice(0, mI), depth + 1),
    right:  balanceTree(array.slice(mI + 1, l), depth + 1),
    i: mI,
    depth: depth,
    pos: [x(botPoints.indexOf(array[mI])), y(depth)]
  }
}
var tree = balanceTree(botPoints, 0)


function addChild(tree){
  if (!tree.pos) return
  svg.append('path')
      .style('stroke', 'lightgrey')
      .attr('d', ['M', tree.pos, 'L', tree.val, ',100'].join(''))

  svg.append('path')
      .style('stroke', 'black')
      .attr('d', ['M', tree.pos, 'L', tree.left.pos, ',100'].join(''))
  svg.append('path')
      .style('stroke', 'black')
      .attr('d', ['M', tree.pos, 'L', tree.right.pos, ',100'].join(''))


  if (tree.left ) addChild(tree.left)
  if (tree.right) addChild(tree.right)
  svg.append('circle')
      .datum(tree)
      .attr('r', 5)
      .translate(tree.pos)
}
addChild(tree)


## index.html
<!DOCTYPE html>
<meta charset="utf-8">

<style>
circle{
	fill: #eee;
	stroke: black;
}
.q{
	stroke: black;
	stroke-dasharray: 2 4 2 6;
}

.connection{
	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='disjoint-sections.js'></script>

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	var m = 10
	width = 960 - m*2,
	height = 500 - m*2,
	numLines = 15


	function randomWidth(d){ return Math.floor(Math.random()width/15)15 }

	var topPoints = _.uniq(d3.range(numLines*2).map(randomWidth)).slice(0, numLines).sort(d3.ascending)
	var botPoints = _.uniq(d3.range(numLines*2).map(randomWidth)).slice(0, numLines).sort(d3.ascending)

	var lines = topPoints.map(function(d, i){
	return [d, botPoints[i]]
	})


	//draw top regions
	var svg = d3.select('html')
	.append('svg')
	.attr({width: width + m2, height: height + m2})
	.append('g')
	.translate([m, m])

	svg.dataAppend([0, 100], 'path.q')
	.attr('d', function(d){ return 'M0,' + d + 'h' + width })

	svg.dataAppend(lines, 'path.connection')
	.attr('d', function(d){
	return ['M', [d[0], 0], 'L', [d[1], 100]].join('') })

	svg.dataAppend([topPoints, botPoints], 'g')
	.translate(function(d, i){ return [0, i ? 100 : 0] })
	.dataAppend(ƒ(), 'circle')
	.attr('cx', ƒ())
	.attr('r', 5)


	var depth = Math.max(Math.log2(numLines))

	var x = d3.scale.linear().domain([0, numLines]).range([0, width])
	var y = d3.scale.linear().domain([0, depth - 1]).range([height, 150])

	function balanceTree(array, depth){
	var l = array.length
	if (!l) return {}
	var mI = Math.floor(l/2)
	console.log(depth)
	return {
	val: array[mI],
	left: balanceTree(array.slice(0, mI), depth + 1),
	right: balanceTree(array.slice(mI + 1, l), depth + 1),
	i: mI,
	depth: depth,
	pos: [x(botPoints.indexOf(array[mI])), y(depth)]
	}
	}
	var tree = balanceTree(botPoints, 0)


	function addChild(tree){
	if (!tree.pos) return
	svg.append('path')
	.style('stroke', 'lightgrey')
	.attr('d', ['M', tree.pos, 'L', tree.val, ',100'].join(''))

	svg.append('path')
	.style('stroke', 'black')
	.attr('d', ['M', tree.pos, 'L', tree.left.pos, ',100'].join(''))
	svg.append('path')
	.style('stroke', 'black')
	.attr('d', ['M', tree.pos, 'L', tree.right.pos, ',100'].join(''))


	if (tree.left ) addChild(tree.left)
	if (tree.right) addChild(tree.right)
	svg.append('circle')
	.datum(tree)
	.attr('r', 5)
	.translate(tree.pos)
	}
	addChild(tree)
	<!DOCTYPE html>
	<meta charset="utf-8">

	<style>
	circle{
	fill: #eee;
	stroke: black;
	}
	.q{
	stroke: black;
	stroke-dasharray: 2 4 2 6;
	}

	.connection{
	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='disjoint-sections.js'></script>