Nächster Punkt auf einer kubischen Bezier-Kurve?

Je nach Toleranzen. Brute-force-und akzeptieren Fehler. Dieser Algorithmus könnte falsch sein, für einige seltene Fälle. Aber, die Mehrheit von Ihnen findet es einen Punkt sehr nahe an der richtigen Antwort, und die Ergebnisse werden sich verbessern, je höher der Scheiben. Es versucht jeder Punkt entlang der Kurve in regelmäßigen Abständen und gibt das beste es gefunden.

public double getClosestPointToCubicBezier(double fx, double fy, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3)  {
    double tick = 1d /(double) slices;
    double x;
    double y;
    double t;
    double best = 0;
    double bestDistance = Double.POSITIVE_INFINITY;
    double currentDistance;
    for (int i = 0; i <= slices; i++) {
        t = i * tick;
        //B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
        x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
        y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;

        currentDistance = Point.distanceSq(x,y,fx,fy);
        if (currentDistance < bestDistance) {
            bestDistance = currentDistance;
            best = t;
        }
    }
    return best;
}

Können Sie viel besser und schneller, indem Sie einfach das finden der nächstgelegenen Punkt und recursing um diesen Punkt.

public double getClosestPointToCubicBezier(double fx, double fy, int slices, int iterations, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
    return getClosestPointToCubicBezier(iterations, fx, fy, 0, 1d, slices, x0, y0, x1, y1, x2, y2, x3, y3);
}

private double getClosestPointToCubicBezier(int iterations, double fx, double fy, double start, double end, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
    if (iterations <= 0) return (start + end) /2;
    double tick = (end - start) /(double) slices;
    double x, y, dx, dy;
    double best = 0;
    double bestDistance = Double.POSITIVE_INFINITY;
    double currentDistance;
    double t = start;
    while (t <= end) {
        //B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
        x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
        y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;


        dx = x - fx;
        dy = y - fy;
        dx *= dx;
        dy *= dy;
        currentDistance = dx + dy;
        if (currentDistance < bestDistance) {
            bestDistance = currentDistance;
            best = t;
        }
        t += tick;
    }
    return getClosestPointToCubicBezier(iterations - 1, fx, fy, Math.max(best - tick, 0d), Math.min(best + tick, 1d), slices, x0, y0, x1, y1, x2, y2, x3, y3);
}

In beiden Fällen können Sie die quad nur als leicht:

x = (1 - t) * (1 - t) * x0 + 2 * (1 - t) * t * x1 + t * t * x2; //quad.
y = (1 - t) * (1 - t) * y0 + 2 * (1 - t) * t * y1 + t * t * y2; //quad.

Durch den Wechsel aus der Gleichung gibt.

Während die akzeptierte Antwort richtig ist, und Sie wirklich herausfinden können, die Wurzeln und vergleichen Sie das Zeug. Wenn Sie wirklich brauchen nur zu finden der nächstgelegenen Punkt auf der Kurve, dies wird es tun.

In Bezug auf Ben in den Kommentaren. Sie können nicht kurzer hand die Formel, in die viele Hunderte von Steuerelement-Punkt-Bereich, wie ich für kubische und quad Formen. Denn die Menge verlangt von jeder neuen Zugabe von einer Bézier-Kurve bedeutet, dass Sie bauen eine Pythagoreische Pyramiden für Sie, und wir sind im Grunde der Umgang mit noch mehr und noch massig zahlen. Für die quad gehen Sie 1, 2, 1, für kubische Sie gehen 1, 3, 3, 1. Sie landen, die Gebäude größer und größer Pyramiden, und am Ende brechen Sie Sie unten mit Casteljau-Algorithmus, (ich schrieb dies für Feste Geschwindigkeit):

/**
 * Performs deCasteljau's algorithm for a bezier curve defined by the given control points.
 *
 * A cubic for example requires four points. So it should get at least an array of 8 values
 *
 * @param controlpoints (x,y) coord list of the Bezier curve.
 * @param returnArray Array to store the solved points. (can be null)
 * @param t Amount through the curve we are looking at.
 * @return returnArray
 */
