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 util.cpp - description
9 -------------------
10 begin : Fri Sep 14 2001
11 copyright : (C) 2001 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 <QRegion>
25 #include "util_math.h"
26 #include "scconfig.h"
27 #include "sclimits.h"
28 #include "fpoint.h"
29 #include "fpointarray.h"
30
31 using namespace std;
32
getDouble(const QByteArray & in,bool raw)33 uint getDouble(const QByteArray& in, bool raw)
34 {
35 QByteArray bb(4, ' ');
36 if (raw)
37 {
38 bb[3] = in.at(0);
39 bb[2] = in.at(1);
40 bb[1] = in.at(2);
41 bb[0] = in.at(3);
42 }
43 else
44 {
45 bb[0] = in.at(0);
46 bb[1] = in.at(1);
47 bb[2] = in.at(2);
48 bb[3] = in.at(3);
49 }
50 uint ret;
51 ret = bb[0] & 0xff;
52 ret |= (bb[1] << 8) & 0xff00;
53 ret |= (bb[2] << 16) & 0xff0000;
54 ret |= (bb[3] << 24) & 0xff000000;
55 return ret;
56 }
57
regularPolygonPath(double w,double h,uint c,bool star,double factor,double rota,double factor2,double innerRot,double factor3)58 QPainterPath regularPolygonPath(double w, double h, uint c, bool star, double factor, double rota, double factor2, double innerRot, double factor3)
59 {
60 uint cx = star ? c * 2 : c;
61 double seg = 360.0 / cx;
62 double sc = rota + 180.0;
63 double di = factor;
64 double mx = 0;
65 double my = 0;
66 double trueLength = sqrt(pow(sin(seg / 180.0 * M_PI) * (w / 2.0), 2) + pow(cos(seg / 180.0 * M_PI) * (h / 2.0) + (h/2.0) - h, 2));
67 QPainterPath pts;
68 // calculate corner Points first
69 QList<QPointF> cornerPoints;
70 cornerPoints.reserve(cx);
71 for (uint x = 0; x < cx; ++x)
72 {
73 sc = seg * x + 180.0 + rota;
74 if (star)
75 {
76 double wf = w / 2.0;
77 double hf = h / 2.0;
78 if (x % 2 != 0)
79 {
80 wf *= di;
81 hf *= di;
82 sc += innerRot;
83 }
84 mx = sin(sc / 180.0 * M_PI) * (wf) + (w/2.0);
85 my = cos(sc / 180.0 * M_PI) * (hf) + (h/2.0);
86 }
87 else
88 {
89 mx = sin(sc / 180.0 * M_PI) * (w/2.0) + (w/2.0);
90 my = cos(sc / 180.0 * M_PI) * (h/2.0) + (h/2.0);
91 }
92 cornerPoints.append(QPointF(mx, my));
93 }
94 // now calculate bezier control points if needed;
95 if (star)
96 {
97 pts.moveTo(cornerPoints[0]);
98 double mxc1 = 0.0;
99 double myc1 = 0.0;
100 double mxc2 = 0.0;
101 double myc2 = 0.0;
102 for (int i = 0; i < cornerPoints.count() - 2; i++)
103 {
104 sc = seg * i + 180.0 + rota;
105 if (i % 2 != 0)
106 {
107 // outer control point
108 QLineF oline = QLineF(cornerPoints[i+1], cornerPoints[i-1]);
109 mxc1 = oline.pointAt(factor3).x();
110 myc1 = oline.pointAt(factor3).y();
111 // inner control point
112 mxc2 = sin((sc + 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints[i].x();
113 myc2 = cos((sc + 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints[i].y();
114 pts.cubicTo(QPointF(mxc2, myc2), QPointF(mxc1, myc1), cornerPoints[i+1]);
115 }
116 else
117 {
118 // outer control point
119 QLineF oline = QLineF(cornerPoints[i], cornerPoints[i+2]);
120 mxc1 = oline.pointAt(factor3).x();
121 myc1 = oline.pointAt(factor3).y();
122 // inner control point
123 mxc2 = sin((sc - 90.0 + seg) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints[i+1].x();
124 myc2 = cos((sc - 90.0 + seg) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints[i+1].y();
125 pts.cubicTo(QPointF(mxc1, myc1), QPointF(mxc2, myc2), cornerPoints[i+1]);
126 }
127 }
128 // outer control point
129 QLineF oline = QLineF(cornerPoints[cornerPoints.count()-2], cornerPoints[0]);
130 mxc1 = oline.pointAt(factor3).x();
131 myc1 = oline.pointAt(factor3).y();
132 // inner control point
133 sc = seg * (cornerPoints.count()-1) + 180.0 + rota;
134 mxc2 = sin((sc - 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints.last().x();
135 myc2 = cos((sc - 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints.last().y();
136 pts.cubicTo(QPointF(mxc1, myc1), QPointF(mxc2, myc2), cornerPoints.last());
137 oline = QLineF(cornerPoints[0], cornerPoints[cornerPoints.count()-2]);
138 mxc1 = oline.pointAt(factor3).x();
139 myc1 = oline.pointAt(factor3).y();
140 // inner control point
141 mxc2 = sin((sc + 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints.last().x();
142 myc2 = cos((sc + 90.0) / 180.0 * M_PI) * (trueLength * factor2) + cornerPoints.last().y();
143 pts.cubicTo(QPointF(mxc2, myc2), QPointF(mxc1, myc1), cornerPoints[0]);
144 pts.closeSubpath();
145 }
146 else
147 {
148 pts.moveTo(cornerPoints[0]);
149 for (int i = 1; i < cornerPoints.count(); i++)
150 pts.lineTo(cornerPoints[i]);
151 pts.closeSubpath();
152 }
153 return pts;
154 }
155
spiralPath(double spiralWidth,double spiralHeight,double spiralStartAngle,double spiralEndAngle,double spiralFactor)156 QPainterPath spiralPath(double spiralWidth, double spiralHeight, double spiralStartAngle, double spiralEndAngle, double spiralFactor)
157 {
158 if (spiralStartAngle >= spiralEndAngle)
159 return QPainterPath();
160 double startAngleK = spiralStartAngle;
161 double endAngleK = spiralEndAngle;
162 QPainterPath path;
163 QPainterPath path2;
164 double sh = spiralHeight / (spiralFactor + 1.0);
165 double sw = 0.0;
166 double ww = spiralWidth;
167 double hh = spiralHeight - sh;
168 double segStart = 0.0;
169 double segEnd = 180.0;
170 double spanAngle = 180.0;
171 double startAngle = 0.0;
172 bool segPart = true;
173 bool draw = false;
174 QPointF tp;
175 path2.moveTo(sw, sh);
176 while (segStart < endAngleK)
177 {
178 if (startAngleK >= segEnd)
179 {
180 tp = path2.currentPosition();
181 if (segPart)
182 {
183 sw = tp.x();
184 sh = spiralHeight / (spiralFactor + 1.0);
185 path2.arcTo(sw, sh - hh, ww, hh * 2, 180, 180);
186 }
187 else
188 {
189 sw = tp.x() - ww;
190 sh = spiralHeight / (spiralFactor + 1.0) - hh;
191 path2.arcTo(sw, sh, ww, hh * 2, 0, 180);
192 }
193 segPart = !segPart;
194 ww /= spiralFactor;
195 hh /= spiralFactor;
196 segStart += 180.0;
197 segEnd += 180.0;
198 spanAngle = 180.0;
199 continue;
200 }
201 if ((startAngleK >= segStart) && (startAngleK <= segEnd))
202 {
203 startAngle = startAngleK + 180;
204 spanAngle = segEnd - startAngleK;
205 if ((endAngleK >= segStart) && (endAngleK <= segEnd))
206 spanAngle -= segEnd - endAngleK;
207 if (segPart)
208 {
209 sw = tp.x();
210 sh = spiralHeight / (spiralFactor + 1.0);
211 path.arcMoveTo(sw, sh - hh, ww, hh * 2, startAngle);
212 path.arcTo(sw, sh - hh, ww, hh * 2, startAngle, spanAngle);
213 startAngle = 0.0;
214 }
215 else
216 {
217 sw = tp.x() - ww;
218 sh = spiralHeight / (spiralFactor + 1.0) - hh;
219 path.arcMoveTo(sw, sh, ww, hh * 2, startAngle);
220 path.arcTo(sw, sh, ww, hh * 2, startAngle, spanAngle);
221 startAngle = 180.0;
222 }
223 draw = true;
224 segPart = !segPart;
225 ww /= spiralFactor;
226 hh /= spiralFactor;
227 if ((endAngleK >= segStart) && (endAngleK <= segEnd))
228 break;
229 segStart += 180.0;
230 segEnd += 180.0;
231 spanAngle = 180.0;
232 continue;
233 }
234 if ((endAngleK >= segStart) && (endAngleK <= segEnd))
235 spanAngle -= segEnd - endAngleK;
236 tp = path.currentPosition();
237 if (segPart)
238 {
239 sw = tp.x();
240 sh = tp.y();
241 if (draw)
242 path.arcTo(sw, sh - hh, ww, hh * 2, startAngle, spanAngle);
243 startAngle = 0.0;
244 }
245 else
246 {
247 sw = tp.x() - ww;
248 sh = tp.y() - hh;
249 if (draw)
250 path.arcTo(sw, sh, ww, hh * 2, startAngle, spanAngle);
251 startAngle = 180.0;
252 }
253 segPart = !segPart;
254 ww /= spiralFactor;
255 hh /= spiralFactor;
256 if ((endAngleK >= segStart) && (endAngleK <= segEnd))
257 break;
258 segStart += 180.0;
259 segEnd += 180.0;
260 spanAngle = 180.0;
261 }
262 return path;
263 }
264
decomposePath(QPainterPath & path)265 QList<QPainterPath> decomposePath(QPainterPath &path)
266 {
267 QList<QPainterPath> ret;
268 QPainterPath part;
269 QPainterPath::Element element1;
270 QPainterPath::Element element2;
271
272 part = QPainterPath();
273 bool first = true;
274 for (int i = 0; i < path.elementCount(); ++i)
275 {
276 const QPainterPath::Element &elm = path.elementAt(i);
277 if ((first) && (elm.type != QPainterPath::MoveToElement))
278 part.moveTo(elm.x, elm.y);
279 switch (elm.type)
280 {
281 case QPainterPath::MoveToElement:
282 if (!first)
283 {
284 ret.append(part);
285 part = QPainterPath();
286 }
287 first = false;
288 part.moveTo(elm.x, elm.y);
289 break;
290 case QPainterPath::LineToElement:
291 part.lineTo(elm.x, elm.y);
292 break;
293 case QPainterPath::CurveToElement:
294 element1 = path.elementAt(i + 1);
295 element2 = path.elementAt(i + 2);
296 part.cubicTo(elm.x, elm.y, element1.x, element1.y, element2.x, element2.y );
297 break;
298 default:
299 break;
300 }
301 }
302 if (!part.isEmpty())
303 ret.append(part);
304 return ret;
305 }
306
projectPointOnLine(FPoint p,QPointF lineStart,QPointF lineEnd)307 FPoint projectPointOnLine(FPoint p, QPointF lineStart, QPointF lineEnd)
308 {
309 if (lineStart == lineEnd)
310 return FPoint(lineStart.x(), lineStart.y());
311
312 // move lineStart to Origin
313 p -= FPoint(lineStart.x(), lineStart.y());
314 lineEnd -= lineStart;
315 // calc dot product
316 double lineLengthSquare = lineEnd.x() * lineEnd.x() + lineEnd.y() * lineEnd.y();
317 double partOfLine = p.x() * lineEnd.x() + p.y() * lineEnd.y() / lineLengthSquare;
318 // return point on line
319 return FPoint(lineStart.x() + partOfLine * lineEnd.x(), lineStart.y() + partOfLine * lineEnd.y());
320 }
321
regionContainsRect(const QRegion & shape,QRect rect)322 bool regionContainsRect(const QRegion& shape, QRect rect)
323 {
324 /*bool oldResult = QRegion(rect).subtracted(shape).isEmpty();*/
325
326 // Code adapted from Qt RectInRegion (cf. qregion.cpp) to detect
327 // if a specific rect is stricly contained in a specific region
328 const QRect *pbox, *pboxEnd;
329 bool partIn(false), partOut(false);
330
331 QRect *prect = ▭
332 int rx = rect.left();
333 int ry = rect.top();
334
335 int rectCount = shape.rectCount();
336 QRect boundingRect = shape.boundingRect();
337 if (rectCount == 0 || !boundingRect.contains(rect))
338 return false;
339
340 /* can stop when both partOut and partIn are true, or we reach prect->y2 */
341 pbox = (rectCount == 1) ? &boundingRect : shape.cbegin();
342 pboxEnd = (rectCount == 1) ? (&boundingRect + 1) : shape.cend();
343 for (; pbox < pboxEnd; ++pbox)
344 {
345 if (pbox->bottom() < ry)
346 continue;
347
348 if (pbox->top() > ry)
349 {
350 partOut = true;
351 if (partIn || pbox->top() > prect->bottom())
352 break;
353 ry = pbox->top();
354 }
355
356 if (pbox->right() < rx)
357 continue; /* not far enough over yet */
358
359 if (pbox->left() > rx)
360 {
361 partOut = true; /* missed part of rectangle to left */
362 if (partIn)
363 break;
364 }
365
366 if (pbox->left() <= prect->right())
367 {
368 partIn = true; /* definitely overlap */
369 if (partOut)
370 break;
371 }
372
373 if (pbox->right() >= prect->right())
374 {
375 ry = pbox->bottom() + 1; /* finished with this band */
376 if (ry > prect->bottom())
377 break;
378 rx = prect->left(); /* reset x out to left again */
379 }
380 else
381 {
382 /*
383 * Because boxes in a band are maximal width, if the first box
384 * to overlap the rectangle doesn't completely cover it in that
385 * band, the rectangle must be partially out, since some of it
386 * will be uncovered in that band. partIn will have been set true
387 * by now...
388 */
389 break;
390 }
391 }
392 /*bool newResult = partIn ? ((ry <= prect->bottom()) ? false : true) : false;
393 if (oldResult != newResult)
394 int test = 0;*/
395 return partIn ? (ry > prect->bottom()) : false;
396 }
397
flattenPath(const FPointArray & ina,QList<uint> & segments)398 QPolygon flattenPath(const FPointArray& ina, QList<uint> &segments)
399 {
400 QPolygon cli;
401 QPolygon outa;
402
403 segments.clear();
404 if (ina.size() <= 3)
405 return outa;
406
407 int limit = ina.size() - 3;
408 for (int i = 0; i < limit; i += 4)
409 {
410 if (ina.isMarker(i)) // && cli.size() > 0)
411 {
412 segments.append(outa.size());
413 continue;
414 }
415 const FPoint& a1 = ina.point(i);
416 const FPoint& a2 = ina.point(i + 1);
417 const FPoint& a3 = ina.point(i + 3);
418 const FPoint& a4 = ina.point(i + 2);
419 QPainterPath bez;
420 bez.moveTo(a1.x(), a1.y());
421 bez.cubicTo(a2.x(), a2.y(), a3.x(), a3.y(), a4.x(), a4.y());
422 cli = bez.toFillPolygon().toPolygon();
423 if (cli.size() > 1)
424 outa.putPoints(outa.size(), cli.size() - 2, cli);
425 else
426 outa << QPoint(qRound(a4.x()), qRound(a4.y()));
427 }
428
429 return outa;
430 }
431
getMaxClipF(const FPointArray * clip)432 FPoint getMaxClipF(const FPointArray* clip)
433 {
434 FPoint np;
435 FPoint rp;
436 double mx = 0;
437 double my = 0;
438 int clipSize = clip->size();
439 for (int i = 0; i < clipSize; ++i)
440 {
441 np = clip->point(i);
442 if (clip->isMarker(i))
443 continue;
444 if (np.x() > mx)
445 mx = np.x();
446 if (np.y() > my)
447 my = np.y();
448 }
449 rp.setXY(mx, my);
450 return rp;
451 }
452
getMinClipF(const FPointArray * clip)453 FPoint getMinClipF(const FPointArray* clip)
454 {
455 FPoint np;
456 FPoint rp;
457 double mx = std::numeric_limits<double>::max();
458 double my = std::numeric_limits<double>::max();
459 int clipSize = clip->size();
460 for (int i = 0; i < clipSize; ++i)
461 {
462 np = clip->point(i);
463 if (clip->isMarker(i))
464 continue;
465 if (np.x() < mx)
466 mx = np.x();
467 if (np.y() < my)
468 my = np.y();
469 }
470 rp.setXY(mx, my);
471 return rp;
472 }
473
474
compareDouble(double a,double b)475 bool compareDouble(double a, double b)
476 {
477 if(a > -21473 && b > -21473 && a < 21474 && b < 21474)
478 {
479 long al = static_cast<long>(10000 * a);
480 long bl = static_cast<long>(10000 * b);
481 return al == bl;
482 }
483 return a == b;
484 }
485
486
constrainAngle(double angle,double constrain)487 double constrainAngle(double angle, double constrain)
488 {
489 double newAngle = angle;
490 double constrainTo = constrain;
491 if (newAngle < 0.0)
492 newAngle += 360.0;
493 newAngle = qRound(newAngle / constrainTo) * constrainTo;
494 if (newAngle == 360.0)
495 newAngle = 0.0;
496 return newAngle;
497 }
498
getRotationFromMatrix(QTransform & matrix,double def)499 double getRotationFromMatrix(QTransform& matrix, double def)
500 {
501 double value = def;
502 double norm = sqrt(fabs(matrix.determinant()));
503 if (norm > 0.0000001)
504 {
505 double m11 = matrix.m11() / norm;
506 double m12 = matrix.m12() / norm;
507 double m21 = matrix.m21() / norm;
508 double m22 = matrix.m22() / norm;
509 if (fabs(m11) <= 1.0 && fabs(m12) <= 1.0 && fabs(m21) <= 1.0 && fabs(m22) <= 1.0)
510 {
511 QTransform mat(m11, m12, m21, m22, 0, 0);
512 if (abs(mat.determinant()-1.0) < 0.00001 && (mat.m12() == -mat.m21()))
513 {
514 double ac = acos(mat.m11());
515 value = (mat.m21() >= 0.0) ? ac : (-ac);
516 }
517 }
518 }
519 return value;
520 }
521
getRotationDFromMatrix(QTransform & matrix)522 double getRotationDFromMatrix(QTransform& matrix)
523 {
524 QLineF line(0.0, 0.0, 1.0, 0.0);
525 line = matrix.map(line);
526 return line.angle();
527 }
528
getScaleFromMatrix(QTransform & matrix,double & scX,double & scY)529 void getScaleFromMatrix(QTransform &matrix, double &scX, double &scY)
530 {
531 QLineF lineX(0.0, 0.0, 1.0, 0.0);
532 QLineF lineY(0.0, 0.0, 0.0, 1.0);
533 lineX = matrix.map(lineX);
534 lineY = matrix.map(lineY);
535 scX = lineX.length();
536 scY = lineY.length();
537 }
538
getTransformValuesFromMatrix(QTransform & matrix,double & scX,double & scY,double & rot,double & dx,double & dy)539 void getTransformValuesFromMatrix(QTransform &matrix, double &scX, double &scY, double &rot, double &dx, double &dy)
540 {
541 QLineF lineX(0.0, 0.0, 1.0, 0.0);
542 QLineF lineY(0.0, 0.0, 0.0, 1.0);
543 lineX = matrix.map(lineX);
544 lineY = matrix.map(lineY);
545 scX = lineX.length();
546 scY = lineY.length();
547 rot = lineX.angle();
548 dx = lineX.x1();
549 dy = lineX.y1();
550 }
551