File indexing completed on 2024-05-19 04:25:03
0001 /* 0002 * SPDX-FileCopyrightText: 2014 Dmitry Kazakov <dimula73@gmail.com> 0003 * 0004 * SPDX-License-Identifier: GPL-2.0-or-later 0005 */ 0006 0007 #ifndef __KIS_ALGEBRA_2D_H 0008 #define __KIS_ALGEBRA_2D_H 0009 0010 #include <QPoint> 0011 #include <QPointF> 0012 #include <QVector> 0013 #include <QPolygonF> 0014 #include <QTransform> 0015 #include <cmath> 0016 #include <kis_global.h> 0017 #include <kritaglobal_export.h> 0018 #include <functional> 0019 #include <boost/optional.hpp> 0020 0021 class QPainterPath; 0022 class QTransform; 0023 0024 namespace KisAlgebra2D { 0025 0026 template <class T> 0027 struct PointTypeTraits 0028 { 0029 }; 0030 0031 template <> 0032 struct PointTypeTraits<QPoint> 0033 { 0034 typedef int value_type; 0035 typedef qreal calculation_type; 0036 typedef QRect rect_type; 0037 }; 0038 0039 template <> 0040 struct PointTypeTraits<QPointF> 0041 { 0042 typedef qreal value_type; 0043 typedef qreal calculation_type; 0044 typedef QRectF rect_type; 0045 }; 0046 0047 0048 template <class T> 0049 typename PointTypeTraits<T>::value_type dotProduct(const T &a, const T &b) 0050 { 0051 return a.x() * b.x() + a.y() * b.y(); 0052 } 0053 0054 template <class T> 0055 typename PointTypeTraits<T>::value_type crossProduct(const T &a, const T &b) 0056 { 0057 return a.x() * b.y() - a.y() * b.x(); 0058 } 0059 0060 template <class T> 0061 qreal norm(const T &a) 0062 { 0063 return std::sqrt(pow2(a.x()) + pow2(a.y())); 0064 } 0065 0066 template <class Point> 0067 Point normalize(const Point &a) 0068 { 0069 const qreal length = norm(a); 0070 return (1.0 / length) * a; 0071 } 0072 0073 template <typename Point> 0074 Point lerp(const Point &pt1, const Point &pt2, qreal t) 0075 { 0076 return pt1 + (pt2 - pt1) * t; 0077 } 0078 0079 /** 0080 * Usual sign() function with positive zero 0081 */ 0082 template <typename T> 0083 T signPZ(T x) { 0084 return x >= T(0) ? T(1) : T(-1); 0085 } 0086 0087 /** 0088 * Usual sign() function with zero returning zero 0089 */ 0090 template <typename T> 0091 T signZZ(T x) { 0092 return x == T(0) ? T(0) : x > T(0) ? T(1) : T(-1); 0093 } 0094 0095 /** 0096 * Copies the sign of \p y into \p x and returns the result 0097 */ 0098 template <typename T> 0099 inline T copysign(T x, T y) { 0100 T strippedX = qAbs(x); 0101 return y >= T(0) ? strippedX : -strippedX; 0102 } 0103 0104 template<class T> 0105 typename std::enable_if<std::is_integral<T>::value, T>::type 0106 divideFloor(T a, T b) 0107 { 0108 const bool a_neg = a < T(0); 0109 const bool b_neg = b < T(0); 0110 0111 if (a == T(0)) { 0112 return 0; 0113 } else if (a_neg == b_neg) { 0114 return a / b; 0115 } else { 0116 const T a_abs = qAbs(a); 0117 const T b_abs = qAbs(b); 0118 0119 return - 1 - (a_abs - T(1)) / b_abs; 0120 } 0121 } 0122 0123 template <class T> 0124 T leftUnitNormal(const T &a) 0125 { 0126 T result = a.x() != 0 ? T(-a.y() / a.x(), 1) : T(-1, 0); 0127 qreal length = norm(result); 0128 result *= (crossProduct(a, result) >= 0 ? 1 : -1) / length; 0129 0130 return -result; 0131 } 0132 0133 template <class T> 0134 T rightUnitNormal(const T &a) 0135 { 0136 return -leftUnitNormal(a); 0137 } 0138 0139 template <class T> 0140 T inwardUnitNormal(const T &a, int polygonDirection) 0141 { 0142 return polygonDirection * leftUnitNormal(a); 0143 } 0144 0145 /** 0146 * Helper function to convert a qreal to int lazily. If the 0147 * passed type is an integer, then the value is rounded. 0148 * Otherwise it is just passed forward. 0149 */ 0150 template<typename R> 0151 R lazyRound(qreal value); 0152 0153 template<> 0154 inline int lazyRound<int>(qreal value) 0155 { 0156 return qRound(value); 0157 } 0158 0159 template<> 0160 inline qreal lazyRound<qreal>(qreal value) 0161 { 0162 return value; 0163 } 0164 0165 /** 0166 * \return 1 if the polygon is counterclockwise 0167 * -1 if the polygon is clockwise 0168 * 0169 * Note: the sign is flipped because our 0y axis 0170 * is reversed 0171 */ 0172 template <class T> 0173 int polygonDirection(const QVector<T> &polygon) { 0174 0175 typename PointTypeTraits<T>::value_type doubleSum = 0; 0176 0177 const int numPoints = polygon.size(); 0178 for (int i = 1; i <= numPoints; i++) { 0179 int prev = i - 1; 0180 int next = i == numPoints ? 0 : i; 0181 0182 doubleSum += 0183 (polygon[next].x() - polygon[prev].x()) * 0184 (polygon[next].y() + polygon[prev].y()); 0185 } 0186 0187 return doubleSum >= 0 ? 1 : -1; 0188 } 0189 0190 template <typename T> 0191 bool isInRange(T x, T a, T b) { 0192 T length = qAbs(a - b); 0193 return qAbs(x - a) <= length && qAbs(x - b) <= length; 0194 } 0195 0196 void KRITAGLOBAL_EXPORT adjustIfOnPolygonBoundary(const QPolygonF &poly, int polygonDirection, QPointF *pt); 0197 0198 /** 0199 * Let \p pt, \p base1 are two vectors. \p base1 is uniformly scaled 0200 * and then rotated into \p base2 using transformation matrix S * 0201 * R. The function applies the same transformation to \pt and returns 0202 * the result. 0203 **/ 0204 QPointF KRITAGLOBAL_EXPORT transformAsBase(const QPointF &pt, const QPointF &base1, const QPointF &base2); 0205 0206 qreal KRITAGLOBAL_EXPORT angleBetweenVectors(const QPointF &v1, const QPointF &v2); 0207 0208 /** 0209 * Computes an angle indicating the direction from p1 to p2. If p1 and p2 are too close together to 0210 * compute an angle, defaultAngle is returned. 0211 */ 0212 qreal KRITAGLOBAL_EXPORT directionBetweenPoints(const QPointF &p1, const QPointF &p2, 0213 qreal defaultAngle); 0214 0215 namespace Private { 0216 inline void resetEmptyRectangle(const QPoint &pt, QRect *rc) { 0217 *rc = QRect(pt, QSize(1, 1)); 0218 } 0219 0220 inline void resetEmptyRectangle(const QPointF &pt, QRectF *rc) { 0221 static const qreal eps = 1e-10; 0222 *rc = QRectF(pt, QSizeF(eps, eps)); 0223 } 0224 } 0225 0226 template <class Point, class Rect> 0227 inline void accumulateBounds(const Point &pt, Rect *bounds) 0228 { 0229 if (bounds->isEmpty()) { 0230 Private::resetEmptyRectangle(pt, bounds); 0231 } 0232 0233 /** 0234 * `Rect::left()` is cheaper than `Rect::right()`, 0235 * so check it first 0236 */ 0237 if (pt.x() < bounds->left()) { 0238 bounds->setLeft(pt.x()); 0239 } else if (pt.x() > bounds->right()) { 0240 bounds->setRight(pt.x()); 0241 } 0242 0243 /** 0244 * `Rect::top()` is cheaper than `Rect::bottom()`, 0245 * so check it first 0246 */ 0247 if (pt.y() < bounds->top()) { 0248 bounds->setTop(pt.y()); 0249 } else if (pt.y() > bounds->bottom()) { 0250 bounds->setBottom(pt.y()); 0251 } 0252 } 0253 0254 template <class Point, class Rect> 0255 inline void accumulateBoundsNonEmpty(const Point &pt, Rect *bounds) 0256 { 0257 if (pt.x() < bounds->left()) { 0258 bounds->setLeft(pt.x()); 0259 } else if (pt.x() > bounds->right()) { 0260 bounds->setRight(pt.x()); 0261 } 0262 0263 if (pt.y() < bounds->top()) { 0264 bounds->setTop(pt.y()); 0265 } else if (pt.y() > bounds->bottom()) { 0266 bounds->setBottom(pt.y()); 0267 } 0268 } 0269 0270 template <template <class T> class Container, class Point, class Rect> 0271 inline void accumulateBounds(const Container<Point> &points, Rect *bounds) 0272 { 0273 Q_FOREACH (const Point &pt, points) { 0274 accumulateBounds(pt, bounds); 0275 } 0276 } 0277 0278 template <template <class T> class Container, class Point> 0279 inline typename PointTypeTraits<Point>::rect_type 0280 accumulateBounds(const Container<Point> &points) 0281 { 0282 typename PointTypeTraits<Point>::rect_type result; 0283 0284 Q_FOREACH (const Point &pt, points) { 0285 accumulateBounds(pt, &result); 0286 } 0287 0288 return result; 0289 } 0290 0291 template <class Point, class Rect> 0292 inline Point clampPoint(Point pt, const Rect &bounds) 0293 { 0294 if (pt.x() > bounds.right()) { 0295 pt.rx() = bounds.right(); 0296 } 0297 0298 if (pt.x() < bounds.left()) { 0299 pt.rx() = bounds.left(); 0300 } 0301 0302 if (pt.y() > bounds.bottom()) { 0303 pt.ry() = bounds.bottom(); 0304 } 0305 0306 if (pt.y() < bounds.top()) { 0307 pt.ry() = bounds.top(); 0308 } 0309 0310 return pt; 0311 } 0312 0313 template <class Size> 0314 auto maxDimension(Size size) -> decltype(size.width()) { 0315 return qMax(size.width(), size.height()); 0316 } 0317 0318 template <class Size> 0319 auto minDimension(Size size) -> decltype(size.width()) { 0320 return qMin(size.width(), size.height()); 0321 } 0322 0323 QPainterPath KRITAGLOBAL_EXPORT smallArrow(); 0324 0325 /** 0326 * Multiply width and height of \p rect by \p coeff keeping the 0327 * center of the rectangle pinned 0328 */ 0329 template <class Rect> 0330 Rect blowRect(const Rect &rect, qreal coeff) 0331 { 0332 typedef decltype(rect.x()) CoordType; 0333 0334 CoordType w = rect.width() * coeff; 0335 CoordType h = rect.height() * coeff; 0336 0337 return rect.adjusted(-w, -h, w, h); 0338 } 0339 0340 QPoint KRITAGLOBAL_EXPORT ensureInRect(QPoint pt, const QRect &bounds); 0341 QPointF KRITAGLOBAL_EXPORT ensureInRect(QPointF pt, const QRectF &bounds); 0342 0343 template <class Rect> 0344 Rect ensureRectNotSmaller(Rect rc, const decltype(Rect().size()) &size) 0345 { 0346 typedef decltype(Rect().size()) Size; 0347 typedef decltype(Rect().top()) ValueType; 0348 0349 if (rc.width() < size.width() || 0350 rc.height() < size.height()) { 0351 0352 ValueType width = qMax(rc.width(), size.width()); 0353 ValueType height = qMax(rc.height(), size.height()); 0354 0355 rc = Rect(rc.topLeft(), Size(width, height)); 0356 } 0357 0358 return rc; 0359 } 0360 0361 template <class Size> 0362 Size ensureSizeNotSmaller(const Size &size, const Size &bounds) 0363 { 0364 Size result = size; 0365 0366 const auto widthBound = qAbs(bounds.width()); 0367 auto width = result.width(); 0368 if (qAbs(width) < widthBound) { 0369 width = copysign(widthBound, width); 0370 result.setWidth(width); 0371 } 0372 0373 const auto heightBound = qAbs(bounds.height()); 0374 auto height = result.height(); 0375 if (qAbs(height) < heightBound) { 0376 height = copysign(heightBound, height); 0377 result.setHeight(height); 0378 } 0379 0380 return result; 0381 } 0382 0383 /** 0384 * Attempt to intersect a line to the area of the a rectangle. 0385 * 0386 * If the line intersects the rectangle, it will be modified to represent the intersecting line segment and true is returned. 0387 * If the line does not intersect the area, it remains unmodified and false will be returned. 0388 * If the line is fully inside the rectangle, it's considered "intersecting" so true will be returned. 0389 * 0390 * @param line line segment 0391 * @param rect area 0392 * @param extend extend the line to the edges of the rect area even if the line segment fits inside the rectangle 0393 * (so, consider the line to be a line defined by those two points, not a line segment) 0394 * @return true if successful 0395 */ 0396 bool KRITAGLOBAL_EXPORT intersectLineRect(QLineF &line, const QRect rect, bool extend); 0397 0398 /** 0399 * Attempt to intersect a line to the area of the a rectangle. 0400 * 0401 * If the line intersects the rectangle, it will be modified to represent the intersecting line segment and true is returned. 0402 * If the line does not intersect the area, it remains unmodified and false will be returned. 0403 * If the line is fully inside the rectangle, it's considered "intersecting" so true will be returned. 0404 * 0405 * extendFirst and extendSecond parameters allow one to use this function in case of unbounded lines (if both are true), 0406 * line segments (if both are false) or half-lines/rays (if one is true and another is false). 0407 * Note that which point is the "first" and which is the "second" is determined by which is the p1() and which is p2() in QLineF. 0408 * 0409 * @param line line segment 0410 * @param rect area 0411 * @param extendFirst extend the line to the edge of the rect area even if the first point of the line segment lies inside the rectangle 0412 * @param extendSecond extend the line to the edge of the rect area even if the second point of the line segment lies inside the rectangle 0413 * @return true if successful 0414 */ 0415 bool KRITAGLOBAL_EXPORT intersectLineRect(QLineF &line, const QRect rect, bool extendFirst, bool extendSecond); 0416 0417 // the same but with a convex polygon; uses Cyrus-Beck algorithm 0418 bool KRITAGLOBAL_EXPORT intersectLineConvexPolygon(QLineF &line, const QPolygonF polygon, bool extendFirst, bool extendSecond); 0419 0420 /** 0421 * Crop line to rect; if it doesn't intersect, just return an empty line (QLineF()). 0422 * 0423 * This is using intersectLineRect, but with the difference that it doesn't require the user to check the return value. 0424 * It's useful for drawing code, since it let the developer not use `if` before drawing. 0425 * 0426 * If the line intersects the rectangle, it will be modified to represent the intersecting line segment. 0427 * If the line does not intersect the area, it will return an empty one-point line. 0428 * 0429 * extendFirst and extendSecond parameters allow one to use this function in case of unbounded lines (if both are true), 0430 * line segments (if both are false) or half-lines/rays (if one is true and another is false). 0431 * Note that which point is the "first" and which is the "second" is determined by which is the p1() and which is p2() in QLineF. 0432 * 0433 * @param line line segment 0434 * @param rect area 0435 * @param extendFirst extend the line to the edge of the rect area even if the first point of the line segment lies inside the rectangle 0436 * @param extendSecond extend the line to the edge of the rect area even if the second point of the line segment lies inside the rectangle 0437 */ 0438 void KRITAGLOBAL_EXPORT cropLineToRect(QLineF &line, const QRect rect, bool extendFirst, bool extendSecond); 0439 0440 void KRITAGLOBAL_EXPORT cropLineToConvexPolygon(QLineF &line, const QPolygonF polygon, bool extendFirst, bool extendSecond); 0441 0442 0443 0444 0445 template <class Point> 0446 inline Point abs(const Point &pt) { 0447 return Point(qAbs(pt.x()), qAbs(pt.y())); 0448 } 0449 0450 template<typename T, typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr> 0451 inline T wrapValue(T value, T wrapBounds) { 0452 value %= wrapBounds; 0453 if (value < 0) { 0454 value += wrapBounds; 0455 } 0456 return value; 0457 } 0458 0459 template<typename T, typename std::enable_if<std::is_floating_point<T>::value, T>::type* = nullptr> 0460 inline T wrapValue(T value, T wrapBounds) { 0461 value = std::fmod(value, wrapBounds); 0462 if (value < 0) { 0463 value += wrapBounds; 0464 } 0465 return value; 0466 } 0467 0468 template<typename T, typename std::enable_if<std::is_same<decltype(T().x()), decltype(T().y())>::value, T>::type* = nullptr> 0469 inline T wrapValue(T value, T wrapBounds) { 0470 value.rx() = wrapValue(value.x(), wrapBounds.x()); 0471 value.ry() = wrapValue(value.y(), wrapBounds.y()); 0472 return value; 0473 } 0474 0475 template<typename T> 0476 inline T wrapValue(T value, T min, T max) { 0477 return wrapValue(value - min, max - min) + min; 0478 } 0479 0480 class RightHalfPlane { 0481 public: 0482 0483 RightHalfPlane(const QPointF &a, const QPointF &b) 0484 : m_a(a), m_p(b - a), m_norm_p_inv(1.0 / norm(m_p)) 0485 { 0486 } 0487 0488 RightHalfPlane(const QLineF &line) 0489 : RightHalfPlane(line.p1(), line.p2()) 0490 { 0491 } 0492 0493 qreal valueSq(const QPointF &pt) const { 0494 const qreal val = value(pt); 0495 return signZZ(val) * pow2(val); 0496 } 0497 0498 qreal value(const QPointF &pt) const { 0499 return crossProduct(m_p, pt - m_a) * m_norm_p_inv; 0500 } 0501 0502 int pos(const QPointF &pt) const { 0503 return signZZ(value(pt)); 0504 } 0505 0506 QLineF getLine() const { 0507 return QLineF(m_a, m_a + m_p); 0508 } 0509 0510 private: 0511 const QPointF m_a; 0512 const QPointF m_p; 0513 const qreal m_norm_p_inv; 0514 }; 0515 0516 class OuterCircle { 0517 public: 0518 0519 OuterCircle(const QPointF &c, qreal radius) 0520 : m_c(c), 0521 m_radius(radius), 0522 m_radius_sq(pow2(radius)), 0523 m_fadeCoeff(1.0 / (pow2(radius + 1.0) - m_radius_sq)) 0524 { 0525 } 0526 0527 qreal valueSq(const QPointF &pt) const { 0528 const qreal val = value(pt); 0529 0530 return signZZ(val) * pow2(val); 0531 } 0532 0533 qreal value(const QPointF &pt) const { 0534 return kisDistance(pt, m_c) - m_radius; 0535 } 0536 0537 int pos(const QPointF &pt) const { 0538 return signZZ(valueSq(pt)); 0539 } 0540 0541 qreal fadeSq(const QPointF &pt) const { 0542 const qreal valSq = kisSquareDistance(pt, m_c); 0543 return (valSq - m_radius_sq) * m_fadeCoeff; 0544 } 0545 0546 private: 0547 const QPointF m_c; 0548 const qreal m_radius; 0549 const qreal m_radius_sq; 0550 const qreal m_fadeCoeff; 0551 }; 0552 0553 QVector<QPoint> KRITAGLOBAL_EXPORT sampleRectWithPoints(const QRect &rect); 0554 QVector<QPointF> KRITAGLOBAL_EXPORT sampleRectWithPoints(const QRectF &rect); 0555 0556 QRect KRITAGLOBAL_EXPORT approximateRectFromPoints(const QVector<QPoint> &points); 0557 QRectF KRITAGLOBAL_EXPORT approximateRectFromPoints(const QVector<QPointF> &points); 0558 0559 QRect KRITAGLOBAL_EXPORT approximateRectWithPointTransform(const QRect &rect, std::function<QPointF(QPointF)> func); 0560 0561 0562 /** 0563 * Cuts off a portion of a rect \p rc defined by a half-plane \p p 0564 * \return the bounding rect of the resulting polygon 0565 */ 0566 KRITAGLOBAL_EXPORT 0567 QRectF cutOffRect(const QRectF &rc, const KisAlgebra2D::RightHalfPlane &p); 0568 0569 0570 /** 0571 * Solves a quadratic equation in a form: 0572 * 0573 * a * x^2 + b * x + c = 0 0574 * 0575 * WARNING: Please note that \p a *must* be nonzero! Otherwise the 0576 * equation is not quadratic! And this function doesn't check that! 0577 * 0578 * \return the number of solutions. It can be 0, 1 or 2. 0579 * 0580 * \p x1, \p x2 --- the found solution. The variables are filled with 0581 * data iff the corresponding solution is found. That 0582 * is: 0 solutions --- variables are not touched, 1 0583 * solution --- x1 is filled with the result, 2 0584 * solutions --- x1 and x2 are filled. 0585 */ 0586 KRITAGLOBAL_EXPORT 0587 int quadraticEquation(qreal a, qreal b, qreal c, qreal *x1, qreal *x2); 0588 0589 /** 0590 * Finds the points of intersections between two circles 0591 * \return the found circles, the result can have 0, 1 or 2 points 0592 */ 0593 KRITAGLOBAL_EXPORT 0594 QVector<QPointF> intersectTwoCircles(const QPointF &c1, qreal r1, 0595 const QPointF &c2, qreal r2); 0596 0597 KRITAGLOBAL_EXPORT 0598 QTransform mapToRect(const QRectF &rect); 0599 0600 KRITAGLOBAL_EXPORT 0601 QTransform mapToRectInverse(const QRectF &rect); 0602 0603 /** 0604 * Scale the relative point \pt into the bounds of \p rc. The point might be 0605 * outside the rectangle. 0606 */ 0607 inline QPointF relativeToAbsolute(const QPointF &pt, const QRectF &rc) { 0608 return rc.topLeft() + QPointF(pt.x() * rc.width(), pt.y() * rc.height()); 0609 } 0610 0611 /** 0612 * Get the relative position of \p pt inside rectangle \p rc. The point can be 0613 * outside the rectangle. 0614 */ 0615 inline QPointF absoluteToRelative(const QPointF &pt, const QRectF &rc) { 0616 const QPointF rel = pt - rc.topLeft(); 0617 return QPointF(rc.width() > 0 ? rel.x() / rc.width() : 0, 0618 rc.height() > 0 ? rel.y() / rc.height() : 0); 0619 0620 } 0621 0622 /** 0623 * Scales relative isotropic value from relative to absolute coordinate system 0624 * using SVG 1.1 rules (see chapter 7.10) 0625 */ 0626 inline qreal relativeToAbsolute(qreal value, const QRectF &rc) { 0627 const qreal coeff = std::sqrt(pow2(rc.width()) + pow2(rc.height())) / std::sqrt(2.0); 0628 return value * coeff; 0629 } 0630 0631 /** 0632 * Scales absolute isotropic value from absolute to relative coordinate system 0633 * using SVG 1.1 rules (see chapter 7.10) 0634 */ 0635 inline qreal absoluteToRelative(const qreal value, const QRectF &rc) { 0636 const qreal coeff = std::sqrt(pow2(rc.width()) + pow2(rc.height())) / std::sqrt(2.0); 0637 return coeff != 0 ? value / coeff : 0; 0638 } 0639 0640 /** 0641 * Scales relative isotropic value from relative to absolute coordinate system 0642 * using SVG 1.1 rules (see chapter 7.10) 0643 */ 0644 inline QRectF relativeToAbsolute(const QRectF &rel, const QRectF &rc) { 0645 return QRectF(relativeToAbsolute(rel.topLeft(), rc), relativeToAbsolute(rel.bottomRight(), rc)); 0646 } 0647 0648 /** 0649 * Scales absolute isotropic value from absolute to relative coordinate system 0650 * using SVG 1.1 rules (see chapter 7.10) 0651 */ 0652 inline QRectF absoluteToRelative(const QRectF &rel, const QRectF &rc) { 0653 return QRectF(absoluteToRelative(rel.topLeft(), rc), absoluteToRelative(rel.bottomRight(), rc)); 0654 } 0655 0656 /** 0657 * Compare the matrices with tolerance \p delta 0658 */ 0659 bool KRITAGLOBAL_EXPORT fuzzyMatrixCompare(const QTransform &t1, const QTransform &t2, qreal delta); 0660 0661 /** 0662 * Returns true if the two points are equal within some tolerance, where the tolerance is determined 0663 * by Qt's built-in fuzzy comparison functions. 0664 */ 0665 bool KRITAGLOBAL_EXPORT fuzzyPointCompare(const QPointF &p1, const QPointF &p2); 0666 0667 /** 0668 * Returns true if the two points are equal within the specified tolerance 0669 */ 0670 bool KRITAGLOBAL_EXPORT fuzzyPointCompare(const QPointF &p1, const QPointF &p2, qreal delta); 0671 0672 /** 0673 * Returns true if points in two containers are equal with specified tolerance 0674 */ 0675 template <template<typename> class Cont, class Point> 0676 bool fuzzyPointCompare(const Cont<Point> &c1, const Cont<Point> &c2, qreal delta) 0677 { 0678 if (c1.size() != c2.size()) return false; 0679 0680 const qreal eps = delta; 0681 0682 return std::mismatch(c1.cbegin(), 0683 c1.cend(), 0684 c2.cbegin(), 0685 [eps] (const QPointF &pt1, const QPointF &pt2) { 0686 return fuzzyPointCompare(pt1, pt2, eps); 0687 }) 0688 .first == c1.cend(); 0689 } 0690 0691 /** 0692 * Compare two rectangles with tolerance \p tolerance. The tolerance means that the 0693 * coordinates of top left and bottom right corners should not differ more than \p tolerance 0694 * pixels. 0695 */ 0696 template<class Rect, typename Difference = decltype(Rect::width())> 0697 bool fuzzyCompareRects(const Rect &r1, const Rect &r2, Difference tolerance) { 0698 typedef decltype(r1.topLeft()) Point; 0699 0700 const Point d1 = abs(r1.topLeft() - r2.topLeft()); 0701 const Point d2 = abs(r1.bottomRight() - r2.bottomRight()); 0702 0703 const Difference maxError = std::max({d1.x(), d1.y(), d2.x(), d2.y()}); 0704 return maxError < tolerance; 0705 } 0706 0707 struct KRITAGLOBAL_EXPORT DecomposedMatrix { 0708 DecomposedMatrix(); 0709 0710 DecomposedMatrix(const QTransform &t0); 0711 0712 inline QTransform scaleTransform() const 0713 { 0714 return QTransform::fromScale(scaleX, scaleY); 0715 } 0716 0717 inline QTransform shearTransform() const 0718 { 0719 QTransform t; 0720 t.shear(shearXY, 0); 0721 return t; 0722 } 0723 0724 inline QTransform rotateTransform() const 0725 { 0726 QTransform t; 0727 t.rotate(angle); 0728 return t; 0729 } 0730 0731 inline QTransform translateTransform() const 0732 { 0733 return QTransform::fromTranslate(dx, dy); 0734 } 0735 0736 inline QTransform projectTransform() const 0737 { 0738 return 0739 QTransform( 0740 1,0,proj[0], 0741 0,1,proj[1], 0742 0,0,proj[2]); 0743 } 0744 0745 inline QTransform transform() const { 0746 return 0747 scaleTransform() * 0748 shearTransform() * 0749 rotateTransform() * 0750 translateTransform() * 0751 projectTransform(); 0752 } 0753 0754 inline bool isValid() const { 0755 return valid; 0756 } 0757 0758 qreal scaleX = 1.0; 0759 qreal scaleY = 1.0; 0760 qreal shearXY = 0.0; 0761 qreal angle = 0.0; 0762 qreal dx = 0.0; 0763 qreal dy = 0.0; 0764 qreal proj[3] = {0.0, 0.0, 1.0}; 0765 0766 private: 0767 bool valid = true; 0768 }; 0769 0770 // NOTE: tiar: this seems to ignore perspective transformation, be wary and use the class in PerspectiveEllipseAssistant.cpp instead 0771 // this is only good for rotation, translation and possibly shear 0772 std::pair<QPointF, QTransform> KRITAGLOBAL_EXPORT transformEllipse(const QPointF &axes, const QTransform &fullLocalToGlobal); 0773 0774 QPointF KRITAGLOBAL_EXPORT alignForZoom(const QPointF &pt, qreal zoom); 0775 0776 0777 /** 0778 * Linearly reshape function \p x so that in range [x0, x1] 0779 * it would cross points (x0, y0) and (x1, y1). 0780 */ 0781 template <typename T> 0782 inline T linearReshapeFunc(T x, T x0, T x1, T y0, T y1) 0783 { 0784 return y0 + (y1 - y0) * (x - x0) / (x1 - x0); 0785 } 0786 0787 0788 /** 0789 * Find intersection of a bounded line \p boundedLine with unbounded 0790 * line \p unboundedLine (if an intersection exists) 0791 */ 0792 KRITAGLOBAL_EXPORT 0793 boost::optional<QPointF> intersectLines(const QLineF &boundedLine, const QLineF &unboundedLine); 0794 0795 0796 /** 0797 * Find intersection of a bounded line \p p1, \p p2 with unbounded 0798 * line \p q1, \p q2 (if an intersection exists) 0799 */ 0800 KRITAGLOBAL_EXPORT 0801 boost::optional<QPointF> intersectLines(const QPointF &p1, const QPointF &p2, 0802 const QPointF &q1, const QPointF &q2); 0803 0804 /** 0805 * Find possible positions for point p3, such that points \p1, \p2 and p3 form 0806 * a triangle, such that the distance between p1 ad p3 is \p a and the distance 0807 * between p2 and p3 is b. There might be 0, 1 or 2 such positions. 0808 */ 0809 QVector<QPointF> KRITAGLOBAL_EXPORT findTrianglePoint(const QPointF &p1, const QPointF &p2, qreal a, qreal b); 0810 0811 /** 0812 * Find a point p3 that forms a triangle with \p1 and \p2 and is the nearest 0813 * possible point to \p nearest 0814 * 0815 * \see findTrianglePoint 0816 */ 0817 boost::optional<QPointF> KRITAGLOBAL_EXPORT findTrianglePointNearest(const QPointF &p1, const QPointF &p2, qreal a, qreal b, const QPointF &nearest); 0818 0819 /** 0820 * @brief moveElasticPoint moves point \p pt based on the model of elasticity 0821 * @param pt point in question, tied to points \p base, \p wingA and \p wingB 0822 * using springs 0823 * @param base initial position of the dragged point 0824 * @param newBase final position of the dragged point 0825 * @param wingA first anchor point 0826 * @param wingB second anchor point 0827 * @return the new position of \p pt 0828 * 0829 * The function requires (\p newBase - \p base) be much smaller than any 0830 * of the distances between other points. If larger distances are necessary, 0831 * then use integration. 0832 */ 0833 QPointF KRITAGLOBAL_EXPORT moveElasticPoint(const QPointF &pt, 0834 const QPointF &base, const QPointF &newBase, 0835 const QPointF &wingA, const QPointF &wingB); 0836 0837 /** 0838 * @brief moveElasticPoint moves point \p pt based on the model of elasticity 0839 * @param pt point in question, tied to points \p base, \p anchorPoints 0840 * using springs 0841 * @param base initial position of the dragged point 0842 * @param newBase final position of tht dragged point 0843 * @param anchorPoints anchor points 0844 * @return the new position of \p pt 0845 * 0846 * The function expects (\p newBase - \p base) be much smaller than any 0847 * of the distances between other points. If larger distances are necessary, 0848 * then use integration. 0849 */ 0850 QPointF KRITAGLOBAL_EXPORT moveElasticPoint(const QPointF &pt, 0851 const QPointF &base, const QPointF &newBase, 0852 const QVector<QPointF> &anchorPoints); 0853 0854 0855 /** 0856 * @brief a simple class to generate Halton sequence 0857 * 0858 * This sequence of numbers can be used to sample areas 0859 * in somewhat uniform way. See Wikipedia for more info: 0860 * 0861 * https://en.wikipedia.org/wiki/Halton_sequence 0862 */ 0863 0864 class HaltonSequenceGenerator 0865 { 0866 public: 0867 HaltonSequenceGenerator(int base) 0868 : m_base(base) 0869 { 0870 } 0871 0872 int generate(int maxRange) { 0873 generationStep(); 0874 return (m_n * maxRange + m_d / 2) / m_d; 0875 } 0876 0877 qreal generate() { 0878 generationStep(); 0879 return qreal(m_n) / m_d; 0880 } 0881 0882 void step() { 0883 generationStep(); 0884 } 0885 0886 int currentValue(int maxRange) const { 0887 return (m_n * maxRange + m_d / 2) / m_d; 0888 } 0889 0890 qreal currentValue() const{ 0891 return qreal(m_n) / m_d; 0892 } 0893 0894 private: 0895 inline void generationStep() { 0896 int x = m_d - m_n; 0897 0898 if (x == 1) { 0899 m_n = 1; 0900 m_d *= m_base; 0901 } else { 0902 int y = m_d / m_base; 0903 while (x <= y) { 0904 y /= m_base; 0905 } 0906 m_n = (m_base + 1) * y - x; 0907 } 0908 } 0909 0910 private: 0911 int m_n = 0; 0912 int m_d = 1; 0913 const int m_base = 0; 0914 }; 0915 0916 0917 // find minimum of the function f(x) between points xA and xB, with eps precision, using Golden Ratio Section 0918 // requirements: only one local minimum between xA and xB 0919 // Golden Section is supposed to be usually faster than Ternary Section 0920 // NOTE: tiar: this function was debugged and should be working correctly but is not used anywhere any longer 0921 qreal findMinimumGoldenSection(std::function<qreal(qreal)> f, qreal xA, qreal xB, qreal eps, int maxIter); 0922 0923 // find minimum of the function f(x) between points xA and xB, with eps precision, using Ternary Section 0924 // requirements: only one local minimum between xA and xB 0925 // Golden Section is supposed to be usually faster than Ternary Section 0926 // NOTE: tiar: this function was debugged and should be working correctly but is not used anywhere any longer 0927 qreal findMinimumTernarySection(std::function<qreal(qreal)> f, qreal xA, qreal xB, qreal eps, int maxIter); 0928 0929 qreal KRITAGLOBAL_EXPORT pointToLineDistSquared(const QPointF& pt, const QLineF& line); 0930 0931 0932 } 0933 0934 0935 #endif /* __KIS_ALGEBRA_2D_H */