Skip to content

Instantly share code, notes, and snippets.

@1wheel
Last active November 8, 2022 13:46
Show Gist options
  • Save 1wheel/464141fe9b940153e636 to your computer and use it in GitHub Desktop.
Save 1wheel/464141fe9b940153e636 to your computer and use it in GitHub Desktop.
line-intersection

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.

//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
}
<!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>
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)
}
}
@GordonSmith
Copy link

Very Nice! Just tested an interesting corner case:
image

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment