segment-intersection.js

// Adapted from http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/1968345#1968345
var eps = 0.0000001;
function between(a, b, c) {
    return a-eps <= b && b <= c+eps;
}
function segment_intersection(x1,y1,x2,y2, x3,y3,x4,y4) {
    var x=((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4)) /
            ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    var y=((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4)) /
            ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    if (isNaN(x)||isNaN(y)) {
        return false;
    } else {
        if (x1>=x2) {
            if (!between(x2, x, x1)) {return false;}
        } else {
            if (!between(x1, x, x2)) {return false;}
        }
        if (y1>=y2) {
            if (!between(y2, y, y1)) {return false;}
        } else {
            if (!between(y1, y, y2)) {return false;}
        }
        if (x3>=x4) {
            if (!between(x4, x, x3)) {return false;}
        } else {
            if (!between(x3, x, x4)) {return false;}
        }
        if (y3>=y4) {
            if (!between(y4, y, y3)) {return false;}
        } else {
            if (!between(y3, y, y4)) {return false;}
        }
    }
    return {x: x, y: y};
}

Hmm this didn't work for me for some reason. It didn't find points for certain lines. For example:

const l1 = new Line(new Point(-20, 20), new Point(18, 5))
const l2 = new Line(new Point(-15, 20), new Point(0, 0))

This worked for me:

class Line{
  // ...
  lineSegmentInterception(line: Line): Point | undefined {
    const p0 = this.point1, p1 = this.point2,
          p2 = line.point1, p3 = line.point2
    const s10_x = p1.x - p0.x, s10_y = p1.y - p0.y,
          s32_x = p3.x - p2.x, s32_y = p3.y - p2.y
    const denom = s10_x * s32_y - s32_x * s10_y
    if(denom == 0) return undefined // collinear
    const s02_x = p0.x - p2.x,
          s02_y = p0.y - p2.y
    const s_numer = s10_x * s02_y - s10_y * s02_x
    if(s_numer < 0 == denom > 0) return undefined // no collision
    const t_numer = s32_x * s02_y - s32_y * s02_x
    if(t_numer < 0 == denom > 0) return undefined // no collision
    if(s_numer > denom == denom > 0 || t_numer > denom == denom > 0) return undefined // no collision
    // collision detected
    const t = t_numer / denom
    return new Point(p0.x + (t * s10_x), p0.y + (t * s10_y))
  }
}

TypeScript version based on this StackOverflow answer https://stackoverflow.com/posts/19550879/revisions

lineSegmentInterception(line: Line): Point | undefined {
const p0 = this.point1, p1 = this.point2,
p2 = line.point1, p3 = line.point2
const s10_x = p1.x - p0.x, s10_y = p1.y - p0.y,
s32_x = p3.x - p2.x, s32_y = p3.y - p2.y
const denom = s10_x * s32_y - s32_x * s10_y
if(denom == 0) return undefined // collinear
const s02_x = p0.x - p2.x,
s02_y = p0.y - p2.y
const s_numer = s10_x * s02_y - s10_y * s02_x
if(s_numer < 0 == denom > 0) return undefined // no collision
const t_numer = s32_x * s02_y - s32_y * s02_x
if(t_numer < 0 == denom > 0) return undefined // no collision
if(s_numer > denom == denom > 0 || t_numer > denom == denom > 0) return undefined // no collision
// collision detected
const t = t_numer / denom
return new Point(p0.x + (t * s10_x), p0.y + (t * s10_y))
}

Clearly a best way to do it. No need of epsilon and failproof.

lineSegmentInterception(line: Line): Point | undefined {
const p0 = this.point1, p1 = this.point2,
p2 = line.point1, p3 = line.point2
const s10_x = p1.x - p0.x, s10_y = p1.y - p0.y,
s32_x = p3.x - p2.x, s32_y = p3.y - p2.y
const denom = s10_x * s32_y - s32_x * s10_y
if(denom == 0) return undefined // collinear
const s02_x = p0.x - p2.x,
s02_y = p0.y - p2.y
const s_numer = s10_x * s02_y - s10_y * s02_x
if(s_numer < 0 == denom > 0) return undefined // no collision
const t_numer = s32_x * s02_y - s32_y * s02_x
if(t_numer < 0 == denom > 0) return undefined // no collision
if(s_numer > denom == denom > 0 || t_numer > denom == denom > 0) return undefined // no collision
// collision detected
const t = t_numer / denom
return new Point(p0.x + (t * s10_x), p0.y + (t * s10_y))
}

A master peace! Thank you so much! Would you happen to have something similar for segment - circle intersection?

@YesIDont If I understand you correctly I think you're looking for something like this?

circleInterception(circleCenter: Point, circleRadius: number): Point[]{
    const v1 = new Point(this.point2.x - this.point1.x, this.point2.y - this.point1.y)
    const v2 = new Point(this.point1.x - circleCenter.x, this.point1.y - circleCenter.y)
    const b = (v1.x * v2.x + v1.y * v2.y) * -2
    const c = (v1.x * v1.x + v1.y * v1.y) * 2
    const d = Math.sqrt(b * b - 2 * c * (v2.x * v2.x + v2.y * v2.y - circleRadius * circleRadius))
    if(isNaN(d)) return [] // no intercept
    const u1 = (b - d) / c  // unit distance of line endpoints
    const u2 = (b + d) / c    
    const points: Point[] = []
    if(u1 <= 1 && u1 >= 0) points.push(new Point(this.point1.x + v1.x * u1, this.point1.y + v1.y * u1))
    if(u2 <= 1 && u2 >= 0) points.push(new Point(this.point1.x + v1.x * u2, this.point1.y + v1.y * u2))
    return points
}

(defined on a Line class so that's what this is referring to)