CODEWITHSUNDEEP
javascripthtml5-canvaslineintersectionbezier
Haussperling
Haussperling

Reputation: 11

Is HTML Canvas quadraticCurveTo() not exact?

Edit: I just changed my Control Point to the Intersection. That's why it couldn't fit anymore.

I know it's a very presumptuous. But I am working on a Web-Application and I need to calculate the intersection with a quadratic Beziere-Curve and a Line.

Because W, V, A, B, and C are points, I could make two equation. I rearranged the first equation to seperate s to solve the equation. I'm pretty sure i did it correctly, but my intersection was not on the line. So i was wondering and made my own quadratic-Beziercurve by the correct formular and my intersection hits this curve. Now I am wondering what did I wrong?

That is my function:

intersectsWithLineAtT(lineStartPoint, lineEndPoint)
{
    let result = []
    let A = this.startPoint, B = this.controlPoint, C = this.endPoint, V = lineStartPoint, W = lineEndPoint
    if (!Common.isLineIntersectingLine(A, B, V, W)
        && !Common.isLineIntersectingLine(B, C, V, W)
        && !Common.isLineIntersectingLine(A, C, V, W))
        return null

    let alpha = Point.add(Point.subtract(A, Point.multiply(B, 2)), C)
    let beta = Point.add(Point.multiply(A, -2), Point.multiply(B, 2))
    let gamma = A
    let delta = V
    let epsilon = Point.subtract(W, V)

    let a = alpha.x * (epsilon.y / epsilon.x) - alpha.y
    let b = beta.x * (epsilon.y / epsilon.x) - beta.y
    let c = (gamma.x - delta.x) * (epsilon.y / epsilon.x) - gamma.y + delta.y

    let underSquareRoot = b * b - 4 * a * c

    if (Common.compareFloats(0, underSquareRoot))
        result.push(-b / 2 * a)
    else if (underSquareRoot > 0)
    {
        result.push((-b + Math.sqrt(underSquareRoot)) / (2 * a))
        result.push((-b - Math.sqrt(underSquareRoot)) / (2 * a))
    }

    result = result.filter((t) =>
    {
        return (t >= 0 && t <= 1)
    })

    return result.length > 0 ? result : null
}

I hope someone can help me.

Lena

Upvotes: 1

Views: 194

Answers (1)

Mike &#39;Pomax&#39; Kamermans
Mike &#39;Pomax&#39; Kamermans

Reputation: 53725

The curve/line intersection problem is the same as the root finding problem, after we rotate all coordinates such that the line ends up on top of the x-axis:

enter image description here

which involves a quick trick involving atan2:

const d = W.minus(V);
const angle = -atan2(d.y, d.x);
const rotated = [A,B,C].map(p => p.minus(V).rotate(angle));

Assuming you're working with point classes that understand vector operations. If not, easy enough to do with standard {x, y} objects:

const rotated = [A,B,C].map(p => {
  p.x -= V.x;
  p.y -= V.y;
  return {
    x: p.x * cos(a) - p.y * sin(a),
    y: p.x * sin(a) + p.y * cos(a)
  };
});

Then all we need to find out is which t values yield y=0, which is (as you also used) just applying the quadratic formula. And we don't need to bother with collapsing dimensions: we've reduced the problem to finding solutions in just the y dimension, so taking

const a = rotated[0].y;
const b = rotated[1].y;
const c = rotated[2].y;

and combining that with the fact that we know that Py = t²(a-b+c)+t(-2a+2b)+a we just work out that t = -b/2a +/- sqrt(b² - 4ac))/2a with the usual checks for negative, zero, and positive discriminant, as well as checking for division by zero.

This gives us with zero or more t value(s) for the y=0 intercept in our rotated case, and for the intersection between our curve and line in the unrotated case. No additional calculations required. Aside from "evaluating B(t) to get the actual (x,y) cooordinates", of course.

Upvotes: 1

Related Questions