Curvas de Bezier. Un poco sobre intersecciones y lo más simple posible.

¿Alguna vez se ha encontrado con la construcción de una ruta (continua) para atravesar una curva en un plano definido por segmentos de línea y curvas de Bézier?

No parece una tarea muy difícil: unir los segmentos de las curvas en un solo camino y rodearlo "sin levantar la pluma". Una curva cerrada atraviesa una dirección, las ramas atraviesan hacia adelante y hacia atrás, y comienzan y terminan en el mismo nodo.

Todo estaba bien hasta que los caminos monstruosos comenzaron a surgir de debajo de las manos de los diseñadores, donde las curvas individuales podían cruzarse o no acoplarse exactamente. La explicación fue extremadamente simple: visualmente, todos mienten como deberían, y para la máquina que evitará este camino, tales desviaciones son invisibles.

Armado con el conocimiento de la desviación máxima permitida, comencé la investigación, cuyos resultados quiero compartir.

Lo primero que hice fue averiguar cómo están las cosas hoy (octubre de 2020) encontrando los puntos de intersección de las curvas. O estaba buscando en el lugar equivocado, o tal vez estaba preguntando, pero no pude encontrar una solución simple. Aunque, la idea con la resultante de un par de polinomios es bastante interesante. Aquí se recopilan muchos algoritmos diferentes relacionados con las curvas de Bezier .

Lo que no me gustó de los métodos conocidos y lo que no quiero hacer es buscar numéricamente las raíces de polinomios, o incluso resolver ecuaciones cuadráticas. Realmente no quiero explorar las curvas para los extremos. De todos modos, me gustaría evitar la división, la exponenciación y todo lo que pueda llevar a un comportamiento indefinido.

Entonces, ¿con qué tienes que trabajar?

• Los puntos se especifican por tipo Point, así:

  
  
  

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

  
  
  

  Para Pointlos operadores de suma, resta, multiplicación por escalar, se definen multiplicaciones escalares.

  
  
  

• Se establece el valor de la Rdesviación admisible de puntos.

  
  
  

• Las curvas se definen mediante matrices de puntos de control (control) std::vector<Point>.

  
  
  

• Las curvas casi coincidentes deben marcarse y, si es posible, eliminarse, por ejemplo, si es un duplicado olvidado (copiar y pegar es malo).

  
  
  

, , . ( ):

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. t1y t2puede ser cualquiera:
   
   
   • subCurve(curve, 1, 0)dará una curva que "se mueve" desde el punto final al punto curvede inicio,
   • subCurve(curve, 1, 2)extrapola curvemás allá del último punto de anclaje.
2. Algunas implementaciones de métodos se omiten intencionalmente porque no contienen nada particularmente interesante.
3. La función point(curve, t)no es adecuada para calcular muchos puntos en una curva (por ejemplo, para la rasterización); para esto, el cálculo usando una matriz triangular es más adecuado.