public static float[] deCasteljau(float[] controlpoints, float[] returnArray, float t) {
    int m = controlpoints.length;
    int sizeRequired = (m/2) * ((m/2) + 1);
    if (returnArray == null) returnArray = new float[sizeRequired];
    if (sizeRequired > returnArray.length) returnArray = Arrays.copyOf(controlpoints, sizeRequired); //insure capacity
    else System.arraycopy(controlpoints,0,returnArray,0,controlpoints.length);
    int index = m; //start after the control points.
    int skip = m-2; //skip if first compare is the last control point.
    for (int i = 0, s = returnArray.length - 2; i < s; i+=2) {
        if (i == skip) {
            m = m - 2;
            skip += m;
            continue;
        }
        returnArray[index++] = (t * (returnArray[i + 2] - returnArray[i])) + returnArray[i];
        returnArray[index++] = (t * (returnArray[i + 3] - returnArray[i + 1])) + returnArray[i + 1];
    }
    return returnArray;
}

Im Grunde muss man den Algorithmus verwenden direkt, nicht nur für die Berechnung der x,y, die auftreten, auf der Kurve selbst, aber Sie müssen auch für die Durchführung der tatsächlichen und ordnungsgemäßen Bezier-subdivision Algorithmus (es gibt andere, aber das ist, was ich empfehlen würde), um zu berechnen, nicht nur eine Annäherung sein, wie ich durch die Aufteilung in Linien-Segmenten, sondern von den tatsächlichen Kurven. Oder eher die polygon-Rumpf ist sicher enthalten die Kurve.

Tun Sie dies, indem Sie den oben beschriebenen Algorithmus zur Unterteilung der Kurven auf der gegebenen t. Also ist T=0.5, schneiden Sie die Kurven in der Hälfte (Hinweis 0.2 geschnitten würde es 20% 80% über der Kurve). Dann index der verschiedenen Punkte an der Seite der Pyramide, und die andere Seite der Pyramide, gebaut von der Basis. So zum Beispiel im kubischen:

   9
  7 8
 4 5 6
0 1 2 3

Sie füttern würde der Algorithmus 0 1 2 3 control points, dann würde index die beiden perfekt unterteilt Kurven bei 0, 4, 7, 9 und 9, 8, 6, 3. Machen Sie sich spezielle Notiz zu sehen, dass diese Kurven beginnen und enden am gleichen Punkt. und der Letzte index 9, das ist der Punkt auf der Kurve ist als die anderen neuen Ankerpunkt. Angesichts dieser Sie können perfekt zu unterteilen, eine bezier-Kurve.

Dann finden Sie den nächsten Punkt, den Sie wollen würde, um zu halten die Unterteilung der Kurve in verschiedenen teilen der Feststellung, dass es der Fall ist, dass die gesamte Kurve eine bezier-Kurve enthalten ist, die innerhalb der Hülle der Kontrollpunkte. Das ist zu sagen, wenn wir die Punkte 0, 1, 2, 3 in einen geschlossenen Pfad verbinden 0,3, die Kurve muss fallen vollständig innerhalb des Polygons Rumpf. Also, was wir tun zu definieren, die unseren gegebenen Punkt P, dann fahren wir weiter zu unterteilen Kurven bis zu dem Zeitpunkt, als wir wissen, dass die entferntesten Punkt einer Kurve ist näher als dem nächstgelegenen Punkt der anderen Kurve. Wir vergleichen einfach dieses Punktes P zu allen Kontroll-und Anker-Punkte der Kurven. Und zu verwerfen jede Kurve aus unserer aktiven Liste, deren nächste Stelle (ob Anker oder Kontrolle) weiter entfernt ist als der am weitesten entfernte Punkt der anderen Kurve. Dann unterteilen wir alle aktiven Kurven und dies wieder tun. Schließlich haben wir sehr unterteilt Kurven verwerfen, etwa die Hälfte jeder Schritt (Bedeutung sollte es werden O(n log n)), bis unsere Fehler ist im Grunde vernachlässigbar. An dieser Stelle nennen wir unsere aktive Kurven der nächste Punkt zu diesem Punkt (es könnte mehr als eine), und beachten Sie, dass der Fehler in der hoch unterteilt bisschen von Kurve ist im Grunde gleich zu einem Punkt. Oder einfach entscheiden, die Frage mit den Worten, welche der beiden Anker-Punkt am nächsten liegt ist der nächste Punkt zu unserem Ausgangspunkt P. Und wir wissen, dass der Fehler zu einem ganz bestimmten Grad.

Diesem, obwohl, erfordert, dass wir tatsächlich eine stabile Lösung und eine sicherlich richtige Algorithmus und richtig finden, den kleinen Teil der Kurve, dass wird sicher sein, den nächsten Punkt zu unserem Ausgangspunkt. Und es sollte relativ schnell sein noch.

InformationsquelleAutor der Antwort Tatarize