Intersection of Quadratic bezier path and line

Question

I am working with a svg element that contains a quadratic bezier curve in the form of a SVG path and a vertical line. How do I calculate the intersection between them programmatically?

I have referred to this and when I plug in the numbers from this question it returns the exact same value but not for the original numbers that I have in SVG.

//referred to https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
var lerp = function(a, b, x) { return (a + x * (b - a)); };

// qCurve & line defs - as in https://stackoverflow.com/a/27664883/11156131
//works for the following
/*var p1 = {x:125,y:200};
var p2 = {x:250,y:225};
var p3 = {x:275,y:100};
var a1 = {x:30,y:125};
var a2 = {x:300,y:175};*/

// current svg  points
//does not work for following
var p1 = { x: 200, y: 300 };
var p2 = { x: 640, y: 175 };
var p3 = { x: 1080, y: 300 };
var a1 = { x: 640, y: 50 };
var a2 = { x: 640, y: 550 };


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);

// Display the intersection points
var textPoints = 'Intersections: ';
for (var i = 0; i < points.length; i++) {
  var p = points[i];
  textPoints += ' [' + parseInt(p.x) + ',' + parseInt(p.y) + ']';
}
console.log(textPoints);
console.log(points);

function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x,
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2,
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];
    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;
      // Bounds checks
      if (a1.x == a2.x && y >= minY && y <= maxY) {
        // Vertical line
        intersections.push(point);
      } else if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
};

<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1280 600" id="svg">
  <rect class="vBoxRect" width="1280" height="600" fill="#EFEFEF"></rect>
  <g id="controlPoint">
    <circle cx="640" cy="175" r="5" fill="green" fill-opacity=".5"></circle>    
  </g>
  <g id="qBez">
    <path d="M200,300Q640,175,1080,300" stroke="tomato" fill="none"></path>
  </g>
  <g id="limit">
    <circle id="upper" cx="640" cy="50" r="5" fill="red"></circle>
    <circle id="lower" cx="640" cy="550" r="5" fill="red"></circle>
    <text id="0" x="650" y="60">(640, 50)</text>
    <text id="1" x="650" y="560">(640, 550)</text>
  </g>
  <g id="vert">
    <line x1="640" y1="550" x2="640" y2="50" stroke="blue" stroke-dasharray="500,500"></line>
  </g>
</svg>

//with the same numbers from https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
var lerp = function(a, b, x) { return (a + x * (b - a)); };

// qCurve & line defs - as in https://stackoverflow.com/a/27664883/11156131
//works for the following
var p1 = {x:125,y:200};
var p2 = {x:250,y:225};
var p3 = {x:275,y:100};
var a1 = {x:30,y:125};
var a2 = {x:300,y:175};


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);

// Display the intersection points
var textPoints = 'Intersections: ';
for (var i = 0; i < points.length; i++) {
  var p = points[i];
  textPoints += ' [' + parseInt(p.x) + ',' + parseInt(p.y) + ']';
}
console.log(textPoints);
console.log(points);

function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x,
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2,
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];
    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;
      // Bounds checks
      if (a1.x == a2.x && y >= minY && y <= maxY) {
        // Vertical line
        intersections.push(point);
      } else if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
};

Answer 1

What you're basically doing is finding the roots of a parabola in a rotated/transformed coordinate system. E.g. these two images are the same pair of line and curve, but one is hard to work with, and the other super easy:

         

The reason the second is super easy is because we just need to solve the standard high school quadratic equation B_y(t) = line_y using the quadratic formula.

If we then also move the line down to y=0 (and the curve by the same amount) now we're literally just root finding, i.e solving B_y(t) = 0.

We can do this, because Bezier curves are invariant under transformation and rotation so finding the t values for the roots in our rotates/translated setup is the same as finding the intersections in the original setup.

So... let's just do that:

const { atan2, cos, sin, sqrt } = Math;

