line-intersection

readme.md

The Bentley–Ottmann algorithm finds all the intersections that occur in a set of line segments. Drag the endpoints of the line to move, click to add and right click to remove.

Instead of calculating the intersection of every pair of segments, which would require O(n²) comparisons for a set of n lines, the algorithm uses a sweep line. Starting at the top of the screen and moving down, it keeps track of the order of the lines' x positions at the current y position (represented by the figure on the right). As lines start, end or intersect, new pairs of lines become adjacent in the x ordering and are checked for intersections.

A set of lines with I intersections ends up only requiring O(n log n + I log n) operations. Computational Geometry: Algorithms and Applications, chapter 2 has a proof and a more detailed explanation.

geometry.js

//creates new point 
function P(x, y, color){
  var rv
  if (x.map){
    rv = {x: x[0], y: x[1], color: 'black'}
  } else{
    rv = {x: x, y: y, color: color || 'black'}
  }
  rv.toString = function(){ return rv.x + ',' + rv.y }
  rv.type = 'point'
  return rv
}

function clone(d){
  if (d.type == 'point'){
    return P(d.x, d.y, d.color)
  }
}

//dist
function distP(a, b){
  return Math.sqrt(
    Math.pow(a.x - b.x, 2) + 
    Math.pow(a.y - b.y, 2))
}

//http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
//todo clean up
function distLine(a, b, p){
  function sqr(x) { return x * x }
  function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
  function distToSegmentSquared(p, v, w) {
    var l2 = dist2(v, w);
    if (l2 == 0) return dist2(p, v);
    var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    if (t < 0) return dist2(p, v);
    if (t > 1) return dist2(p, w);
    return dist2(p, { x: v.x + t * (w.x - v.x),
                      y: v.y + t * (w.y - v.y) });
  }
  function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }
  return distToSegment(p, a, b)
}

function calcAngle(a, b, c){
  var v1 = [b.x - a.x, b.y - a.y]
  var v2 = [c.x - b.x, c.y - b.y]
  
  var dot = v1[0]*v2[0] + v1[1]*v2[1]

  var ab = distP(a, b)
  var bc = distP(b, c)
  var ca = distP(c, a)

  return Math.acos((bc*bc + ab*ab - ca*ca)/(2*bc*ab))//*180/Math.PI
  // return Math.acos((bc*bc + ab*ab - ca*ca)/(2*bc*ab))*180/Math.PI
}


//intersection between lines connect points [a, b] and [c, d]
function intersection(a, b, c, d){
  var det = (a.x - b.x)*(c.y - d.y) 
          - (a.y - b.y)*(c.x - d.x),

  l = a.x*b.y - a.y*b.x,
  m = c.x*d.y - c.y*d.x,

  ix = (l*(c.x - d.x) - m*(a.x - b.x))/det,
  iy = (l*(c.y - d.y) - m*(a.y - b.y))/det,
  i = P(ix, iy)

  i.isOverlap = (ix == a.x && iy == a.y) || (ix == b.x && iy == b.y)

  i.isIntersection = !(a.x < ix ^ ix < b.x) 
                  && !(c.x < ix ^ ix < d.x)
                  && !i.isOverlap
                  && det

  // if (isNaN(i.x)) debugger

  return i
}

function isLeft(a, b, c){
  return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x) > 0
}

//http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d-triangle
function triangleContains(a, b, c, p){
  var b1 = isLeft(p, a, b)
  var b2 = isLeft(p, b, c)
  var b3 = isLeft(p, c, a)

  return (b1 == b2) && (b2 == b3)
}

function lineXatY(l, y){
  var a = l[0], b = l[1],
      m = (a.y - b.y)/(a.x - b.x)

  return (y - a.y + m*a.x)/m 
}


function toPathStr(d){ return 'M' + d.join('L') }

function negFn(d){ return !d }

function clamp(a,b,c){ return Math.max(a, Math.min(b, c)) }

