1 /*
2 For general Scribus (>=1.3.2) copyright and licensing information please refer
3 to the COPYING file provided with the program. Following this notice may exist
4 a copyright and/or license notice that predates the release of Scribus 1.3.2
5 for which a new license (GPL+exception) is in place.
6 */
7 /***************************************************************************
8 fpointarray.cpp - description
9 -------------------
10 begin : Mit Jul 24 2002
11 copyright : (C) 2002 by Franz Schmid
12 email : Franz.Schmid@altmuehlnet.de
13 ***************************************************************************/
14
15 /***************************************************************************
16 * *
17 * This program is free software; you can redistribute it and/or modify *
18 * it under the terms of the GNU General Public License as published by *
19 * the Free Software Foundation; either version 2 of the License, or *
20 * (at your option) any later version. *
21 * *
22 ***************************************************************************/
23
24 #include "fpointarray.h"
25 #include <cstdarg>
26
27 #if defined(_MSC_VER) && !defined(_USE_MATH_DEFINES)
28 #define _USE_MATH_DEFINES
29 #endif
30 #include <cmath>
31
32 #include <QRegExp>
33 #include <QVector>
34
35 #include "util.h"
36 #include "util_math.h"
37 #include "sclimits.h"
38
39 using namespace std;
40
41
copy() const42 FPointArray FPointArray::copy() const
43 {
44 FPointArray tmp;
45 tmp << *this;
46 tmp.QVector<FPoint>::squeeze();
47 return tmp;
48 }
49
50
operator =(const FPointArray & a)51 FPointArray & FPointArray::operator=(const FPointArray &a)
52 {
53 QVector<FPoint>::operator=(a);
54 m_svgState = nullptr;
55 QVector<FPoint>::squeeze();
56 return *this;
57 }
58
59
60 /* optimized for speed:
61 * never shrink
62 * when growing, try to double size
63 * if capacity permits, just increase count
64 */
resize(int newCount)65 bool FPointArray::resize(int newCount)
66 {
67 if (newCount <= 0)
68 {
69 QVector<FPoint>::resize(0);
70 QVector<FPoint>::squeeze();
71 }
72 else
73 {
74 QVector<FPoint>::resize(newCount);
75 }
76 return true;
77 }
78
reverse()79 void FPointArray::reverse()
80 {
81 FPointArray tmp;
82 tmp << *this;
83 tmp.QVector<FPoint>::squeeze();
84 QVector<FPoint>::resize(0);
85 QVector<FPoint>::squeeze();
86 for (int a = 0; a < tmp.count()-1; a += 2)
87 {
88 QVector<FPoint>::prepend(tmp.point(a+1));
89 QVector<FPoint>::prepend(tmp.point(a));
90 }
91 }
92
setPoints(int nPoints,double firstx,double firsty,...)93 bool FPointArray::setPoints(int nPoints, double firstx, double firsty, ...)
94 {
95 va_list ap;
96 if (nPoints < 0 || !FPointArray::resize(nPoints))
97 return false;
98 setPoint(0, firstx, firsty);
99 int i = 1;
100 double x, y;
101 nPoints--;
102 va_start(ap, firsty);
103 while (nPoints--)
104 {
105 x = static_cast<double>(va_arg(ap, double));
106 y = static_cast<double>(va_arg(ap, double));
107 setPoint(i++, x, y);
108 }
109 va_end(ap);
110 return true;
111 }
112
putPoints(int index,int nPoints,double firstx,double firsty,...)113 bool FPointArray::putPoints(int index, int nPoints, double firstx, double firsty, ...)
114 {
115 va_list ap;
116 if (index + nPoints > QVector<FPoint>::count())
117 {
118 if (!FPointArray::resize(index + nPoints))
119 return false;
120 }
121 if (nPoints <= 0)
122 return true;
123 setPoint(index, firstx, firsty); // set first point
124 int i = index + 1;
125 double x, y;
126 nPoints--;
127 va_start(ap, firsty);
128 while (nPoints--)
129 {
130 x = static_cast<double>(va_arg(ap, double));
131 y = static_cast<double>(va_arg(ap, double));
132 setPoint(i++, x, y);
133 }
134 va_end(ap);
135 return true;
136 }
137
putPoints(int index,int nPoints,const FPointArray & from,int fromIndex)138 bool FPointArray::putPoints(int index, int nPoints, const FPointArray & from, int fromIndex)
139 {
140 if (index + nPoints > QVector<FPoint>::count())
141 { // extend array
142 if (!FPointArray::resize(index + nPoints))
143 return false;
144 }
145 if (nPoints <= 0)
146 return true;
147 Iterator p = begin();
148 p += index;
149 ConstIterator q = from.begin();
150 q += fromIndex;
151 while (--nPoints >= 0)
152 {
153 *p++ = *q++;
154 }
155 return true;
156 }
157
point(int i,double * x,double * y) const158 void FPointArray::point(int i, double *x, double *y) const
159 {
160 const FPoint& p = QVector<FPoint>::at(i);
161 if (x)
162 *x = p.xp;
163 if (y)
164 *y = p.yp;
165 }
166
167
pointQ(int i) const168 QPoint FPointArray::pointQ(int i) const
169 {
170 const FPoint& p = QVector<FPoint>::at(i);
171 return QPoint(qRound(p.xp), qRound(p.yp));
172 }
173
pointQF(int i) const174 QPointF FPointArray::pointQF(int i) const
175 {
176 const FPoint& p = QVector<FPoint>::at(i);
177 QPointF r(p.xp, p.yp);
178 return r;
179 }
180
translate(double dx,double dy)181 void FPointArray::translate(double dx, double dy)
182 {
183 FPoint pt(dx, dy);
184 Iterator pend = begin();
185 pend += QVector<FPoint>::count();
186 for (Iterator p = begin(); p != pend; p++)
187 {
188 if (!isMarkerI(p))
189 *p += pt;
190 }
191 }
192
scale(double sx,double sy)193 void FPointArray::scale(double sx, double sy)
194 {
195 Iterator pend = begin();
196 pend += QVector<FPoint>::count();
197 for (Iterator p = begin(); p != pend; p++)
198 {
199 if (!isMarkerI(p))
200 p->setXY(p->x() * sx, p->y() * sy);
201 }
202 }
203
boundingRect() const204 QRectF FPointArray::boundingRect() const
205 {
206 FPoint min = getMinClipF(this);
207 FPoint max = getMaxClipF(this);
208 return QRectF(QPointF(min.x(), min.y()), QPointF(max.x(), max.y()));
209 }
210
widthHeight() const211 FPoint FPointArray::widthHeight() const
212 {
213 if (QVector<FPoint>::count() == 0)
214 return FPoint(0.0, 0.0); // null rectangle
215 ConstIterator pd = begin();
216 ConstIterator pend = begin();
217 pend += QVector<FPoint>::count();
218 double minx, maxx, miny, maxy;
219 minx = maxx = pd->xp;
220 miny = maxy = pd->yp;
221 for (++pd; pd != pend; ++pd)
222 { // find min+max x and y
223 if (isMarkerI(pd))
224 {
225 continue;
226 }
227 if (pd->xp < minx)
228 minx = pd->xp;
229 else
230 if (pd->xp > maxx)
231 maxx = pd->xp;
232 if (pd->y() < miny)
233 miny = pd->yp;
234 else
235 if (pd->yp > maxy)
236 maxy = pd->yp;
237 }
238 return FPoint(maxx - minx,maxy - miny);
239 }
240
map(const QTransform & m)241 void FPointArray::map(const QTransform& m)
242 {
243 const double m11 = m.m11();
244 const double m12 = m.m12();
245 const double m21 = m.m21();
246 const double m22 = m.m22();
247 const double dx = m.dx();
248 const double dy = m.dy();
249 double mx, my;
250 Iterator pend = begin();
251 pend += QVector<FPoint>::count();
252 for (Iterator p = begin(); p != pend; p++)
253 {
254 if (isMarkerD(p->xp, p->yp))
255 {
256 mx = p->xp;
257 my = p->yp;
258 }
259 else
260 {
261 mx = m11 * p->xp + m21 * p->yp + dx;
262 my = m22 * p->yp + m12 * p->xp + dy;
263 }
264 p->xp = mx;
265 p->yp = my;
266 }
267 }
268
setMarker()269 void FPointArray::setMarker()
270 {
271 double maxVal = std::numeric_limits<double>::max() / 2.0;
272 addQuadPoint(maxVal, maxVal, maxVal, maxVal, maxVal, maxVal, maxVal, maxVal);
273 }
274
isMarker(int pos) const275 bool FPointArray::isMarker(int pos) const
276 {
277 double maxVal = std::numeric_limits<double>::max() / 3.0;
278 const FPoint& p = QVector<FPoint>::at(pos);
279 return ((p.x() >= maxVal) && (p.y() >= maxVal));
280 }
281
isMarkerI(ConstIterator p) const282 bool FPointArray::isMarkerI(ConstIterator p) const
283 {
284 double maxVal = std::numeric_limits<double>::max() / 3.0;
285 return ((p->xp >= maxVal) && (p->yp >= maxVal));
286 }
287
isMarkerD(double x,double y) const288 bool FPointArray::isMarkerD(double x, double y) const
289 {
290 double maxVal = std::numeric_limits<double>::max() / 3.0;
291 return ((x >= maxVal) && (y >= maxVal));
292 }
293
addPoint(double x,double y)294 void FPointArray::addPoint(double x, double y)
295 {
296 QVector<FPoint>::append(FPoint(x, y));
297 }
298
addPoint(const FPoint & p)299 void FPointArray::addPoint(const FPoint& p)
300 {
301 QVector<FPoint>::append(p);
302 }
303
304
hasLastQuadPoint(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4) const305 bool FPointArray::hasLastQuadPoint(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) const
306 {
307 int i = QVector<FPoint>::count()-4;
308 if (i < 0)
309 return false;
310 ConstIterator p = begin();
311 p += i;
312 if (p->xp != x1 || p->yp != y1)
313 return false;
314 ++p;
315 if (p->xp != x2 || p->yp != y2)
316 return false;
317 ++p;
318 if (p->xp != x3 || p->yp != y3)
319 return false;
320 ++p;
321 return !(p->xp != x4 || p->yp != y4);
322 }
323
addQuadPoint(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)324 void FPointArray::addQuadPoint(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
325 {
326 QVector<FPoint>::append(FPoint(x1, y1));
327 QVector<FPoint>::append(FPoint(x2, y2));
328 QVector<FPoint>::append(FPoint(x3, y3));
329 QVector<FPoint>::append(FPoint(x4, y4));
330 }
331
addQuadPoint(const FPoint & p1,const FPoint & p2,const FPoint & p3,const FPoint & p4)332 void FPointArray::addQuadPoint(const FPoint& p1, const FPoint& p2, const FPoint& p3, const FPoint& p4)
333 {
334 QVector<FPoint>::append(p1);
335 QVector<FPoint>::append(p2);
336 QVector<FPoint>::append(p3);
337 QVector<FPoint>::append(p4);
338 }
339
lenPathSeg(int seg) const340 double FPointArray::lenPathSeg(int seg) const
341 {
342 FPoint p1 = point(seg);
343 FPoint k1 = point(seg+1);
344 FPoint p2 = point(seg+2);
345 FPoint k2 = point(seg+3);
346 FPoint newP, oldP;
347 double newLen = 1;
348 double oldLen = 0;
349 double ts = 0.5;
350 double t = 0.5;
351 int iter = 2;
352 while (true)
353 {
354 oldP = p1;
355 newLen = 0;
356 for (int dx = 0; dx < iter; ++dx)
357 {
358 double tm = 1.0 - t;
359 newP = ((tm * tm * tm) * p1) + (3 * t * (tm * tm) * k1) + (3 * t * t * tm * k2 + t * t * t * p2);
360 newLen += sqrt(pow(newP.x()-oldP.x(),2.0)+pow(newP.y()-oldP.y(),2.0));
361 oldP = newP;
362 t += ts;
363 }
364 if (fabs(newLen - oldLen) < 0.01)
365 break;
366 oldLen = newLen;
367 ts /= 2.0;
368 iter *= 2;
369 t = ts;
370 }
371 return newLen;
372 }
373
lenPathDist(int seg,double t1,double t2) const374 double FPointArray::lenPathDist(int seg, double t1, double t2) const
375 {
376 FPoint p1 = point(seg);
377 FPoint k1 = point(seg+1);
378 FPoint p2 = point(seg+2);
379 FPoint k2 = point(seg+3);
380 FPoint newP, oldP;
381 double newLen = 0;
382 double ts, t, tm;
383 tm = 1.0 - t1;
384 oldP = ((tm * tm * tm) * p1) + (3 * t1 * (tm * tm) * k1) + (3 * t1 * t1 * tm * k2 + t1 * t1 * t1 * p2);
385 ts = (t2 - t1) / 100;
386 t = t1 + ts;
387 for (int dx = 0; dx < 99; ++dx)
388 {
389 tm = 1.0 - t;
390 newP = ((tm * tm * tm) * p1) + (3 * t * (tm * tm) * k1) + (3 * t * t * tm * k2 + t * t * t * p2);
391 newLen += sqrt(pow(newP.x()-oldP.x(),2.0)+pow(newP.y()-oldP.y(),2.0));
392 oldP = newP;
393 t += ts;
394 }
395 return newLen;
396 }
397
pointTangentNormalAt(int seg,double t,FPoint * p,FPoint * tn,FPoint * n) const398 void FPointArray::pointTangentNormalAt(int seg, double t, FPoint* p, FPoint* tn, FPoint* n) const
399 {
400 // Calculate derivative if necessary.
401 FPoint d;
402 if (tn || n)
403 pointDerivativesAt(seg, t, p, &d, nullptr);
404 else
405 pointDerivativesAt(seg, t, p, nullptr, nullptr);
406 // Normalize derivative.
407 if (tn || n)
408 {
409 const double norm = sqrt(d.x() * d.x() + d.y() * d.y());
410 d = norm ? d * (1.0 / norm) : FPoint(0.0, 0.0);
411 }
412 // Assign tangent vector.
413 if (tn)
414 *tn = d;
415 // Calculate normal vector.
416 if (n)
417 {
418 // Calculate vector product of "binormal" x tangent
419 // (0,0,1) x (dx,dy,0), which is simply (dy,-dx,0).
420 n->setX(d.y());
421 n->setY(-d.x());
422 }
423 FPoint p1 = point(seg);
424 FPoint k1 = point(seg+1);
425 FPoint p2 = point(seg+2);
426 FPoint k2 = point(seg+3);
427 double tm = 1.0 - t;
428 *p = ((tm * tm * tm) * p1) + (3 * t * (tm * tm) * k1) + (3 * (t * t) * tm * k2 + (t * t * t) * p2);
429 }
430
pointDerivativesAt(int seg,double t,FPoint * p,FPoint * d1,FPoint * d2) const431 void FPointArray::pointDerivativesAt(int seg, double t, FPoint* p, FPoint* d1, FPoint* d2) const
432 {
433 // Copy points.
434 FPoint* q = new FPoint[ 4 ];
435 q[ 0 ] = point(seg);
436 q[ 1 ] = point(seg+1);
437 q[ 3 ] = point(seg+2);
438 q[ 2 ] = point(seg+3);
439 // The De Casteljau algorithm.
440 for (unsigned short j = 1; j <= 3; j++)
441 {
442 for (unsigned short i = 0; i <= 3 - j; i++)
443 {
444 q[ i ] = (1.0 - t) * q[ i ] + t * q[ i + 1 ];
445 }
446 // Save second derivative now that we have it.
447 if (j == 1)
448 {
449 if (d2)
450 *d2 = 6 * (q[ 2 ] - 2 * q[ 1 ] + q[ 0 ]);
451 }
452 // Save first derivative now that we have it.
453 else if (j == 2)
454 {
455 if (d1)
456 *d1 = 3 * (q[ 1 ] - q[ 0 ]);
457 }
458 }
459 // Save point.
460 if (p)
461 *p = q[ 0 ];
462 delete[] (q);
463 }
464
isBezierClosed() const465 bool FPointArray::isBezierClosed() const
466 {
467 int sz = size();
468 return ((sz >= 4) && (pointQF(0) == pointQF(sz - 2)));
469 }
470
471 struct SVGState
472 {
473 double CurrX, CurrY, StartX, StartY;
474 bool FirstM, WasM, PathClosed;
475 int PathLen;
476
resetSVGState477 void reset(double x, double y)
478 {
479 CurrX = x;
480 CurrY = y;
481 StartX = x;
482 StartY = y;
483 PathLen = 0;
484 }
485
moveSVGState486 void move(double x, double y, int newPoints)
487 {
488 CurrX = x;
489 CurrY = y;
490 PathLen += newPoints;
491 }
492
needsMarkerSVGState493 bool needsMarker()
494 {
495 bool result = (!FirstM) && (WasM);
496 if (result)
497 PathLen += 4;
498 return result;
499 }
500 };
501
502
svgPath(bool closed) const503 QString FPointArray::svgPath(bool closed) const
504 {
505 QString tmp = "";
506 FPoint np, np1, np2, np3, np4, firstP;
507 bool nPath = true;
508 bool first = true;
509 if (size() > 3)
510 {
511 for (int poi=0; poi < size()-3; poi += 4)
512 {
513 if (isMarker(poi))
514 {
515 nPath = true;
516 continue;
517 }
518 if (nPath)
519 {
520 np = point(poi);
521 if ((!first) && (closed) && (np4 == firstP))
522 tmp += "Z ";
523 tmp += "M"+QString::number(np.x())+" "+QString::number(np.y())+" ";
524 nPath = false;
525 first = false;
526 firstP = np;
527 np4 = np;
528 }
529 np = point(poi);
530 np1 = point(poi+1);
531 np2 = point(poi+3);
532 np3 = point(poi+2);
533 if ((np == np1) && (np2 == np3))
534 tmp += QString("L%1 %2 ").arg(np3.x()).arg(np3.y());
535 else
536 tmp += QString("C%1 %2 %3 %4 %5 %6 ").arg(np1.x()).arg(np1.y()).arg(np2.x()).arg(np2.y()).arg(np3.x()).arg(np3.y());
537 np4 = np3;
538 }
539 if (closed)
540 tmp += "Z";
541 }
542 return tmp;
543 }
544
toQPainterPath(bool closed) const545 QPainterPath FPointArray::toQPainterPath(bool closed) const
546 {
547 QPainterPath m_path = QPainterPath();
548 bool nPath = true;
549 bool first = true;
550 FPoint np, np1, np2, np3, np4, firstP;
551 if (size() > 3)
552 {
553 for (int poi = 0; poi < size()-3; poi += 4)
554 {
555 if (isMarker(poi))
556 {
557 nPath = true;
558 continue;
559 }
560 if (nPath)
561 {
562 np = point(poi);
563 if ((!first) && (closed) && (np4 == firstP))
564 m_path.closeSubpath();
565 m_path.moveTo(np.x(), np.y());
566 nPath = false;
567 first = false;
568 firstP = np;
569 np4 = np;
570 }
571 np = point(poi);
572 np1 = point(poi+1);
573 np2 = point(poi+3);
574 np3 = point(poi+2);
575 if ((np == np1) && (np2 == np3))
576 m_path.lineTo(np3.x(), np3.y());
577 else
578 m_path.cubicTo(np1.x(), np1.y(), np2.x(), np2.y(), np3.x(), np3.y());
579 np4 = np3;
580 }
581 if (closed)
582 m_path.closeSubpath();
583 }
584 return m_path;
585 }
586
fromQPainterPath(QPainterPath & path,bool close)587 void FPointArray::fromQPainterPath(QPainterPath &path, bool close)
588 {
589 resize(0);
590 svgInit();
591 for (int i = 0; i < path.elementCount(); ++i)
592 {
593 const QPainterPath::Element &elm = path.elementAt(i);
594 switch (elm.type)
595 {
596 case QPainterPath::MoveToElement:
597 if (m_svgState->WasM)
598 svgClosePath();
599 m_svgState->WasM = true;
600 svgMoveTo(elm.x, elm.y);
601 break;
602 case QPainterPath::LineToElement:
603 svgLineTo(elm.x, elm.y);
604 break;
605 case QPainterPath::CurveToElement:
606 svgCurveToCubic(elm.x, elm.y, path.elementAt(i + 1).x, path.elementAt(i + 1).y, path.elementAt(i + 2).x, path.elementAt(i + 2).y);
607 break;
608 default:
609 break;
610 }
611 }
612 if (close)
613 svgClosePath();
614 }
615
~FPointArray()616 FPointArray::~FPointArray()
617 {
618 delete m_svgState;
619 }
620
621
svgInit()622 void FPointArray::svgInit()
623 {
624 if (!m_svgState)
625 m_svgState = new SVGState;
626 m_svgState->reset(0,0);
627 m_svgState->FirstM = true;
628 m_svgState->WasM = false;
629 }
630
631
svgMoveTo(double x,double y)632 void FPointArray::svgMoveTo(double x, double y)
633 {
634 if (!m_svgState)
635 return;
636 m_svgState->reset(x, y);
637 m_svgState->WasM = true;
638 }
639
640
svgLineTo(double x1,double y1)641 void FPointArray::svgLineTo(double x1, double y1)
642 {
643 if (!m_svgState)
644 return;
645 if (m_svgState->needsMarker())
646 setMarker();
647 m_svgState->FirstM = false;
648 m_svgState->WasM = false;
649 if (size() > 3)
650 {
651 FPoint b1 = point(size()-4);
652 FPoint b2 = point(size()-3);
653 FPoint b3 = point(size()-2);
654 FPoint b4 = point(size()-1);
655 FPoint n1 = FPoint(m_svgState->CurrX, m_svgState->CurrY);
656 FPoint n2 = FPoint(x1, y1);
657 if ((b1 == n1) && (b2 == n1) && (b3 == n2) && (b4 == n2))
658 return;
659 }
660 addPoint(FPoint(m_svgState->CurrX, m_svgState->CurrY));
661 addPoint(FPoint(m_svgState->CurrX, m_svgState->CurrY));
662 addPoint(FPoint(x1, y1));
663 addPoint(FPoint(x1, y1));
664 m_svgState->move(x1, y1, 4);
665 }
666
667
svgCurveToCubic(double x1,double y1,double x2,double y2,double x3,double y3)668 void FPointArray::svgCurveToCubic(double x1, double y1, double x2, double y2, double x3, double y3)
669 {
670 if (!m_svgState)
671 return;
672 if (m_svgState->needsMarker())
673 setMarker();
674 m_svgState->FirstM = false;
675 m_svgState->WasM = false;
676 if (m_svgState->PathLen > 3)
677 {
678 FPoint b1 = point(size()-4);
679 FPoint b2 = point(size()-3);
680 FPoint b3 = point(size()-2);
681 FPoint b4 = point(size()-1);
682 FPoint n1 = FPoint(m_svgState->CurrX, m_svgState->CurrY);
683 FPoint n2 = FPoint(x1, y1);
684 FPoint n3 = FPoint(x3, y3);
685 FPoint n4 = FPoint(x2, y2);
686 if ((b1 == n1) && (b2 == n2) && (b3 == n3) && (b4 == n4))
687 return;
688 }
689 addPoint(FPoint(m_svgState->CurrX, m_svgState->CurrY));
690 addPoint(FPoint(x1, y1));
691 addPoint(FPoint(x3, y3));
692 addPoint(FPoint(x2, y2));
693 m_svgState->move(x3, y3, 4);
694 }
695
696
svgClosePath()697 void FPointArray::svgClosePath()
698 {
699 if (!m_svgState)
700 return;
701 if (m_svgState->PathLen > 2)
702 {
703 if ((m_svgState->PathLen == 4) || (point(size()-2).x() != m_svgState->StartX) || (point(size()-2).y() != m_svgState->StartY))
704 {
705 addPoint(point(size()-2));
706 addPoint(point(size()-3));
707 addPoint(FPoint(m_svgState->StartX, m_svgState->StartY));
708 addPoint(FPoint(m_svgState->StartX, m_svgState->StartY));
709 }
710 }
711 }
712
svgArcTo(double r1,double r2,double angle,bool largeArcFlag,bool sweepFlag,double x1,double y1)713 void FPointArray::svgArcTo(double r1, double r2, double angle, bool largeArcFlag, bool sweepFlag, double x1, double y1)
714 {
715 if (!m_svgState)
716 return;
717 calculateArc(false, m_svgState->CurrX, m_svgState->CurrY, angle, x1, y1, r1, r2, largeArcFlag, sweepFlag);
718 }
719
calculateArc(bool relative,double & curx,double & cury,double angle,double x,double y,double r1,double r2,bool largeArcFlag,bool sweepFlag)720 void FPointArray::calculateArc(bool relative, double &curx, double &cury, double angle,
721 double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag)
722 {
723 double sin_th, cos_th;
724 double a00, a01, a10, a11;
725 double x0, y0, x1, y1, xc, yc;
726 double d, sfactor, sfactor_sq;
727 double th0, th1, th_arc;
728 int i, n_segs;
729 sin_th = sin(angle * (M_PI / 180.0));
730 cos_th = cos(angle * (M_PI / 180.0));
731 double dx;
732 if (!relative)
733 dx = (curx - x) / 2.0;
734 else
735 dx = -x / 2.0;
736 double dy;
737 if (!relative)
738 dy = (cury - y) / 2.0;
739 else
740 dy = -y / 2.0;
741 double _x1 = cos_th * dx + sin_th * dy;
742 double _y1 = -sin_th * dx + cos_th * dy;
743 double Pr1 = r1 * r1;
744 double Pr2 = r2 * r2;
745 double Px = _x1 * _x1;
746 double Py = _y1 * _y1;
747 // Spec : check if radii are large enough
748 double check = Px / Pr1 + Py / Pr2;
749 if (check > 1)
750 {
751 r1 = r1 * sqrt(check);
752 r2 = r2 * sqrt(check);
753 }
754 a00 = cos_th / r1;
755 a01 = sin_th / r1;
756 a10 = -sin_th / r2;
757 a11 = cos_th / r2;
758 x0 = a00 * curx + a01 * cury;
759 y0 = a10 * curx + a11 * cury;
760 if (!relative)
761 x1 = a00 * x + a01 * y;
762 else
763 x1 = a00 * (curx + x) + a01 * (cury + y);
764 if (!relative)
765 y1 = a10 * x + a11 * y;
766 else
767 y1 = a10 * (curx + x) + a11 * (cury + y);
768 /* (x0, y0) is current point in transformed coordinate space.
769 (x1, y1) is new point in transformed coordinate space.
770
771 The arc fits a unit-radius circle in this space.
772 */
773 d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
774 sfactor_sq = 1.0 / d - 0.25;
775 if (sfactor_sq < 0)
776 sfactor_sq = 0;
777 sfactor = sqrt(sfactor_sq);
778 if (sweepFlag == largeArcFlag)
779 sfactor = -sfactor;
780 xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0);
781 yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0);
782
783 /* (xc, yc) is center of the circle. */
784 th0 = atan2(y0 - yc, x0 - xc);
785 th1 = atan2(y1 - yc, x1 - xc);
786 th_arc = th1 - th0;
787 if (th_arc < 0 && sweepFlag)
788 th_arc += 2 * M_PI;
789 else if (th_arc > 0 && !sweepFlag)
790 th_arc -= 2 * M_PI;
791 n_segs = static_cast<int>(ceil(fabs(th_arc / (M_PI * 0.5 + 0.001))));
792 for (i = 0; i < n_segs; i++)
793 {
794 {
795 double sin_th, cos_th;
796 double a00, a01, a10, a11;
797 double x1, y1, x2, y2, x3, y3;
798 double t;
799 double th_half;
800 double _th0 = th0 + i * th_arc / n_segs;
801 double _th1 = th0 + (i + 1) * th_arc / n_segs;
802 sin_th = sin(angle * (M_PI / 180.0));
803 cos_th = cos(angle * (M_PI / 180.0));
804 /* inverse transform compared with rsvg_path_arc */
805 a00 = cos_th * r1;
806 a01 = -sin_th * r2;
807 a10 = sin_th * r1;
808 a11 = cos_th * r2;
809 th_half = 0.5 * (_th1 - _th0);
810 t = (8.0 / 3.0) * sin(th_half * 0.5) * sin(th_half * 0.5) / sin(th_half);
811 x1 = xc + cos(_th0) - t * sin(_th0);
812 y1 = yc + sin(_th0) + t * cos(_th0);
813 x3 = xc + cos(_th1);
814 y3 = yc + sin(_th1);
815 x2 = x3 + t * sin(_th1);
816 y2 = y3 - t * cos(_th1);
817 svgCurveToCubic(a00 * x1 + a01 * y1, a10 * x1 + a11 * y1, a00 * x2 + a01 * y2, a10 * x2 + a11 * y2, a00 * x3 + a01 * y3, a10 * x3 + a11 * y3);
818 }
819 }
820 if (!relative)
821 curx = x;
822 else
823 curx += x;
824 if (!relative)
825 cury = y;
826 else
827 cury += y;
828 }
829
830
getCoord(const char * ptr,double & number)831 static const char * getCoord(const char *ptr, double &number)
832 {
833 int integer, exponent;
834 double decimal, frac;
835 int sign, expsign;
836
837 exponent = 0;
838 integer = 0;
839 frac = 1.0;
840 decimal = 0;
841 sign = 1;
842 expsign = 1;
843
844 // read the sign
845 if (*ptr == '+')
846 ptr++;
847 else if (*ptr == '-')
848 {
849 ptr++;
850 sign = -1;
851 }
852
853 // Check for nan value
854 if (*ptr == 'n' || *ptr == 'N')
855 {
856 bool isNan = true;
857 const char *tmpPtr = ptr + 1;
858 isNan &= (*tmpPtr == 'a' || *tmpPtr == 'A');
859 if (*tmpPtr != '\0')
860 ++tmpPtr;
861 isNan &= (*tmpPtr == 'n' || *tmpPtr == 'N');
862 if (*tmpPtr != '\0')
863 ++tmpPtr;
864 isNan &= (*tmpPtr == ' ' || *tmpPtr == '\0');
865 if (isNan)
866 {
867 number = 0.0;
868 ptr += 3;
869 if (*ptr == ' ')
870 ++ptr;
871 return ptr;
872 }
873 }
874
875 // read the integer part
876 while (*ptr != '\0' && *ptr >= '0' && *ptr <= '9')
877 integer = (integer * 10) + *(ptr++) - '0';
878 if (*ptr == '.') // read the decimals
879 {
880 ptr++;
881 while (*ptr != '\0' && *ptr >= '0' && *ptr <= '9')
882 decimal += (*(ptr++) - '0') * (frac *= 0.1);
883 }
884
885 if (*ptr == 'e' || *ptr == 'E') // read the exponent part
886 {
887 ptr++;
888
889 // read the sign of the exponent
890 if (*ptr == '+')
891 ptr++;
892 else if (*ptr == '-')
893 {
894 ptr++;
895 expsign = -1;
896 }
897
898 exponent = 0;
899 while (*ptr != '\0' && *ptr >= '0' && *ptr <= '9')
900 {
901 exponent *= 10;
902 exponent += *ptr - '0';
903 ptr++;
904 }
905 }
906 number = integer + decimal;
907 number *= sign * pow(static_cast<double>(10), static_cast<double>(expsign * exponent));
908 // skip the following space
909 if (*ptr == ' ')
910 ptr++;
911
912 return ptr;
913 }
914
915
parseSVG(const QString & svgPath)916 bool FPointArray::parseSVG(const QString& svgPath)
917 {
918 QString d = svgPath;
919 d = d.replace(QRegExp(","), " ");
920
921 bool ret = false;
922 if (d.isEmpty())
923 return false;
924
925 d = d.simplified();
926 QByteArray pathData = d.toLatin1();
927 const char *ptr = pathData.constData();
928 const char *end = pathData.constData() + pathData.length() + 1;
929 double contrlx, contrly, curx, cury, subpathx, subpathy, tox, toy, x1, y1, x2, y2, xc, yc;
930 double px1, py1, px2, py2, px3, py3;
931 bool relative;
932 int moveCount = 0;
933 svgInit();
934 char command = *(ptr++), lastCommand = ' ';
935 subpathx = subpathy = curx = cury = contrlx = contrly = 0.0;
936 while (ptr < end)
937 {
938 if (*ptr == ' ')
939 ptr++;
940 relative = false;
941 switch (command)
942 {
943 case 'f':
944 case 'F':
945 {
946 ptr = getCoord(ptr, tox);
947 break;
948 }
949 case 'm':
950 relative = true;
951 case 'M':
952 {
953 ptr = getCoord(ptr, tox);
954 ptr = getCoord(ptr, toy);
955 m_svgState->WasM = true;
956 subpathx = curx = relative ? curx + tox : tox;
957 subpathy = cury = relative ? cury + toy : toy;
958 svgMoveTo(curx, cury);
959 moveCount++;
960 break;
961 }
962 case 'l':
963 relative = true;
964 case 'L':
965 {
966 ptr = getCoord(ptr, tox);
967 ptr = getCoord(ptr, toy);
968 curx = relative ? curx + tox : tox;
969 cury = relative ? cury + toy : toy;
970 svgLineTo(curx, cury);
971 break;
972 }
973 case 'h':
974 {
975 ptr = getCoord(ptr, tox);
976 curx = curx + tox;
977 svgLineTo(curx, cury);
978 break;
979 }
980 case 'H':
981 {
982 ptr = getCoord(ptr, tox);
983 curx = tox;
984 svgLineTo(curx, cury);
985 break;
986 }
987 case 'v':
988 {
989 ptr = getCoord(ptr, toy);
990 cury = cury + toy;
991 svgLineTo(curx, cury);
992 break;
993 }
994 case 'V':
995 {
996 ptr = getCoord(ptr, toy);
997 cury = toy;
998 svgLineTo( curx, cury);
999 break;
1000 }
1001 case 'z':
1002 case 'Z':
1003 {
1004 curx = subpathx;
1005 cury = subpathy;
1006 svgClosePath();
1007 break;
1008 }
1009 case 'c':
1010 relative = true;
1011 case 'C':
1012 {
1013 ptr = getCoord(ptr, x1);
1014 ptr = getCoord(ptr, y1);
1015 ptr = getCoord(ptr, x2);
1016 ptr = getCoord(ptr, y2);
1017 ptr = getCoord(ptr, tox);
1018 ptr = getCoord(ptr, toy);
1019 px1 = relative ? curx + x1 : x1;
1020 py1 = relative ? cury + y1 : y1;
1021 px2 = relative ? curx + x2 : x2;
1022 py2 = relative ? cury + y2 : y2;
1023 px3 = relative ? curx + tox : tox;
1024 py3 = relative ? cury + toy : toy;
1025 svgCurveToCubic(px1, py1, px2, py2, px3, py3);
1026 contrlx = relative ? curx + x2 : x2;
1027 contrly = relative ? cury + y2 : y2;
1028 curx = relative ? curx + tox : tox;
1029 cury = relative ? cury + toy : toy;
1030 break;
1031 }
1032 case 's':
1033 relative = true;
1034 case 'S':
1035 {
1036 ptr = getCoord(ptr, x2);
1037 ptr = getCoord(ptr, y2);
1038 ptr = getCoord(ptr, tox);
1039 ptr = getCoord(ptr, toy);
1040 px1 = 2 * curx - contrlx;
1041 py1 = 2 * cury - contrly;
1042 px2 = relative ? curx + x2 : x2;
1043 py2 = relative ? cury + y2 : y2;
1044 px3 = relative ? curx + tox : tox;
1045 py3 = relative ? cury + toy : toy;
1046 svgCurveToCubic(px1, py1, px2, py2, px3, py3);
1047 contrlx = relative ? curx + x2 : x2;
1048 contrly = relative ? cury + y2 : y2;
1049 curx = relative ? curx + tox : tox;
1050 cury = relative ? cury + toy : toy;
1051 break;
1052 }
1053 case 'q':
1054 relative = true;
1055 case 'Q':
1056 {
1057 ptr = getCoord(ptr, x1);
1058 ptr = getCoord(ptr, y1);
1059 ptr = getCoord(ptr, tox);
1060 ptr = getCoord(ptr, toy);
1061 px1 = relative ? (curx + 2 * (x1 + curx)) * (1.0 / 3.0) : (curx + 2 * x1) * (1.0 / 3.0);
1062 py1 = relative ? (cury + 2 * (y1 + cury)) * (1.0 / 3.0) : (cury + 2 * y1) * (1.0 / 3.0);
1063 px2 = relative ? ((curx + tox) + 2 * (x1 + curx)) * (1.0 / 3.0) : (tox + 2 * x1) * (1.0 / 3.0);
1064 py2 = relative ? ((cury + toy) + 2 * (y1 + cury)) * (1.0 / 3.0) : (toy + 2 * y1) * (1.0 / 3.0);
1065 px3 = relative ? curx + tox : tox;
1066 py3 = relative ? cury + toy : toy;
1067 svgCurveToCubic(px1, py1, px2, py2, px3, py3);
1068 contrlx = relative ? curx + x1 : (tox + 2 * x1) * (1.0 / 3.0);
1069 contrly = relative ? cury + y1 : (toy + 2 * y1) * (1.0 / 3.0);
1070 curx = relative ? curx + tox : tox;
1071 cury = relative ? cury + toy : toy;
1072 break;
1073 }
1074 case 't':
1075 relative = true;
1076 case 'T':
1077 {
1078 ptr = getCoord(ptr, tox);
1079 ptr = getCoord(ptr, toy);
1080 xc = 2 * curx - contrlx;
1081 yc = 2 * cury - contrly;
1082 px1 = relative ? (curx + 2 * xc) * (1.0 / 3.0) : (curx + 2 * xc) * (1.0 / 3.0);
1083 py1 = relative ? (cury + 2 * yc) * (1.0 / 3.0) : (cury + 2 * yc) * (1.0 / 3.0);
1084 px2 = relative ? ((curx + tox) + 2 * xc) * (1.0 / 3.0) : (tox + 2 * xc) * (1.0 / 3.0);
1085 py2 = relative ? ((cury + toy) + 2 * yc) * (1.0 / 3.0) : (toy + 2 * yc) * (1.0 / 3.0);
1086 px3 = relative ? curx + tox : tox;
1087 py3 = relative ? cury + toy : toy;
1088 svgCurveToCubic(px1, py1, px2, py2, px3, py3);
1089 contrlx = xc;
1090 contrly = yc;
1091 curx = relative ? curx + tox : tox;
1092 cury = relative ? cury + toy : toy;
1093 break;
1094 }
1095 case 'a':
1096 relative = true;
1097 case 'A':
1098 {
1099 bool largeArc, sweep;
1100 double angle, rx, ry;
1101 ptr = getCoord(ptr, rx);
1102 ptr = getCoord(ptr, ry);
1103 ptr = getCoord(ptr, angle);
1104 ptr = getCoord(ptr, tox);
1105 largeArc = tox == 1;
1106 ptr = getCoord(ptr, tox);
1107 sweep = tox == 1;
1108 ptr = getCoord(ptr, tox);
1109 ptr = getCoord(ptr, toy);
1110 calculateArc(relative, curx, cury, angle, tox, toy, rx, ry, largeArc, sweep);
1111 }
1112 }
1113 lastCommand = command;
1114 if (*ptr == '+' || *ptr == '-' || *ptr == '.' || (*ptr >= '0' && *ptr <= '9'))
1115 {
1116 // there are still coords in this command
1117 if (command == 'M')
1118 command = 'L';
1119 else if (command == 'm')
1120 command = 'l';
1121 }
1122 else
1123 command = *(ptr++);
1124
1125 if (lastCommand != 'C' && lastCommand != 'c' &&
1126 lastCommand != 'S' && lastCommand != 's' &&
1127 lastCommand != 'Q' && lastCommand != 'q' &&
1128 lastCommand != 'T' && lastCommand != 't')
1129 {
1130 contrlx = curx;
1131 contrly = cury;
1132 }
1133 }
1134 if (((lastCommand != 'z') && (lastCommand != 'Z')) || (moveCount > 1))
1135 ret = true;
1136 if (size() > 2)
1137 {
1138 const FPoint& p0 = point(0);
1139 const FPoint& p2 = point(size() - 2);
1140 if ((p0.x() == p2.x()) && (p0.y() == p2.y()) && (moveCount == 1))
1141 ret = false;
1142 }
1143
1144 return ret;
1145 }
1146
1147