function getRoots(pts, [[x1,y1], [x2,y2]]) {
  // Transform and rotate our coordinates as per above,
  // noting that we only care about the y coordinate:
  const angle = atan2(y2-y1, x2-x1);
  const v = pts.map(([x,y]) => (x-x1) * sin(-angle) + (y-y1) * cos(-angle));  
  // And now we're essentially done, we can trivially find our roots: 
  return solveQuadratic(v[0], v[1], v[2])
  // ...as long as those roots are in the Bezier interval [0,1] of course.
  .filter(t => (0 <= t && t <=1));
}

function solveQuadratic(v1,v2,v3) {
  const a = v1 - 2*v2 + v3, b = 2 * (v2 - v1), c = v1;
  // quick check, is "a" zero? if so, the solution is linear. 
  if (a === 0) return (b === 0) ? [] : [-c/b];
  const u = -b/(2*a), v = b**2 - 4*a*c;
  if (v < 0) return []; // If there are no roots, there are no roots. Done.
  if (v === 0) return [u]; // If there's only one root, return that.
  // And if there are two roots we compute the "full" formula
  const w = sqrt(v)/(2*a);
  return [u + w, u - w];
}

// Let's test the coordinates from the question:
const [[x1,y1],[x2,y2],[x3,y3]] = points = [
  [200,300],
  [640,175],
  [1080,300]
];

const line = [
  [650,60],
  [650,550]
];

const roots = getRoots(points, line);
console.log(`roots: ${roots.join(`, `)}`);

const coordForRoot = t => {
  const mt = 1-t;
  return [
    x1*mt**2 + 2*x2*t*mt + x3*t**2,
    y1*mt**2 + 2*y2*t*mt + y3*t**2,
  ];
};

const coordinates = roots.map(t => coordForRoot (t).map(v => v.toFixed(2)));
console.log(`coordinates: ${coordinates.join(`, `)}`);

As you can see, there is surprisingly little code required here, simply because we know we can turn a hard problem into a super easy problem with a change in perspective, and further simplify things by realizing we only care about the y coordinates in solving this problem.

Answer 2

The function works fine unless the line is vertical (b and c become infinity).

A simple workaround can be to give the line an invisible slant like so:

  if (a1.x === a2.x && a1.y !== a2.y) {
    a1.x += 1e-8;
  }

var p1 = {
  x: 200,
  y: 300
};
var p2 = {
  x: 640,
  y: 175
};
var p3 = {
  x: 1080,
  y: 300
};

var a1 = {
  x: +vert.getAttribute('x1'),
  y: +vert.getAttribute('y1')
};
var a2 = {
  x: +vert.getAttribute('x2'),
  y: +vert.getAttribute('y2')
};

var a3 = {
  x: +hor.getAttribute('x1'),
  y: +hor.getAttribute('y1')
};
var a4 = {
  x: +hor.getAttribute('x2'),
  y: +hor.getAttribute('y2')
};


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);
var points2 = calcQLintersects(p1, p2, p3, a3, a4);

// Display the intersection points
renderIntersections(points, svg);
renderIntersections(points2, svg);



function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  //add invisible slant to vertical lines
  if (a1.x === a2.x && a1.y !== a2.y) {
    a1.x += 1e-8;
  }

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;
  //console.log(normal, a, b, c)

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];

    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;

      // Bounds checks
      if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
}


//referred to https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
function lerp(a, b, x) {
  return a + x * (b - a);
};

<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1280 600" id="svg">
  <rect class="vBoxRect" width="1280" height="600" fill="#EFEFEF"></rect>
    <path d="
             M 200 300
             Q 640 175 
             1080 300" stroke="tomato" fill="none"></path>

    <line id="vert" x1="640" y1="550" x2="640" y2="50" stroke="blue" />
    <line id="hor" x1="200" y1="280" x2="1200" y2="280" stroke="purple" />
</svg>

<script>
  function renderIntersections(points, target) {
    for (var i = 0; i < points.length; i++) {
      var pt = points[i];
      let circle = document.createElementNS(
        "http://www.w3.org/2000/svg",
        "circle"
      );
      circle.setAttribute("cx", pt.x);
      circle.setAttribute("cy", pt.y);
      circle.setAttribute("r", "5");
      svg.append(circle);
    }
  }
</script>