function pairs(array){
  var rv = []
  array.forEach(function(d, i){
    for (var j = i + 1; j < array.length; j++) rv.push([d, array[j]])
  })

  return rv
}


function mod(n, m){ return ((n % m) + m) % m }




function tree(array){
  var key = function(d){ return d }
  var bisect = d3.bisector(function(d){ return key(d) }).left

  array.insert = function(d){
    var i = array.findIndex(d)
    var val = key(d)
    if (array[i] && val == key(array[i])) return // don't add dupes
    array.splice(i, 0, d)
    return i
  }

  array.remove = function(d){
    var i = array.findIndex(d)
    array.splice(i, 1)
    return i
  }

  array.swap = function(i, j){

  }

  array.findIndex = function(d){ return bisect(array, key(d)) }

  array.key = function(_){
    key = _ 
    return array
  }

  array.order = function(){
    array.sort(d3.ascendingKey(key))
    return array
  }

  return array
}

index.html

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

<style>
body{
	max-width: 960px;
	margin: 0px auto;
	font-family: monospace;
}

.point{
	stroke: black;
	cursor: pointer;
}

.line{
	stroke: black;
	stroke-width: 2;
	pointer-events: none;
}

.pairpath{
	fill: none;
	stroke: black;
	pointer-events: none;
}

svg{
	overflow: visible;
	border: 1px solid #ccc;
}
</style>

<div id='graph'></div>

<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='geometry.js'></script>


<script src='intersection-drag.js'></script>

intersection-drag.js

var w = 960, h = 500, dragW = 960 - 200 , ε = 1e-9
var points = []
var drag = d3.behavior.drag().on('drag', function(d){
  d.x = clamp(0, d3.event.x, dragW)
  d.y = clamp(0, d3.event.y, h)
  render()
})

var svg = d3.select('#graph').append('svg')
    .attr({width: w, height: h})

svg.append('path').attr('d', 'M' + dragW + ',0v' + h).style('stroke', '#ccc')

svg.append('rect').attr({width: w, height: h, opacity: 0})
    .on('click', function(){
      points.push(P(d3.mouse(this)))
      render()
    })

var colors = ['#F44336', '#2196F3', '#4CAF50', '#9C27B0', '#FF9800', '#795548']
colors = colors.concat(colors.map(function(d){ return d3.rgb(d).brighter(2) }))
colors = colors.concat(colors.map(function(d){ return d3.rgb(d).darker(3) }))

var queueLine = d3.svg.line()
    .x(function(d){ return d.x*20 + dragW + 20})
    .y(ƒ('y'))

//copy(JSON.stringify(points.map(function(d){ return [d.x, d.y].map(Math.round) })))
// points = [[611,341],[488,318],[388,336],[413,484],[655,216],[783,360],[798,245],[716,6],[546,126],[782,65],[314,177],[356,394]].map(P)
// points = [[916,299],[779,477],[640,367],[716,6],[793,131],[787,87]].map(P)
// points = [[646,89],[783,360],[486,462],[782,65],[846,140],[365,422]].map(P)
// points = [[581,205],[326,442],[120,74],[590,473],[309,129],[456,297]].map(P)
// points = [[375,486],[581,21],[644,265],[111,265],[315,382],[327,135]].map(P)
points = [[200,12],[612,401],[375,486],[581,21],[680,25],[106,414],[135,478],[333,51],[120,74],[590,473]].map(P)
render()


