convertir curva de bezier a cadena poligonal?

Question

Quiero dividir una curva bezier en una cadena poligonal con n líneas rectas. El número de líneas depende de un ángulo máximo permitido entre 2 líneas de conexión. Estoy buscando un algoritmo para encontrar la solución más óptima (es decir, para reducir al máximo la cantidad de líneas rectas).

Sé cómo dividir una curva bezier utilizando polinomios de Casteljau o Bernstein. Traté de dividir el bezier para calcular a medias el ángulo entre las líneas rectas, y dividir de nuevo si el ángulo entre las líneas de conexión se encuentra dentro de un cierto rango de umbral, pero puedo encontrar atajos.

¿Existe un algoritmo conocido o pseudo código disponible para hacer esta conversión?

Answer 1

Use el algoritmo de Casteljau recursivamente hasta que los puntos de control sean aproximadamente colineales. Ver por ejemplo http://www.antigrain.com/research/adaptive_bezier/index.html.

Answer 2

Un ejemplo visual en my website -> DXF -> polybezier. es básicamente una división recursiva con casteljau.

Bezier2Poly.prototype.convert = function(array,init) { 
    if (init) { 
    this.vertices = []; 
    } 
    if (!init && (Math.abs(this.controlPointsDiff(array[0], array[2])) < this.threshold 
     || Math.abs(this.controlPointsDiff({x:array[2].x-array[1].x, y:array[2]-array[1].y}, array[2])) < this.threshold)) { 
     this.vertices.push(array[2]); 
    } else { 
     var split = this.splitBezier(array); 
     this.convert(split.b1); 
     this.convert(split.b2); 
    } 
    return this.vertices; 
} 

Y el juicio por: el cálculo del ángulo entre los puntos de control y la línea a través del punto final.

Bezier2Poly.prototype.controlPointsDiff = function (vector1, vector2) { 
    var angleCp1 = Math.atan2(vector1.y, vector1.x); 
    var angleCp2 = Math.atan2(vector2.y, vector2.x); 
    return angleCp1 - angleCp2; 
} 

Answer 3

hay algunas alternativas para RSA aplanamiento que son reportados a ser más rápido:

RSA vs PAA: http://www.cis.usouthal.edu/~hain/general/Theses/Ahmad_thesis.pdf

RSA vs CAA vs PAA: http://www.cis.usouthal.edu/~hain/general/Theses/Racherla_thesis.pdf

RSA = recursiva Algoritmo de subdivisión PAA = Algoritmo de aproximación parabólica CAA = Algoritmo de aproximación circular

Según Rachela, CAA es más lento que el PAA por un factor de 1.5-2. CAA es tan lento como RSA, pero logra mejor planitud requerida en curvas de desplazamiento.

Parece que PAA es la mejor opción para la curva real y CAA es mejor para los desplazamientos de la curva (cuando se acarician las curvas).

He probado PAA de ambas tesis, pero fallan en algunos casos. El PAA de Ahmad falla en casos colineales (todos los puntos en la misma línea) y el PAA de Rachela falla en casos colineales y en casos donde ambos puntos de control son iguales. Con algunas correcciones, es posible hacer que funcionen como se esperaba.

Answer 4

lo resuelvo con qt para cualquier ruta svg incluyendo curva de bezier, encontré en el módulo svg una función estática en qsvghandler.cpp que parsePathDataFast de su ruta svg a QPainterPath y la guinda del pastel !! QPainterPath tiene tres funciones nativas para convertir tu ruta en un polígono (el más grande en FillPolygon y los otros que se dividen en una lista de polígonos para los PolígonosSubpath o paraFillPolygons) junto con elementos interesantes como cuadro delimitador, intersección, traducción ... listo para usar con Boost: : Geometría ahora, ¡no tan mal!

la cabecera parsepathdatafast.h

#ifndef PARSEPATHDATAFAST_H 
#define PARSEPATHDATAFAST_H 

#include <QPainterPath> 
#include <QString> 

bool parsePathDataFast(const QStringRef &dataStr, QPainterPath &path); 

#endif // PARSEPATHDATAFAST_H 

la parsepathdatafast código.CPP

#include <QtCore/qmath.h> 
#include <QtMath> 
#include <QChar> 
#include <QByteArray> 
#include <QMatrix> 


#include <parsepathdatafast.h> 

Q_CORE_EXPORT double qstrtod(const char *s00, char const **se, bool *ok); 

// '0' is 0x30 and '9' is 0x39 
static inline bool isDigit(ushort ch) 
{ 
    static quint16 magic = 0x3ff; 
    return ((ch >> 4) == 3) && (magic >> (ch & 15)); 
} 

static qreal toDouble(const QChar *&str) 
{ 
    const int maxLen = 255;//technically doubles can go til 308+ but whatever 
    char temp[maxLen+1]; 
    int pos = 0; 

    if (*str == QLatin1Char('-')) { 
     temp[pos++] = '-'; 
     ++str; 
    } else if (*str == QLatin1Char('+')) { 
     ++str; 
    } 
    while (isDigit(str->unicode()) && pos < maxLen) { 
     temp[pos++] = str->toLatin1(); 
     ++str; 
    } 
    if (*str == QLatin1Char('.') && pos < maxLen) { 
     temp[pos++] = '.'; 
     ++str; 
    } 
    while (isDigit(str->unicode()) && pos < maxLen) { 
     temp[pos++] = str->toLatin1(); 
     ++str; 
    } 
    bool exponent = false; 
    if ((*str == QLatin1Char('e') || *str == QLatin1Char('E')) && pos < maxLen) { 
     exponent = true; 
     temp[pos++] = 'e'; 
     ++str; 
     if ((*str == QLatin1Char('-') || *str == QLatin1Char('+')) && pos < maxLen) { 
      temp[pos++] = str->toLatin1(); 
      ++str; 
     } 
     while (isDigit(str->unicode()) && pos < maxLen) { 
      temp[pos++] = str->toLatin1(); 
      ++str; 
     } 
    } 

    temp[pos] = '\0'; 

    qreal val; 
    if (!exponent && pos < 10) { 
     int ival = 0; 
     const char *t = temp; 
     bool neg = false; 
     if(*t == '-') { 
      neg = true; 
      ++t; 
     } 
     while(*t && *t != '.') { 
      ival *= 10; 
      ival += (*t) - '0'; 
      ++t; 
     } 
     if(*t == '.') { 
      ++t; 
      int div = 1; 
      while(*t) { 
       ival *= 10; 
       ival += (*t) - '0'; 
       div *= 10; 
       ++t; 
      } 
      val = ((qreal)ival)/((qreal)div); 
     } else { 
      val = ival; 
     } 
     if (neg) 
      val = -val; 
    } else { 
     bool ok = false; 
     val = qstrtod(temp, 0, &ok); 
    } 
    return val; 

} 

static inline void parseNumbersArray(const QChar *&str, QVarLengthArray<qreal, 8> &points) 
{ 
    while (str->isSpace()) 
     ++str; 
    while (isDigit(str->unicode()) || 
      *str == QLatin1Char('-') || *str == QLatin1Char('+') || 
      *str == QLatin1Char('.')) { 

     points.append(toDouble(str)); 

     while (str->isSpace()) 
      ++str; 
     if (*str == QLatin1Char(',')) 
      ++str; 

     //eat the rest of space 
     while (str->isSpace()) 
      ++str; 
    } 
} 

/** 
static QVector<qreal> parsePercentageList(const QChar *&str) 
{ 
    QVector<qreal> points; 
    if (!str) 
     return points; 

    while (str->isSpace()) 
     ++str; 
    while ((*str >= QLatin1Char('0') && *str <= QLatin1Char('9')) || 
      *str == QLatin1Char('-') || *str == QLatin1Char('+') || 
      *str == QLatin1Char('.')) { 

     points.append(toDouble(str)); 

     while (str->isSpace()) 
      ++str; 
     if (*str == QLatin1Char('%')) 
      ++str; 
     while (str->isSpace()) 
      ++str; 
     if (*str == QLatin1Char(',')) 
      ++str; 

     //eat the rest of space 
     while (str->isSpace()) 
      ++str; 
    } 

    return points; 
} 
**/ 

static void pathArcSegment(QPainterPath &path, 
          qreal xc, qreal yc, 
          qreal th0, qreal th1, 
          qreal rx, qreal ry, qreal xAxisRotation) 
{ 
    qreal sinTh, cosTh; 
    qreal a00, a01, a10, a11; 
    qreal x1, y1, x2, y2, x3, y3; 
    qreal t; 
    qreal thHalf; 

    sinTh = qSin(xAxisRotation * (M_PI/180.0)); 
    cosTh = qCos(xAxisRotation * (M_PI/180.0)); 

    a00 = cosTh * rx; 
    a01 = -sinTh * ry; 
    a10 = sinTh * rx; 
    a11 = cosTh * ry; 

    thHalf = 0.5 * (th1 - th0); 
    t = (8.0/3.0) * qSin(thHalf * 0.5) * qSin(thHalf * 0.5)/qSin(thHalf); 
    x1 = xc + qCos(th0) - t * qSin(th0); 
    y1 = yc + qSin(th0) + t * qCos(th0); 
    x3 = xc + qCos(th1); 
    y3 = yc + qSin(th1); 
    x2 = x3 + t * qSin(th1); 
    y2 = y3 - t * qCos(th1); 

    path.cubicTo(a00 * x1 + a01 * y1, a10 * x1 + a11 * y1, 
       a00 * x2 + a01 * y2, a10 * x2 + a11 * y2, 
       a00 * x3 + a01 * y3, a10 * x3 + a11 * y3); 
} 


// the arc handling code underneath is from XSVG (BSD license) 
/* 
* Copyright 2002 USC/Information Sciences Institute 
* 
* Permission to use, copy, modify, distribute, and sell this software 
* and its documentation for any purpose is hereby granted without 
* fee, provided that the above copyright notice appear in all copies 
* and that both that copyright notice and this permission notice 
* appear in supporting documentation, and that the name of 
* Information Sciences Institute not be used in advertising or 
* publicity pertaining to distribution of the software without 
* specific, written prior permission. Information Sciences Institute 
* makes no representations about the suitability of this software for 
* any purpose. It is provided "as is" without express or implied 
* warranty. 
* 
* INFORMATION SCIENCES INSTITUTE DISCLAIMS ALL WARRANTIES WITH REGARD 
* TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF 
* MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL INFORMATION SCIENCES 
* INSTITUTE BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL 
* DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA 
* OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 
* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
* PERFORMANCE OF THIS SOFTWARE. 
* 
*/ 
static void pathArc(QPainterPath &path, 
        qreal    rx, 
        qreal    ry, 
        qreal    x_axis_rotation, 
        int   large_arc_flag, 
        int   sweep_flag, 
        qreal    x, 
        qreal    y, 
        qreal curx, qreal cury) 
{ 
    qreal sin_th, cos_th; 
    qreal a00, a01, a10, a11; 
    qreal x0, y0, x1, y1, xc, yc; 
    qreal d, sfactor, sfactor_sq; 
    qreal th0, th1, th_arc; 
    int i, n_segs; 
    qreal dx, dy, dx1, dy1, Pr1, Pr2, Px, Py, check; 

    rx = qAbs(rx); 
    ry = qAbs(ry); 

    sin_th = qSin(x_axis_rotation * (M_PI/180.0)); 
    cos_th = qCos(x_axis_rotation * (M_PI/180.0)); 

    dx = (curx - x)/2.0; 
    dy = (cury - y)/2.0; 
    dx1 = cos_th * dx + sin_th * dy; 
    dy1 = -sin_th * dx + cos_th * dy; 
    Pr1 = rx * rx; 
    Pr2 = ry * ry; 
    Px = dx1 * dx1; 
    Py = dy1 * dy1; 
    /* Spec : check if radii are large enough */ 
    check = Px/Pr1 + Py/Pr2; 
    if (check > 1) { 
     rx = rx * qSqrt(check); 
     ry = ry * qSqrt(check); 
    } 

    a00 = cos_th/rx; 
    a01 = sin_th/rx; 
    a10 = -sin_th/ry; 
    a11 = cos_th/ry; 
    x0 = a00 * curx + a01 * cury; 
    y0 = a10 * curx + a11 * cury; 
    x1 = a00 * x + a01 * y; 
    y1 = a10 * x + a11 * y; 
    /* (x0, y0) is current point in transformed coordinate space. 
     (x1, y1) is new point in transformed coordinate space. 

     The arc fits a unit-radius circle in this space. 
    */ 
    d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0); 
    sfactor_sq = 1.0/d - 0.25; 
    if (sfactor_sq < 0) sfactor_sq = 0; 
    sfactor = qSqrt(sfactor_sq); 
    if (sweep_flag == large_arc_flag) sfactor = -sfactor; 
    xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0); 
    yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0); 
    /* (xc, yc) is center of the circle. */ 

    th0 = qAtan2(y0 - yc, x0 - xc); 
    th1 = qAtan2(y1 - yc, x1 - xc); 

    th_arc = th1 - th0; 
    if (th_arc < 0 && sweep_flag) 
     th_arc += 2 * M_PI; 
    else if (th_arc > 0 && !sweep_flag) 
     th_arc -= 2 * M_PI; 

    n_segs = qCeil(qAbs(th_arc/(M_PI * 0.5 + 0.001))); 

    for (i = 0; i < n_segs; i++) { 
     pathArcSegment(path, xc, yc, 
         th0 + i * th_arc/n_segs, 
         th0 + (i + 1) * th_arc/n_segs, 
         rx, ry, x_axis_rotation); 
    } 
} 

