chuyển đổi đường cong bezier thành chuỗi đa giác?

Question

Tôi muốn chia một đường cong bezier thành một chuỗi đa giác với n đường thẳng. Số dòng phụ thuộc vào góc cho phép tối đa giữa 2 đường kết nối. Tôi đang tìm một thuật toán để tìm ra giải pháp tối ưu nhất (tức là giảm số lượng đường thẳng càng nhiều càng tốt).

Tôi biết cách phân chia đường cong bezier bằng cách sử dụng đa thức Casteljau hoặc Bernstein. Tôi đã thử chia bezier thành một nửa tính toán góc giữa các đường thẳng, và chia một lần nữa nếu góc giữa các đường kết nối nằm trong phạm vi ngưỡng nhất định, nhưng tôi có thể chạy vào các phím tắt.

Có một thuật toán hoặc mã giả nào đã biết để thực hiện chuyển đổi này không?

Answer 1

Sử dụng thuật toán de Casteljau đệ quy cho đến khi các điểm điều khiển gần đúng. Xem ví dụ http://www.antigrain.com/research/adaptive_bezier/index.html.

Answer 2

Ví dụ trực quan trên my website -> DXF -> polybezier. về cơ bản nó là một phân tách đệ quy với 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; 
} 

Và phán đoán bằng cách: tính góc giữa các điểm kiểm soát và đường thẳng qua điểm cuối.

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

Có một số lựa chọn thay thế cho RSA phẳng được báo cáo là nhanh hơn:

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 = đệ quy Thuật toán phân ngành PAA = xấp xỉ parabol Thuật toán CAA = Thuật toán xấp xỉ xấp xỉ

Theo Rachela, CAA chậm hơn PAA theo hệ số 1,5–2. CAA chậm như RSA, nhưng đạt được độ phẳng yêu cầu tốt hơn trong các đường cong bù đắp.

Có vẻ như PAA là lựa chọn tốt nhất cho đường cong thực tế và CAA là tốt nhất cho đường cong bù đắp (khi vuốt ve đường cong).

Tôi đã kiểm tra PAA của cả hai luận án, nhưng chúng không thành công trong một số trường hợp. PAA của Ahmad thất bại trong các trường hợp collinear (tất cả các điểm trên cùng một dòng) và PAA của Rachela thất bại trong trường hợp collinear và trong trường hợp cả hai điểm kiểm soát đều bình đẳng. Với một số bản sửa lỗi, có thể làm cho chúng hoạt động như mong đợi.

Answer 4

tôi giải quyết nó với qt cho bất kỳ đường dẫn svg nào bao gồm đường cong bezier, tôi tìm thấy trong mô-đun svg một hàm tĩnh trong qsvghandler.cpp mà parsePathDataFast từ đường dẫn svg của bạn đến QPainterPath và cherry trên bánh !! QPainterPath có ba hàm gốc để chuyển đổi đường dẫn của bạn thành đa giác (đường dẫn toFillPolygon và các đường dẫn khác chia thành danh sách đa giác thànhSubpathPolygons hoặc toFillPolygons) cùng với các nội dung đẹp như hộp giới hạn, giao nhau, dịch ... sẵn sàng để sử dụng với Boost: : Hình học bây giờ, không quá tệ!

header parsepathdatafast.h

#ifndef PARSEPATHDATAFAST_H 
#define PARSEPATHDATAFAST_H 

#include <QPainterPath> 
#include <QString> 

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

#endif // PARSEPATHDATAFAST_H 

mã parsepathdatafast.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; 
} 

Một câu hỏi, tôi không tìm thấy hằng số Q_PI trong tiêu đề qt tiêu chuẩn và tôi thay thế nó bằng M_PI hy vọng là OK !!