function render(){
  lines = []
  points.forEach(function(d, i){
    if (i % 2) lines.push(_.sortBy([d, points[i - 1]], 'y')) })

  openColors = colors.slice() 
  lines.forEach(function(d, i){
    if (d[0].x == d[1].x) d[0].x += ε
    if (d[0].y == d[1].y) d[0].y -= ε

    //don't change colors on remove
    d.color = d[0].line && d[0].line.color ? d[0].line.color : openColors[0]
    d[0].line = d
    d[1].line = d

    openColors = openColors.filter(function(color){ return color != d.color })
  })


  calcQueue()


  var lineSel = svg.selectAll('path.line').data(lines)
  lineSel.enter().append('path.line')
  lineSel.style({stroke: ƒ('color')}).attr('d', toPathStr)
  lineSel.exit().remove()

  svg.selectAll('circle.intersection').remove()
  svg.dataAppend(intersections, 'circle.intersection')
      .attr({cx: ƒ('x'), cy: ƒ('y'), r: 5, fill: 'none', stroke: '#000'})

  var circleSel = svg.selectAll('g.point').data(points)
  var circleEnter = circleSel.enter().append('g.point')
      .call(drag)
      .on('contextmenu', function(d){
        d3.event.preventDefault()
        points = points.filter(function(e){ return d != e && !_.contains(d.line, e) })
        render()
      })
  circleEnter.append('circle').attr('r', 7)

  circleSel
      .translate(ƒ())
    .filter(ƒ('line'))
      .style('fill', ƒ('line', 'color'))

  circleSel.exit().remove()


  linesByY.forEach(function(d){
    d.positions = []
    d.queuePositions.forEach(function(p, i){
      d.positions.push(p)
      var nextY = d.queuePositions[i + 1] && d.queuePositions[i + 1].y
      if (nextY > p.y + 10){
        d.positions.push({x: p.x, y: nextY - 10})
      }
    })
  })

  var queueSel = svg.selectAll('path.queue').data(linesByY)
  queueSel.enter().append('path.queue')
  queueSel
      .style({stroke: ƒ('color'), fill: 'none', 'stroke-width': 3})
      .attr('d', function(d){ return queueLine(_.sortBy(d.positions, 'y')) })
  queueSel.exit().remove()
}



function calcQueue(){
  queue = tree(points.slice())
    .key(function(d){ return d.y + ε*d.x })
    .order()

  intersections = []


  linesByY = _.sortBy(lines, ƒ(0, 'y'))
  linesByY.forEach(function(d){
    d.queuePositions = []
  })

  statusT = tree([])


  for (var i = 0; i < queue.length && i < 1000; i++){
    var d = queue[i]
    var y = d.y
    if (d.line && d.line[0] == d){
      // insert
      d.color = d.line.color
      d.type = 'insert'
      var index = statusT
          .key(function(e){ return lineXatY(e, d.y - ε/1000) })
          .insert(d.line)
      checkIntersection(d.line, statusT[index + 1])
      checkIntersection(d.line, statusT[index - 1])

    } else if (d.line){
      // removal 
      d.color = d.line.color
      d.type = 'removal'

      var index = statusT.findIndex(d.line)
      statusT.remove(d.line)

      d.line.queuePositions.push({x: index, y: Math.max(y - 10, queue[i - 1].y)})
      checkIntersection(statusT[index - 1], statusT[index])
    } else if (d.lineA && d.lineB){
      // intersection
      statusT.key(function(e){ return lineXatY(e, d.y - ε/1000) })

      var indexA = statusT.findIndex(d.lineA)
      var indexB = statusT.findIndex(d.lineB)
      if (indexA == indexB) indexA = indexA + 1
      statusT[indexA] = d.lineB
      statusT[indexB] = d.lineA

      var minIndex = indexA < indexB ? indexA : indexB
      checkIntersection(statusT[minIndex - 1], statusT[minIndex])
      checkIntersection(statusT[minIndex + 1], statusT[minIndex + 2])
    }


    statusT.forEach(function(d, i){
      d.queuePositions.push({x: i, y: y})
    })

  }

  function checkIntersection(a, b){
    if (!a || !b) return 
    var i = intersection(a[0], a[1], b[0], b[1])
    i.lineA = a
    i.lineB = b
    if (i.isIntersection) intersections.push(i) && queue.insert(i)
  }

}

preview.png

thumbnail.png

Very Nice! Just tested an interesting corner case: