Line Segment Intersection

line-segment-intersection.ts

// based on: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

import test from 'ava';

export interface Point2D {
  readonly x: number;
  readonly y: number;
}

export class LineSegment {
  public readonly start: Point2D;
  public readonly end: Point2D;

  public readonly length: number;
  public readonly direction: Point2D;

  constructor(start: Point2D, end: Point2D) {
    this.start = start;
    this.end = end;

    this.length = distance(start, end);

    if (this.length === 0 || isNaN(this.length) || !isFinite(this.length)) {
      throw new Error('Invalid length');
    }

    this.direction = {
      x: end.x - start.x,
      y: end.y - start.y,
    };
  }
}

export function distance(p1: Point2D, p2: Point2D): number {
  const distance = Math.sqrt(Math.pow(p2.y - p1.y, 2) + Math.pow(p2.x - p1.x, 2));

  return distance;
}

export function subtractPoints(a: Point2D, b: Point2D): Point2D {
  return { x: a.x - b.x, y: a.y - b.y };
}

export function addPoints(a: Point2D, b: Point2D): Point2D {
  return { x: a.x + b.x, y: a.y + b.y };
}

function dot(u: Point2D, v: Point2D): number {
  return u.x * v.x + u.y + v.y;
}

/**
 * 2-dimensional vector cross product v × w = vx wy − vy wx
 */
function cross(v: Point2D, w: Point2D): number {
  return v.x * w.y - v.y * w.x;
}

type LineSegmentIntersectionResult =
 { type: 'colinear-overlapping', ls0t0: number, ls0t1: number } |
 { type: 'colinear-disjoint' } |
 { type: 'parallel-non-intersecting' } |
 { type: 'intersection', ls0t: number, ls1u: number } |
 { type: 'no-intersection' } |
 never;

const epsilon = 1 / 1000000;
function equals0(x: number) {
  return Math.abs(x) < epsilon;
}

/**
 *
 * p + t r = q + u s
 *
 */
function intersection(ls0: LineSegment, ls1: LineSegment): LineSegmentIntersectionResult {
  const p = ls0.start;
  const r = ls0.direction;
  const q = ls1.start;
  const s = ls1.direction;

  // r × s
  const r_s = cross(r, s);
  // (q − p) × r
  const q_p_r = cross(subtractPoints(q, p), r);

  if (equals0(r_s) && equals0(q_p_r)) {
    // t0 = (q − p) · r / (r · r)
    // const t0 = dot(subtractPoints(q, p), r) / dot(r, r);

    // t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r)
    // const t1 = t0 + dot(s, r) / dot(r, r);

    // NOTE(tp): For some reason (which I haven't spotted yet), the above t0 and hence t1 is wrong
    // So resorting to calculating it 'backwards'
    const t1 = dot(addPoints(q, subtractPoints(s, p)), r) / dot(r, r);
    const t0 = t1 - dot(s, r) / dot(r, r);

    if (t0 >= 0 && t0 <= 1 || t1 >= 0 && t1 <= 1) {
      return { type: 'colinear-overlapping', ls0t0: t0, ls0t1: t1 };
    }

    return { type: 'colinear-disjoint' };
  }

  if (equals0(r_s) && !equals0(q_p_r)) {
    return { type: 'parallel-non-intersecting' };
  }

  // t = (q − p) × s / (r × s)
  const t = cross(subtractPoints(q, p), s) / cross(r, s);

  // u = (q − p) × r / (r × s)
  const u = cross(subtractPoints(q, p), r) / cross(r, s);

  if (!equals0(r_s) && t >= 0 && t <= 1 && u >= 0 && u <= 1) {
    return { type: 'intersection', ls0t: t, ls1u: u };
  }

  return { type: 'no-intersection' };
}

test('Line Segment', (t) => {
  {
    const ls0 = new LineSegment({ x: 0, y: 0}, { x: 2, y: 2});

    t.true(ls0.direction.x === 2);
    t.true(ls0.direction.y === 2);
  }

  {
    const ls1 = new LineSegment({ x: 1, y: 1}, { x: 2, y: 2});

    t.true(ls1.direction.x === 1);
    t.true(ls1.direction.y === 1);
  }
});

test('colinear overlapping (same)', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 4, y: 4});

  const result = intersection(ls0, ls0);

  if (result.type !== 'colinear-overlapping') {
    t.fail();
    return;
  }

  t.deepEqual(result.ls0t0, 0);
  t.deepEqual(result.ls0t1, 1);
});

test('colinear overlapping (partially)', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 2, y: 0});
  const ls1 = new LineSegment({ x: 1, y: 0}, { x: 3, y: 0});

  const result = intersection(ls0, ls1);

  if (result.type !== 'colinear-overlapping') {
    t.fail();
    return;
  }

  t.deepEqual(result.ls0t0, 0.5);
  t.deepEqual(result.ls0t1, 1.5);
});

test('colinear overlapping (inside)', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 4, y: 0});
  const ls1 = new LineSegment({ x: 1, y: 0}, { x: 3, y: 0});

  const result = intersection(ls0, ls1);

  if (result.type !== 'colinear-overlapping') {
    t.fail();
    return;
  }

  t.deepEqual(result.ls0t0, 0.25);
  t.deepEqual(result.ls0t1, 0.75);
});

test('colinear disjoint', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 1, y: 1});
  const ls1 = new LineSegment({ x: 2, y: 2}, { x: 3, y: 3});

  const result = intersection(ls0, ls1);

  if (result.type !== 'colinear-disjoint') {
    t.fail();
    return;
  }

  t.pass();
});

test('no intersection', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 1, y: 1});
  const ls1 = new LineSegment({ x: 2, y: 0}, { x: 2, y: 10});

  const result = intersection(ls0, ls1);

  if (result.type !== 'no-intersection') {
    t.fail();
    return;
  }

  t.pass();
});

test('intersection', (t) => {
  const ls0 = new LineSegment({ x: -1, y: 0}, { x: 1, y: 0});
  const ls1 = new LineSegment({ x: 0, y: -1}, { x: 0, y: 1});

  const result = intersection(ls0, ls1);

  if (result.type !== 'intersection') {
    t.fail();
    return;
  }

  t.deepEqual(result.ls0t, 0.5);
  t.deepEqual(result.ls1u, 0.5);
});

test('intersection 2', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 10, y: 0});
  const ls1 = new LineSegment({ x: 9, y: -1}, { x: 9, y: 9});

  const result = intersection(ls0, ls1);

  if (result.type !== 'intersection') {
    t.fail();
    return;
  }

  t.deepEqual(result.ls0t, 0.9);
  t.deepEqual(result.ls1u, 0.1);
});

test('parallel', (t) => {
  const ls0 = new LineSegment({ x: 0, y: 0}, { x: 2, y: 2});
  const ls1 = new LineSegment({ x: 1, y: 0}, { x: 3, y: 2});

  const result = intersection(ls0, ls1);

  t.true(result.type === 'parallel-non-intersecting');
});

Good implementation.
BTW there is a bug in dot product. It has to be u.x * v.x + u.y * v.y (* between ys).