Coincident line segment intersection (v3)

Revision 3 of this benchmark created on

Description

Two methods to determine if line segments intersect (assuming lines are coincident):

1) rotate parallel with x-axis and use x-coords to determine. 2) translate to origin and use magnitudes to determine.

Preparation HTML

<script>
  function rangesIntersect(low1, high1, low2, high2) {
    return low1 <= high2 && low2 <= high1
  }

  function ccw(x1, y1, x2, y2, x3, y3) {
    return (y3 - y1) * (x2 - x1) > (y2 - y1) * (x3 - x1)
  }

  function mag(x, y) {
    return Math.sqrt(x * x + y * y);
  }

  var seg1 = {
    x1: 0,
    y1: 0,
    x2: 1,
    y2: 1
  };

  var seg2 = {
    x1: 1,
    y1: 1,
    x2: 2,
    y2: 2
  };
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Rotation
var angleToRotate = -Math.atan2(seg1.y2 - seg1.y1, seg1.x2 - seg1.x1),
    cosAngle = Math.cos(angleToRotate),
    sinAngle = Math.sin(angleToRotate),
    x1 = seg1.x1 * cosAngle - seg1.y1 * sinAngle,
    x2 = seg1.x2 * cosAngle - seg1.y2 * sinAngle,
    x3 = seg2.x1 * cosAngle - seg2.y1 * sinAngle,
    x4 = seg2.x2 * cosAngle - seg2.y2 * sinAngle;
rangesIntersect(x1, x2, x3, x4);
ready
Translate + Mag
var xOrigin = Math.min(seg1.x1, seg1.x2, seg2.x1, seg2.x2),
    yOrigin;
if (seg1.x1 === xOrigin) {
  if (seg1.x2 === xOrigin) { // vertical lines, use y's instead
    yOrigin = Math.min(seg1.y1, seg1.y2, seg2.y1, seg2.y2);
    if (seg1.y1 === yOrigin) {
      xOrigin = seg1.x1;
    } else if (seg1.y2 === yOrigin) {
      xOrigin = seg1.x2;
    } else if (seg2.y1 === yOrigin) {
      xOrigin = seg2.x1;
    } else {
      xOrigin = seg2.x2;
    }

  } else {
    yOrigin = seg1.y1;
  }
} else if (seg1.x2 === xOrigin) {
  yOrigin = seg1.y2;
} else if (seg2.x1 === xOrigin) {
  yOrigin = seg2.y1;
} else {
  yOrigin = seg2.y2;
}

var mag1 = mag(seg1.x1 - xOrigin, seg1.y1 - yOrigin),
    mag2 = mag(seg1.x2 - xOrigin, seg1.y2 - yOrigin),
    mag3 = mag(seg2.x1 - xOrigin, seg2.y1 - yOrigin),
    mag4 = mag(seg2.x2 - xOrigin, seg2.y2 - yOrigin);

rangesIntersect(mag1, mag2, mag3, mag4);
ready
Switch Translate + Mag
var xOrigin = Math.min(seg1.x1, seg1.x2, seg2.x1, seg2.x2),
    yOrigin;
switch (xOrigin) {
case seg1.x1:
  if (seg1.x2 === xOrigin) { // vertical lines, use y's instead
    yOrigin = Math.min(seg1.y1, seg1.y2, seg2.y1, seg2.y2);
    switch (yOrigin) {
    case seg1.y1:
      xOrigin = seg1.x1;
      break;
    case seg1.y2:
      xOrigin = seg1.x2;
      break;
    case seg2.y1:
      xOrigin = seg2.x1;
      break;
    case seg2.y2:
      xOrigin = seg2.x2;
      break;
    }
  } else {
    yOrigin = seg1.y1;
  }
  break;
case seg1.x2:
  yOrigin = seg1.y2;
  break;
case seg2.x1:
  yOrigin = seg2.y1;
  break;
case seg2.x2:
  yOrigin = seg2.y2;
  break;
}


var mag1 = mag(seg1.x1 - xOrigin, seg1.y1 - yOrigin),
    mag2 = mag(seg1.x2 - xOrigin, seg1.y2 - yOrigin),
    mag3 = mag(seg2.x1 - xOrigin, seg2.y1 - yOrigin),
    mag4 = mag(seg2.x2 - xOrigin, seg2.y2 - yOrigin);

rangesIntersect(mag1, mag2, mag3, mag4);
ready
CCW
ccw(seg1.x1, seg1.y1, seg2.x1, seg2.y1, seg2.x2, seg2.y2) != ccw(seg1.x2, seg1.y2, seg2.x1, seg2.y1, seg2.x2, seg2.y2) && ccw(seg1.x1, seg1.y1, seg1.x2, seg1.y2, seg2.x1, seg2.y1) != ccw(seg1.x1, seg1.y1, seg1.x2, seg1.y2, seg2.x2, seg2.y2);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.