add a proto.getTforPoint(point)

[Pomax]

If a point is on-or-near-enough the curve, return all t values that yield the specified point.

This will allow things like:

getDistanceforPoint(p):
  ts = getTforPoint(p)
  ds = (ts: (t) => split(t).length)
  yield ds

[NaridaL]

Hey, I implemented this function for 3d non-intersecting cubic curves. Posting it here in case you find it useful: (NLA.equals and NLA.isZero are fuzzy comparison functions, solveCubicRoot2 is a modified version of your utils.roots which works when a == 0 and b == 0)

        /**
         * Returns curve parameter t for point p on curve.
         * @param p
         * @returns {*}
         */
        pointLambda: function (p) {
            var {p0, p1, p2, p3} = this
            // calculate cubic equation coefficients
            // a t³ + b t² + c t + d = 0
            // multiplying out the cubic Bézier curve equation gives:
            // a = -p0 + 3 p1 - 3 p2 + p3
            // b = 3 p0 - 6 p1 + 3 p2
            // c = -3 p0 + 3 p1
            // d = p0 - p
            var a = p1.minus(p2).times(3).minus(p0).plus(p3)
            var b = p0.plus(p2).times(3).minus(p1.times(6))
            var c = p1.minus(p0).times(3)
            var d = p0.minus(p)
            var results = null, newResults

            // assume passed point is on curve and that curve does not self-intersect,
            // i.e. there is exactly one correct result for t
            // try to find a single result in the x-dimension, if multiple are found,
            // filter them by checking the other dimesions
            if (NLA.isZero(a.x) && NLA.isZero(b.x) && NLA.isZero(c.x)) {
                // ax == bx == cx == 0 => x(t) = dx
                // x value is constant
                // if x == 0 for all t, this does not limit the result, otherwise, there is no result, i.e
                // the passed point is not on the curve
                assert(NLA.isZero(d.x))
            } else {
                newResults = solveCubicReal2(a.x, b.x, c.x, d.x)
                console.log('xres', a.x, b.x, c.x, d.x, newResults)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }

            if (NLA.isZero(a.y) && NLA.isZero(b.y) && NLA.isZero(c.y)) {
                assert(NLA.isZero(d.y))
            } else {
                newResults = solveCubicReal2(a.y, b.y, c.y, d.y)
                console.log('yres', a.y, b.y, c.y, d.y, newResults,p.ss)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }

            if (NLA.isZero(a.z) && NLA.isZero(b.z) && NLA.isZero(c.z)) {
                assert(NLA.isZero(d.z))
            } else {
                newResults = solveCubicReal2(a.z, b.z, c.z, d.z)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }
            assert(false, 'found no t; point '+p.ss+' is not on curve')
        }

[Pomax]

nice - does Cardano's algorithm break down on a=0 and b=0 though?

[NaridaL]

Well assuming the form a t³ + b t² + c t + d = 0, the first step is to normalize it to t³ + b/a t² + c/a t + d/a = 0 which obviously doesn't work for a == 0, so I pass it to a quadratic formula implementation, which also assumes a normalized form x² + c/b x + d/b = 0.

At that points it's just a line, solving is easy :-D

[Pomax]

ah!

[danmarshall]

+1 on this feature. @NaridaL , can you also provide your implementation of solveCubicRoot2 ?

[NaridaL]

@danmarshall As I said, it basically the same as @Pomax 's version, with added parameter checking. For what it's worth:

function solveCubicReal2(a, b, c, d) {
    if (NLA.isZero(a)) {
        if (NLA.isZero(b)) {
            return [-d/c]
        } else {
            return pqEquation(c / b, d / b)
        }
    }
    var div = a
    a = b/div
    b = c/div
    c = d/div
    var p = (3*b - a*a)/3,
        p3 = p/3,
        q = (2*a*a*a - 9*a*b + 27*c)/27,
        q2 = q/2,
        discriminant = q2*q2 + p3*p3*p3,
    u1,v1,x1,x2,x3
    // 18abcd - 4b³d + b²c² - 4ac³ - 27a²d²
    if (discriminant < -NLA.PRECISION) {
        var mp3 = -p/3,
            mp33 = mp3*mp3*mp3,
            r = Math.sqrt( mp33 ),
            t = -q/(2*r),
            cosphi = t<-1 ? -1 : t>1 ? 1 : t,
            phi = Math.acos(cosphi),
            crtr = Math.cbrt(r),
            t1 = 2*crtr
        x1 = t1 * Math.cos(phi/3) - a/3
        x2 = t1 * Math.cos((phi+2*Math.PI)/3) - a/3
        x3 = t1 * Math.cos((phi+4*Math.PI)/3) - a/3
        return [x1, x2, x3]
    } else if(discriminant <= NLA.PRECISION) {
        u1 = q2 < 0 ? Math.cbrt(-q2) : -Math.cbrt(q2)
        x1 = 2*u1-a/3
        x2 = -u1 - a/3
        return [x1,x2]
    } else {
        var sd = Math.sqrt(discriminant)
        u1 = Math.cbrt(-q2+sd)
        v1 = Math.cbrt(q2+sd)
        return [u1-v1-a/3]
    }
}

/*
 solves x² + px + q = 0
 */
function pqEquation(p, q) {
    // 4 times the discriminant:
    var discriminant4 = p * p / 4 - q
    if (discriminant4 < -NLA.PRECISION) {
        return []
    } else if (discriminant4 <= NLA.PRECISION) {
        return [-p/2]
    } else {
        var root = Math.sqrt(discriminant4)
        return [-p/2 - root, -p/2 + root]
    }
}

[dashng]

It is not clear enough. how should I involved these code to my project.

Bezier should be extended to support this feature?

[Pomax]

you shouldn't, this code should get worked into bezierjs itself.