Bezier-Kurven. Ein wenig über Kreuzungen und so einfach wie möglich

Haben Sie jemals einen (kontinuierlichen) Pfad zum Überqueren einer Kurve in einer durch Liniensegmente und Bezier-Kurven definierten Ebene gefunden?

Es scheint keine sehr schwierige Aufgabe zu sein: die Kurvensegmente in einem Pfad zu verbinden und sie zu umgehen, "ohne den Stift anzuheben". Eine geschlossene Kurve verläuft in eine Richtung, Zweige bewegen sich vorwärts und rückwärts und beginnen und enden am selben Knoten.

Alles war in Ordnung, bis monströse Pfade unter den Händen der Designer hervorkrochen, wo sich einzelne Kurven schneiden oder nicht genau andocken konnten. Die Erklärung war äußerst einfach - visuell lügen sie alle so, wie sie sollten, und für die Maschine, die diesen Pfad umgeht, sind solche Abweichungen unsichtbar.

Mit der Kenntnis der maximal zulässigen Abweichung begann ich mit der Forschung, deren Ergebnisse ich teilen möchte.

Als erstes habe ich herausgefunden, wie es heute (Oktober 2020) ist, indem ich die Schnittpunkte von Kurven gefunden habe. Entweder habe ich am falschen Ort gesucht oder ich habe gefragt, aber ich konnte keine einfache Lösung finden. Obwohl die Idee mit dem Ergebnis eines Paares von Polynomen ziemlich interessant ist. Viele verschiedene Algorithmen im Zusammenhang mit Bezier - Kurven werden gesammelt hier .

Was mir bei den bekannten Methoden nicht gefallen hat und was ich nicht tun möchte, ist numerisch nach den Wurzeln von Polynomen zu suchen oder sogar quadratische Gleichungen zu lösen. Ich möchte die Kurven wirklich nicht auf Extreme untersuchen. Auf jeden Fall möchte ich Spaltung, Potenzierung und alles vermeiden, was zu undefiniertem Verhalten führen kann.

Also, mit was musst du arbeiten?

• Die Punkte werden nach Typ Pointwie folgt angegeben :

  
  
  

  using Point = std::array<double, 2>;

  
  
  

  Für Pointdie Operatoren Addition, Subtraktion, Multiplikation mit einem Skalar, Skalarmultiplikation sind definiert.

  
  
  

• Der Wert der Rzulässigen Punktabweichung wird eingestellt.

  
  
  

• Kurven werden durch Anordnungen von Kontrollpunkten (Kontrollpunkten) definiert std::vector<Point>.

  
  
  

• Fast übereinstimmende Kurven sollten markiert und wenn möglich gelöscht werden, beispielsweise wenn es sich um ein vergessenes Duplikat handelt (Kopieren und Einfügen ist böse).

  
  
  

, , . ( ):

Point point(const std::vector<Point> &curve, double t, int n, int i)
{
    return n == 0 ? curve[i] : (point(curve, t, n - 1, i - 1) * (1 - t) + point(curve, t, n - 1, i) * t);
}

— , :

Point point(const std::vector<Point> &curve, double t)
{
    return point(curve, t, curve.size() - 1, curve.size() - 1);
}

, curve — : , .

— - , R:

template <>
struct std::less<Point>
{
    bool operator()(const Point &a, const Point &b, const double edge = R) const
    {
        for (auto i = a.size(); i-- > 0;) {
            if (a[i] + edge < b[i])
                return true;
            if (a[i] > b[i] + edge)
                return true;
        }
        return false;
    }
};

. , , , . — :

struct Rect
{
    Point topLeft, bottomRight;
    Rect(const Point &point);
    Rect(const std::vector<Point> &curve);
    bool isCross(const Rect &rect, const double edge) const
    {
        for (auto i = topLeft.size(); i-- > 0;) {
            if (topLeft[i] > rect.bottomRight[i] + edge
                || bottomRight[i] + edge < rect.topLeft[i])
                return false;
        }
        return true;
    }
};

void find(const std::vector<Point> &curveA, const std::vector<Point> &curveB,
          double tA, double tB, double dt)
{

    if (m_isSimilarCurve)
        return;

    Rect aRect(curveA);
    Rect bRect(curveB);
    if (!aRect.isCross(bRect, R))
        return;

    if (isNear(aRect.tl, aRect.br, R / 2) && isNear(bRect.tl, bRect.br, R / 2)) {
        // 3.1        
        addBest(curveA.front(), curveA.back(), curveB.front(), curveB.back(), tA, tB, dt);
        m_isSimilarCurve = (m_result.size() > curveA.size() * curveB.size());
        return;
    }

    const auto curveALeft = subCurve(curveA, 0, 0.5);
    const auto curveARight = subCurve(curveA, 0.5, 1.0);
    const auto curveBLeft = subCurve(curveB, 0, 0.5);
    const auto curveBRight = subCurve(curveB, 0.5, 1.0);

    const auto dtHalf = dt / 2;
    find(curveALeft, curveBLeft, tA, tB, dtHalf);
    find(curveALeft, curveBRight, tA, tB + dtHalf, dtHalf);
    find(curveARight, curveBLeft, tA + dtHalf, tB, dtHalf);
    find(curveARight, curveBRight, tA + dtHalf, tB + dtHalf, dtHalf);

}

- : , t t1 t2?

t = (t2 - t1) t' + t1 . t = t1, t = t2. , ( ) . : k t2 t1, k:

Point point(const std::vector<Point> &curve, double t1, int n, int i, double t2, int k)
{
    return n > k ? (point(curve, t1, n - 1, i - 1, t2, k) * (1 - t2) +
                    point(curve, t1, n - 1, i, t2, k) * t2)
                 : point(curve, t1, n, i);
}

, :

std::vector<Point> subCurve(const std::vector<Point> &curve, double t1, double t2)
{
    std::vector<Point> result(curve.size());
    for (auto k = result.size(); k-- > 0;) {
        result[k] = point(curve, t1, curve.size() - 1, curve.size() - 1, t2, curve.size() - 1 - k);
    }
    return result;
}

, , .

.

1. t1und t2kann beliebig sein:
   
   
   • subCurve(curve, 1, 0)gibt eine Kurve, die sich vom Endpunkt curvezum Startpunkt "bewegt" ,
   • subCurve(curve, 1, 2)extrapoliert curveüber den letzten Ankerpunkt hinaus.
2. Einige Methodenimplementierungen werden absichtlich weggelassen, da sie nichts besonders Interessantes enthalten.
3. Die Funktion eignet sich point(curve, t)nicht zur Berechnung vieler Punkte auf einer Kurve (z. B. zur Rasterung), dafür ist die Berechnung mit einer Dreiecksmatrix besser.