我想用一条直线将贝塞尔曲线分成多边形链。线的数量取决于2条连接线之间的最大允许角度。 我正在寻找一种算法来找到最优化的解决方案（即尽可能减少直线的数量）。将贝塞尔曲线转换为多边形链？
我知道如何使用Casteljau或Bernstein polynomals分割贝塞尔曲线。我尝试将贝塞尔分成两半，计算直线之间的角度，如果连接线之间的角度在一定的阈值范围内，则再次分裂，但我可能会遇到快捷方式。
是否有已知的算法或伪代码可用于执行此转换？
递归地使用de Casteljau算法，直到控制点大致共线。参见例如http://www.antigrain.com/research/adaptive_bezier/index.html。
my website - > DXF - > polybezier的视觉示例。 它基本上是与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;
}
和判断通过：计算所述控制点，并通过端点的直线之间的角度。
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;
}
下面是决定何时停止递归的另一个标准：[Bézier曲线的分段线性近似]（http://hcklbrrfnn.wordpress.com/2012/08/20/piecewise-linear-approximation-of-bezier-curves /） – Hbf 2013-02-28 00:13:11
没有关于RSA平整一些替代品被报告会更快：
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 =递归细分算法 PAA =抛物线型近似算法 CAA =圆形近似算法
根据Rachela的说法，CAA比PAA慢1.5-2倍。 CAA和RSA一样慢，但在偏移曲线上达到了更好的平坦度。
似乎PAA是实际曲线的最佳选择，而CAA最适合曲线的偏移量（在抚摸曲线时）。
我测试了两篇论文的PAA，但在某些情况下失败。艾哈迈德的PAA在共线情况下失败（所有点在同一行）并且Rachela的PAA在共线情况下失败并且在两个控制点相同的情况下失败。有了一些修复程序，可能可以让它们按预期工作。
我使用Qt解决它的任何SVG路径包括贝塞尔曲线，我在SVG模块发现了一个静态函数在qsvghandler.cpp其中parsePathDataFast从SVG路径QPainterPath并在蛋糕上的樱桃！ QPainterPath有三个本地函数可以将你的路径转换为多边形（大到多边形和其他多边形到SubpathPolygons或toPillPolygons），以及像边界框，相交，翻译等好东西，可以使用Boost： ：几何现在，不是很糟糕！
#ifndef PARSEPATHDATAFAST_H
#define PARSEPATHDATAFAST_H
#include <QPainterPath>
#include <QString>
bool parsePathDataFast(const QStringRef &dataStr, QPainterPath &path);
#endif // PARSEPATHDATAFAST_H
#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;
}
有一个问题，我没有在标准qt头文件中找到Q_PI常量，我用M_PI替换它希望是OK！
我假设你有贝塞尔的控制多边形可用？这不是一个好的起点吗？为什么这里的角度很重要？我非常好奇你想要达到的目标。 – batbrat 2012-02-12 08:57:49
2个控制点可用。从曲线的起点开始确实是另一种选择，但我很好奇是否有可用的最佳解决方案。我想用它来为cnc路由设备生成输入。这台机器只能理解直线，所以贝塞尔曲线需要分成一组直线。 – 2012-02-12 09:06:41
我在阅读你的文章之前知道贝塞尔曲线，但是想把曲线划分为n st。线条让我想起康托尔的无限理论。 ;） – uday 2012-02-12 09:30:02