bool parsePathDataFast(const QStringRef &dataStr, QPainterPath &path) 
{ 
    qreal x0 = 0, y0 = 0;    // starting point 
    qreal x = 0, y = 0;    // current point 
    char lastMode = 0; 
    QPointF ctrlPt; 
    const QChar *str = dataStr.constData(); 
    const QChar *end = str + dataStr.size(); 

    while (str != end) { 
     while (str->isSpace()) 
      ++str; 
     QChar pathElem = *str; 
     ++str; 
     QChar endc = *end; 
     *const_cast<QChar *>(end) = 0; // parseNumbersArray requires 0-termination that QStringRef cannot guarantee 
     QVarLengthArray<qreal, 8> arg; 
     parseNumbersArray(str, arg); 
     *const_cast<QChar *>(end) = endc; 
     if (pathElem == QLatin1Char('z') || pathElem == QLatin1Char('Z')) 
      arg.append(0);//dummy 
     const qreal *num = arg.constData(); 
     int count = arg.count(); 
     while (count > 0) { 
      qreal offsetX = x;  // correction offsets 
      qreal offsetY = y;  // for relative commands 
      switch (pathElem.unicode()) { 
      case 'm': { 
       if (count < 2) { 
        num++; 
        count--; 
        break; 
       } 
       x = x0 = num[0] + offsetX; 
       y = y0 = num[1] + offsetY; 
       num += 2; 
       count -= 2; 
       path.moveTo(x0, y0); 

       // As per 1.2 spec 8.3.2 The "moveto" commands 
       // If a 'moveto' is followed by multiple pairs of coordinates without explicit commands, 
       // the subsequent pairs shall be treated as implicit 'lineto' commands. 
       pathElem = QLatin1Char('l'); 
      } 
       break; 
      case 'M': { 
       if (count < 2) { 
        num++; 
        count--; 
        break; 
       } 
       x = x0 = num[0]; 
       y = y0 = num[1]; 
       num += 2; 
       count -= 2; 
       path.moveTo(x0, y0); 

       // As per 1.2 spec 8.3.2 The "moveto" commands 
       // If a 'moveto' is followed by multiple pairs of coordinates without explicit commands, 
       // the subsequent pairs shall be treated as implicit 'lineto' commands. 
       pathElem = QLatin1Char('L'); 
      } 
       break; 
      case 'z': 
      case 'Z': { 
       x = x0; 
       y = y0; 
       count--; // skip dummy 
       num++; 
       path.closeSubpath(); 
      } 
       break; 
      case 'l': { 
       if (count < 2) { 
        num++; 
        count--; 
        break; 
       } 
       x = num[0] + offsetX; 
       y = num[1] + offsetY; 
       num += 2; 
       count -= 2; 
       path.lineTo(x, y); 

      } 
       break; 
      case 'L': { 
       if (count < 2) { 
        num++; 
        count--; 
        break; 
       } 
       x = num[0]; 
       y = num[1]; 
       num += 2; 
       count -= 2; 
       path.lineTo(x, y); 
      } 
       break; 
      case 'h': { 
       x = num[0] + offsetX; 
       num++; 
       count--; 
       path.lineTo(x, y); 
      } 
       break; 
      case 'H': { 
       x = num[0]; 
       num++; 
       count--; 
       path.lineTo(x, y); 
      } 
       break; 
      case 'v': { 
       y = num[0] + offsetY; 
       num++; 
       count--; 
       path.lineTo(x, y); 
      } 
       break; 
      case 'V': { 
       y = num[0]; 
       num++; 
       count--; 
       path.lineTo(x, y); 
      } 
       break; 
      case 'c': { 
       if (count < 6) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c1(num[0] + offsetX, num[1] + offsetY); 
       QPointF c2(num[2] + offsetX, num[3] + offsetY); 
       QPointF e(num[4] + offsetX, num[5] + offsetY); 
       num += 6; 
       count -= 6; 
       path.cubicTo(c1, c2, e); 
       ctrlPt = c2; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'C': { 
       if (count < 6) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c1(num[0], num[1]); 
       QPointF c2(num[2], num[3]); 
       QPointF e(num[4], num[5]); 
       num += 6; 
       count -= 6; 
       path.cubicTo(c1, c2, e); 
       ctrlPt = c2; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 's': { 
       if (count < 4) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c1; 
       if (lastMode == 'c' || lastMode == 'C' || 
        lastMode == 's' || lastMode == 'S') 
        c1 = QPointF(2*x-ctrlPt.x(), 2*y-ctrlPt.y()); 
       else 
        c1 = QPointF(x, y); 
       QPointF c2(num[0] + offsetX, num[1] + offsetY); 
       QPointF e(num[2] + offsetX, num[3] + offsetY); 
       num += 4; 
       count -= 4; 
       path.cubicTo(c1, c2, e); 
       ctrlPt = c2; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'S': { 
       if (count < 4) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c1; 
       if (lastMode == 'c' || lastMode == 'C' || 
        lastMode == 's' || lastMode == 'S') 
        c1 = QPointF(2*x-ctrlPt.x(), 2*y-ctrlPt.y()); 
       else 
        c1 = QPointF(x, y); 
       QPointF c2(num[0], num[1]); 
       QPointF e(num[2], num[3]); 
       num += 4; 
       count -= 4; 
       path.cubicTo(c1, c2, e); 
       ctrlPt = c2; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'q': { 
       if (count < 4) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c(num[0] + offsetX, num[1] + offsetY); 
       QPointF e(num[2] + offsetX, num[3] + offsetY); 
       num += 4; 
       count -= 4; 
       path.quadTo(c, e); 
       ctrlPt = c; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'Q': { 
       if (count < 4) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF c(num[0], num[1]); 
       QPointF e(num[2], num[3]); 
       num += 4; 
       count -= 4; 
       path.quadTo(c, e); 
       ctrlPt = c; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 't': { 
       if (count < 2) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF e(num[0] + offsetX, num[1] + offsetY); 
       num += 2; 
       count -= 2; 
       QPointF c; 
       if (lastMode == 'q' || lastMode == 'Q' || 
        lastMode == 't' || lastMode == 'T') 
        c = QPointF(2*x-ctrlPt.x(), 2*y-ctrlPt.y()); 
       else 
        c = QPointF(x, y); 
       path.quadTo(c, e); 
       ctrlPt = c; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'T': { 
       if (count < 2) { 
        num += count; 
        count = 0; 
        break; 
       } 
       QPointF e(num[0], num[1]); 
       num += 2; 
       count -= 2; 
       QPointF c; 
       if (lastMode == 'q' || lastMode == 'Q' || 
        lastMode == 't' || lastMode == 'T') 
        c = QPointF(2*x-ctrlPt.x(), 2*y-ctrlPt.y()); 
       else 
        c = QPointF(x, y); 
       path.quadTo(c, e); 
       ctrlPt = c; 
       x = e.x(); 
       y = e.y(); 
       break; 
      } 
      case 'a': { 
       if (count < 7) { 
        num += count; 
        count = 0; 
        break; 
       } 
       qreal rx = (*num++); 
       qreal ry = (*num++); 
       qreal xAxisRotation = (*num++); 
       qreal largeArcFlag = (*num++); 
       qreal sweepFlag = (*num++); 
       qreal ex = (*num++) + offsetX; 
       qreal ey = (*num++) + offsetY; 
       count -= 7; 
       qreal curx = x; 
       qreal cury = y; 
       pathArc(path, rx, ry, xAxisRotation, int(largeArcFlag), 
         int(sweepFlag), ex, ey, curx, cury); 

       x = ex; 
       y = ey; 
      } 
       break; 
      case 'A': { 
       if (count < 7) { 
        num += count; 
        count = 0; 
        break; 
       } 
       qreal rx = (*num++); 
       qreal ry = (*num++); 
       qreal xAxisRotation = (*num++); 
       qreal largeArcFlag = (*num++); 
       qreal sweepFlag = (*num++); 
       qreal ex = (*num++); 
       qreal ey = (*num++); 
       count -= 7; 
       qreal curx = x; 
       qreal cury = y; 
       pathArc(path, rx, ry, xAxisRotation, int(largeArcFlag), 
         int(sweepFlag), ex, ey, curx, cury); 

       x = ex; 
       y = ey; 
      } 
       break; 
      default: 
       return false; 
      } 
      lastMode = pathElem.toLatin1(); 
     } 
    } 
    return true; 
} 

Una pregunta, i no encuentra constante en las cabeceras qt estándar Q_PI y reemplazarlo con M_PI esperanza está bien !!