KisAlgebra2D Namespace Reference

Namespaces
namespace	Private

Classes
struct	DecomposedMatrix
class	HaltonSequenceGenerator
	a simple class to generate Halton sequence More...
class	OuterCircle
struct	PointTypeTraits
struct	PointTypeTraits< QPoint >
struct	PointTypeTraits< QPointF >
class	RightHalfPlane
class	VectorPath

Enumerations
enum	KisTransformComponent {   Translate = 0x1 , Scale = 0x2 , Rotate = 0x4 , Shear = 0x8 ,   Project = 0x10 }

Functions
template<class Point >
Point	abs (const Point &pt)
QPointF	absoluteToRelative (const QPointF &pt, const QRectF &rc)
qreal	absoluteToRelative (const qreal value, const QRectF &rc)
QRectF	absoluteToRelative (const QRectF &rel, const QRectF &rc)
template<template< class T > class Container, class Point >
PointTypeTraits< Point >::rect_type	accumulateBounds (const Container< Point > &points)
template<template< class T > class Container, class Point , class Rect >
void	accumulateBounds (const Container< Point > &points, Rect *bounds)
template<class Point , class Rect >
void	accumulateBounds (const Point &pt, Rect *bounds)
template<class Point , class Rect >
void	accumulateBoundsNonEmpty (const Point &pt, Rect *bounds)
void	adjustIfOnPolygonBoundary (const QPolygonF &poly, int polygonDirection, QPointF *pt)
QPointF	alignForZoom (const QPointF &pt, qreal zoom)
qreal	angleBetweenVectors (const QPointF &v1, const QPointF &v2)
QRect	approximateRectFromPoints (const QVector< QPoint > &points)
QRectF	approximateRectFromPoints (const QVector< QPointF > &points)
template<class Rect , class Point , bool alignPixels>
Rect	approximateRectFromPointsImpl (const QVector< Point > &points)
QRect	approximateRectWithPointTransform (const QRect &rect, std::function< QPointF(QPointF)> func)
template<class Rect >
Rect	blowRect (const Rect &rect, qreal coeff)
QPolygonF	calculateConvexHull (const QPolygonF &polygon)
	calculateConvexHull Calculate the convex hull of the polygon using the QuickHull
QPolygonF	calculateConvexHullFromPointsOverTheLine (const QPolygonF &points, const QLineF &line)
template<class Point , class Rect >
Point	clampPoint (Point pt, const Rect &bounds)
QPolygonF	combineConvexHullParts (const QPolygonF &leftPolygon, QPolygonF &rightPolygon, bool triangular)
KisTransformComponents	compareTransformComponents (const QTransform &lhs, const QTransform &rhs)
KisTransformComponents	componentsForTransform (const QTransform &t)
template<typename T >
T	copysign (T x, T y)
template<class Point >
PointTypeTraits< Point >::rect_type	createRectFromCorners (Point corner1, Point corner2)
QRectF	createRectFromCorners (QLineF line)
void	cropLineToConvexPolygon (QLineF &line, const QPolygonF polygon, bool extendFirst, bool extendSecond)
void	cropLineToRect (QLineF &line, const QRect rect, bool extendFirst, bool extendSecond)
	Crop line to rect; if it doesn't intersect, just return an empty line (QLineF()).
template<class T >
PointTypeTraits< T >::value_type	crossProduct (const T &a, const T &b)
QRectF	cutOffRect (const QRectF &rc, const KisAlgebra2D::RightHalfPlane &p)
qreal	directionBetweenPoints (const QPointF &p1, const QPointF &p2, qreal defaultAngle)
template<class T >
std::enable_if< std::is_integral< T >::value, T >::type	divideFloor (T a, T b)
template<class T >
PointTypeTraits< T >::value_type	dotProduct (const T &a, const T &b)
QPoint	ensureInRect (QPoint pt, const QRect &bounds)
QPointF	ensureInRect (QPointF pt, const QRectF &bounds)
template<class Point , class Rect >
Point	ensureInRectImpl (Point pt, const Rect &bounds)
template<class Rect >
Rect	ensureRectNotSmaller (Rect rc, const decltype(Rect().size()) &size)
template<class Size >
Size	ensureSizeNotSmaller (const Size &size, const Size &bounds)
qreal	findMinimumGoldenSection (std::function< qreal(qreal)> f, qreal xA, qreal xB, qreal eps, int maxIter=100)
qreal	findMinimumTernarySection (std::function< qreal(qreal)> f, qreal xA, qreal xB, qreal eps, int maxIter=100)
QPointF	findNearestPointOnLine (const QPointF &point, const QLineF &line, bool unbounded)
QVector< QPointF >	findTrianglePoint (const QPointF &p1, const QPointF &p2, qreal a, qreal b)
boost::optional< QPointF >	findTrianglePointNearest (const QPointF &p1, const QPointF &p2, qreal a, qreal b, const QPointF &nearest)
Eigen::Matrix3d	fromQTransformStraight (const QTransform &t)
template<class Rect , typename Difference = decltype(Rect::width())>
bool	fuzzyCompareRects (const Rect &r1, const Rect &r2, Difference tolerance)
bool	fuzzyMatrixCompare (const QTransform &t1, const QTransform &t2, qreal delta)
template<template< typename > class Cont, class Point >
bool	fuzzyPointCompare (const Cont< Point > &c1, const Cont< Point > &c2, qreal delta)
bool	fuzzyPointCompare (const QPointF &p1, const QPointF &p2)
bool	fuzzyPointCompare (const QPointF &p1, const QPointF &p2, qreal delta)
QLineF	getLineFromElements (const QPainterPath &shape, int index)
QList< int >	getLineSegmentCrossingLineIndexes (const QLineF &line, const QPainterPath &shape)
QPainterPath	getOnePathFromRectangleCutThrough (const QList< QPointF > &points, const QLineF &line, bool left)
QList< QLineF >	getParallelLines (const QLineF &line, const qreal distance)
QList< QPainterPath >	getPathsFromRectangleCutThrough (const QRectF &rect, const QLineF &leftLine, const QLineF &rightLine)
	getPathsFromRectangleCutThrough get paths defining both sides of a rectangle cut through using two (supposedly parallel) lines It is used in the Knife Tool If you just want to cut a rectangle, you can use the same line in both
QList< QLineF >	intersectLineConcavePolygon (const QPolygonF polygon, const QLineF &line, bool extendFirst, bool extendSecond)
bool	intersectLineConvexPolygon (QLineF &line, const QPolygonF polygon, bool extendFirst, bool extendSecond)
bool	intersectLineRect (QLineF &line, const QRect rect, bool extend)
bool	intersectLineRect (QLineF &line, const QRect rect, bool extendFirst, bool extendSecond)
boost::optional< QPointF >	intersectLines (const QLineF &boundedLine, const QLineF &unboundedLine)
boost::optional< QPointF >	intersectLines (const QPointF &p1, const QPointF &p2, const QPointF &q1, const QPointF &q2)
QVector< QPointF >	intersectTwoCircles (const QPointF &center1, qreal r1, const QPointF &center2, qreal r2)
template<class T >
T	inwardUnitNormal (const T &a, int polygonDirection)
template<typename T >
bool	isInRange (T x, T a, T b)
bool	isInsideShape (const QPainterPath &path, const QPointF &point)
bool	isInsideShape (const VectorPath &path, const QPointF &point)
bool	isOnLine (const QLineF &line, const QPointF &point, const qreal eps, bool boundedStart, bool boundedEnd, bool includeEnds)
template<class Polygon , typename Difference = decltype(Polygon::first())>
bool	isPolygonRect (const Polygon &poly, Difference tolerance)
template<class T >
bool	isPolygonTrulyConvex (const QVector< T > &polygon)
template<typename R >
R	lazyRound (qreal value)
template<>
int	lazyRound< int > (qreal value)
template<>
qreal	lazyRound< qreal > (qreal value)
template<class T >
T	leftUnitNormal (const T &a)
template<typename Point >
Point	lerp (const Point &pt1, const Point &pt2, qreal t)
template<typename T >
T	linearReshapeFunc (T x, T x0, T x1, T y0, T y1)
int	lineSideForPoint (const QLineF &line, const QPointF &point)
KisTransformComponents	makeFullTransformComponents ()
QTransform	mapToRect (const QRectF &rect)
QTransform	mapToRectInverse (const QRectF &rect)
template<class Size >
auto	maxDimension (Size size) -> decltype(size.width())
VectorPath	mergeShapesWithGutter (const VectorPath &shape1, const VectorPath &shape2, const VectorPath &oneEnd, const VectorPath &otherEnd, int index1, int index2, bool reverseSecondPoly, bool isSameShape)
	mergeShapesWithGutter merges two shapes with a gutter shape (defined as two paths)
template<class Size >
auto	minDimension (Size size) -> decltype(size.width())
QPointF	moveElasticPoint (const QPointF &pt, const QPointF &base, const QPointF &newBase, const QPointF &wingA, const QPointF &wingB)
	moveElasticPoint moves point pt based on the model of elasticity
QPointF	moveElasticPoint (const QPointF &pt, const QPointF &base, const QPointF &newBase, const QVector< QPointF > &anchorPoints)
	moveElasticPoint moves point pt based on the model of elasticity
QPointF	movePointAlongTheLine (const QPointF &point, const QLineF &direction, qreal distance, bool ensureOnLine)
	movePointAlongTheLine moves the point a particular distance in the specified direction
QPointF	movePointInTheDirection (const QPointF &point, const QPointF &direction, qreal distance)
	movePointAlongTheLine moves the point a particular distance in the specified direction
template<class T >
qreal	norm (const T &a)
template<class Point >
Point	normalize (const Point &a)
template<class T >
qreal	normSquared (const T &a)
QDebug	operator<< (QDebug debug, const VectorPath &path)
QDebug	operator<< (QDebug debug, const VectorPath::VectorPathPoint &point)
qreal	pointToLineDistSquared (const QPointF &pt, const QLineF &line)
template<class T >
int	polygonDirection (const QVector< T > &polygon)
	Q_DECLARE_FLAGS (KisTransformComponents, KisTransformComponent)
int	quadraticEquation (qreal a, qreal b, qreal c, qreal *x1, qreal *x2)
QPointF	relativeToAbsolute (const QPointF &pt, const QRectF &rc)
QRectF	relativeToAbsolute (const QRectF &rel, const QRectF &rc)
qreal	relativeToAbsolute (qreal value, const QRectF &rc)
QPainterPath	removeGutterOneEndSmart (const QPainterPath &shape1, int index1, const QPainterPath &shape2, int index2, QLineF middleLine, bool reverseFirstPoly, bool reverseSecondPoly)
QPainterPath	removeGutterSmart (const QPainterPath &shape1, int index1, const QPainterPath &shape2, int index2, bool isSameShape)
	removeGutterSmart
QLineF	reverseDirection (const QLineF &line)
template<class T >
T	rightUnitNormal (const T &a)
QVector< QPoint >	sampleRectWithPoints (const QRect &rect)
QVector< QPointF >	sampleRectWithPoints (const QRectF &rect)
template<class Rect , class Point >
QVector< Point >	sampleRectWithPoints (const Rect &rect)
template<typename T >
T	signPZ (T x)
template<typename T >
T	signZZ (T x)
QPainterPath	simplifyShape (const QPainterPath &path)
QPainterPath	smallArrow ()
QTransform	toQTransformStraight (const Eigen::Matrix3d &m)
QPointF	transformAsBase (const QPointF &pt, const QPointF &base1, const QPointF &base2)
std::pair< QPointF, QTransform >	transformEllipse (const QPointF &axes, const QTransform &fullLocalToGlobal)
bool	tryMergePoints (QPainterPath &path, const QPointF &startPoint, const QPointF &endPoint, qreal &distance, qreal distanceThreshold, bool lastSegment)
QPainterPath	trySimplifyPath (const QPainterPath &path, qreal lengthThreshold)
	trySimplifyPath Tries to simplify a QPainterPath
template<typename T >
T	wrapValue (T value, T min, T max)
template<typename T , typename std::enable_if< std::is_integral< T >::value, T >::type * = nullptr>
T	wrapValue (T value, T wrapBounds)

Enumeration Type Documentation

KisTransformComponent

enum KisAlgebra2D::KisTransformComponent

Enumerator
Translate
Scale
Rotate
Shear
Project

Definition at line 15 of file KisTransformComponents.h.

{
    Translate = 0x1,
    Scale = 0x2,
    Rotate = 0x4,
    Shear = 0x8,
    Project = 0x10
};

Function Documentation

abs()

template<class Point >

Point KisAlgebra2D::abs ( const Point & pt )

inline

Definition at line 477 of file kis_algebra_2d.h.

                                  {
    return Point(qAbs(pt.x()), qAbs(pt.y()));
}

absoluteToRelative() [1/3]

QPointF KisAlgebra2D::absoluteToRelative ( const QPointF & pt, const QRectF & rc )

inline

Get the relative position of pt inside rectangle rc. The point can be outside the rectangle.

Definition at line 760 of file kis_algebra_2d.h.

                                                                       {
    const QPointF rel = pt - rc.topLeft();
    return QPointF(rc.width() > 0 ? rel.x() / rc.width() : 0,
                   rc.height() > 0 ? rel.y() / rc.height() : 0);
 
}

absoluteToRelative() [2/3]

qreal KisAlgebra2D::absoluteToRelative ( const qreal value, const QRectF & rc )

inline

Scales absolute isotropic value from absolute to relative coordinate system using SVG 1.1 rules (see chapter 7.10)

Definition at line 780 of file kis_algebra_2d.h.

                                                                     {
    const qreal coeff = std::sqrt(pow2(rc.width()) + pow2(rc.height())) / std::sqrt(2.0);
    return coeff != 0 ? value / coeff : 0;
}

References pow2(), and value().

absoluteToRelative() [3/3]

QRectF KisAlgebra2D::absoluteToRelative ( const QRectF & rel, const QRectF & rc )

inline

Scales absolute isotropic value from absolute to relative coordinate system using SVG 1.1 rules (see chapter 7.10)

Definition at line 797 of file kis_algebra_2d.h.

                                                                      {
    return QRectF(absoluteToRelative(rel.topLeft(), rc), absoluteToRelative(rel.bottomRight(), rc));
}

References absoluteToRelative().

accumulateBounds() [1/3]

template<template< class T > class Container, class Point >

PointTypeTraits< Point >::rect_type KisAlgebra2D::accumulateBounds ( const Container< Point > & points )

inline

Definition at line 288 of file kis_algebra_2d.h.

{
    typename PointTypeTraits<Point>::rect_type result;
 
    Q_FOREACH (const Point &pt, points) {
        accumulateBounds(pt, &result);
    }
 
    return result;
}

References accumulateBounds().

accumulateBounds() [2/3]

template<template< class T > class Container, class Point , class Rect >

void KisAlgebra2D::accumulateBounds ( const Container< Point > & points, Rect * bounds )

inline

Definition at line 279 of file kis_algebra_2d.h.

{
    Q_FOREACH (const Point &pt, points) {
        accumulateBounds(pt, bounds);
    }
}

References accumulateBounds(), and bounds.

accumulateBounds() [3/3]

template<class Point , class Rect >

void KisAlgebra2D::accumulateBounds ( const Point & pt, Rect * bounds )

inline

Rect::left() is cheaper than Rect::right(), so check it first

Rect::top() is cheaper than Rect::bottom(), so check it first

Definition at line 235 of file kis_algebra_2d.h.

{
    if (bounds->isEmpty()) {
        Private::resetEmptyRectangle(pt, bounds);
    }
 
    if (pt.x() < bounds->left()) {
        bounds->setLeft(pt.x());
    } else if (pt.x() > bounds->right()) {
        bounds->setRight(pt.x());
    }
 
    if (pt.y() < bounds->top()) {
        bounds->setTop(pt.y());
    } else if (pt.y() > bounds->bottom()) {
        bounds->setBottom(pt.y());
    }
}

References bounds, and KisAlgebra2D::Private::resetEmptyRectangle().

accumulateBoundsNonEmpty()

template<class Point , class Rect >

void KisAlgebra2D::accumulateBoundsNonEmpty ( const Point & pt, Rect * bounds )

inline

Definition at line 263 of file kis_algebra_2d.h.

{
    if (pt.x() < bounds->left()) {
        bounds->setLeft(pt.x());
    } else if (pt.x() > bounds->right()) {
        bounds->setRight(pt.x());
    }
 
    if (pt.y() < bounds->top()) {
        bounds->setTop(pt.y());
    } else if (pt.y() > bounds->bottom()) {
        bounds->setBottom(pt.y());
    }
}

References bounds.

adjustIfOnPolygonBoundary()

void KRITAGLOBAL_EXPORT KisAlgebra2D::adjustIfOnPolygonBoundary	(	const QPolygonF &	poly,
		int	polygonDirection,
		QPointF *	pt )

Definition at line 37 of file kis_algebra_2d.cpp.

{
    const int numPoints = poly.size();
    for (int i = 0; i < numPoints; i++) {
        int nextI = i + 1;
        if (nextI >= numPoints) {
            nextI = 0;
        }
 
        const QPointF &p0 = poly[i];
        const QPointF &p1 = poly[nextI];
 
        QPointF edge = p1 - p0;
 
        qreal cross = crossProduct(edge, *pt - p0)
            / (0.5 * edge.manhattanLength());
 
        if (cross < 1.0 &&
            isInRange(pt->x(), p0.x(), p1.x()) &&
            isInRange(pt->y(), p0.y(), p1.y())) {
 
            QPointF salt = 1.0e-3 * inwardUnitNormal(edge, polygonDirection);
 
            QPointF adjustedPoint = *pt + salt;
 
            // in case the polygon is self-intersecting, polygon direction
            // might not help
            if (kisDistanceToLine(adjustedPoint, QLineF(p0, p1)) < 1e-4) {
                adjustedPoint = *pt - salt;
 
#ifdef SANITY_CHECKS
                if (kisDistanceToLine(adjustedPoint, QLineF(p0, p1)) < 1e-4) {
                    dbgKrita << ppVar(*pt);
                    dbgKrita << ppVar(adjustedPoint);
                    dbgKrita << ppVar(QLineF(p0, p1));
                    dbgKrita << ppVar(salt);
 
                    dbgKrita << ppVar(poly.containsPoint(*pt, Qt::OddEvenFill));
 
                    dbgKrita << ppVar(kisDistanceToLine(*pt, QLineF(p0, p1)));
                    dbgKrita << ppVar(kisDistanceToLine(adjustedPoint, QLineF(p0, p1)));
                }
 
                *pt = adjustedPoint;
 
                KIS_ASSERT_RECOVER_NOOP(kisDistanceToLine(*pt, QLineF(p0, p1)) > 1e-4);
#endif /* SANITY_CHECKS */
            }
        }
    }
}

References crossProduct(), dbgKrita, inwardUnitNormal(), isInRange(), KIS_ASSERT_RECOVER_NOOP, kisDistanceToLine(), p0, p1, polygonDirection(), ppVar, and salt.

alignForZoom()

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::alignForZoom	(	const QPointF &	pt,
		qreal	zoom )

Definition at line 970 of file kis_algebra_2d.cpp.

{
    return QPointF((pt * zoom).toPoint()) / zoom;
}

angleBetweenVectors()

qreal KRITAGLOBAL_EXPORT KisAlgebra2D::angleBetweenVectors	(	const QPointF &	v1,
		const QPointF &	v2 )

Definition at line 111 of file kis_algebra_2d.cpp.

{
    qreal a1 = std::atan2(v1.y(), v1.x());
    qreal a2 = std::atan2(v2.y(), v2.x());
 
    return a2 - a1;
}

approximateRectFromPoints() [1/2]

QRect KRITAGLOBAL_EXPORT KisAlgebra2D::approximateRectFromPoints

(

const QVector< QPoint > &

points

)

Definition at line 545 of file kis_algebra_2d.cpp.

    {
        return approximateRectFromPointsImpl<QRect, QPoint, true>(points);
    }

approximateRectFromPoints() [2/2]

QRectF KRITAGLOBAL_EXPORT KisAlgebra2D::approximateRectFromPoints

(

const QVector< QPointF > &

points

)

Definition at line 550 of file kis_algebra_2d.cpp.

    {
        return approximateRectFromPointsImpl<QRectF, QPointF, false>(points);
    }

approximateRectFromPointsImpl()

template<class Rect , class Point , bool alignPixels>

Rect KisAlgebra2D::approximateRectFromPointsImpl

(

const QVector< Point > &

points

)

Definition at line 521 of file kis_algebra_2d.cpp.

    {
        using namespace boost::accumulators;
        accumulator_set<qreal, stats<tag::min, tag::max > > accX;
        accumulator_set<qreal, stats<tag::min, tag::max > > accY;
 
        Q_FOREACH (const Point &pt, points) {
            accX(pt.x());
            accY(pt.y());
        }
 
        Rect resultRect;
 
        if (alignPixels) {
            resultRect.setCoords(std::floor(min(accX)), std::floor(min(accY)),
                                 std::ceil(max(accX)), std::ceil(max(accY)));
        } else {
            resultRect.setCoords(min(accX), min(accY),
                                 max(accX), max(accY));
        }
 
        return resultRect;
    }

approximateRectWithPointTransform()

QRect KRITAGLOBAL_EXPORT KisAlgebra2D::approximateRectWithPointTransform	(	const QRect &	rect,
		std::function< QPointF(QPointF)>	func )

Definition at line 555 of file kis_algebra_2d.cpp.

    {
        QVector<QPoint> points = sampleRectWithPoints(rect);
 
        using namespace boost::accumulators;
        accumulator_set<qreal, stats<tag::min, tag::max > > accX;
        accumulator_set<qreal, stats<tag::min, tag::max > > accY;
 
        Q_FOREACH (const QPoint &pt, points) {
            QPointF dstPt = func(pt);
 
            accX(dstPt.x());
            accY(dstPt.y());
        }
 
        QRect resultRect;
        resultRect.setCoords(std::floor(min(accX)), std::floor(min(accY)),
                             std::ceil(max(accX)), std::ceil(max(accY)));
 
        return resultRect;
    }

References sampleRectWithPoints().

blowRect()

template<class Rect >

Rect KisAlgebra2D::blowRect	(	const Rect &	rect,
		qreal	coeff )

Multiply width and height of rect by coeff keeping the center of the rectangle pinned

Definition at line 354 of file kis_algebra_2d.h.

{
    typedef decltype(rect.x()) CoordType;
 
    CoordType w = rect.width() * coeff;
    CoordType h = rect.height() * coeff;
 
    return rect.adjusted(-w, -h, w, h);
}

calculateConvexHull()

QPolygonF KRITAGLOBAL_EXPORT KisAlgebra2D::calculateConvexHull

(

const QPolygonF &

polygon

)

calculateConvexHull Calculate the convex hull of the polygon using the QuickHull

Parameters

polygon

to find the convex hull of

Returns

Definition at line 1412 of file kis_algebra_2d.cpp.

{
    if (polygon.count() < 4) {
        return polygon;
    }
    QPointF leftPoint = polygon[0];
    QPointF rightPoint = polygon[1];
    if (leftPoint.x() > rightPoint.x()) { // swap them around
        leftPoint = polygon[1];
        rightPoint = polygon[0];
    }
 
    Q_FOREACH(QPointF point, polygon) {
        if (point.x() < leftPoint.x()) {
            leftPoint = point;
        } else if (point.x() > rightPoint.x()) {
            rightPoint = point;
        }
    }
    QLineF line(leftPoint, rightPoint);
    QLineF lineOther(rightPoint, leftPoint);
    QPolygonF left;
    QPolygonF right;
 
    Q_FOREACH(QPointF point, polygon) {
        qCritical() << "Checking point " << point << "and line" << line << ": " << lineSideForPoint(line, point);
        if (lineSideForPoint(line, point) > 0) {
            left << point;
        } else if (lineSideForPoint(line, point) < 0) {
            right << point;
        }
    }
 
    qCritical() << "Using line: " << line << "for points: " << left;
    qCritical() << "Using line: " << lineOther << "for points: " << right;
 
    left = calculateConvexHullFromPointsOverTheLine(left, line);
    right = calculateConvexHullFromPointsOverTheLine(right, lineOther);
 
    qCritical() << "Then the result: " << left << right;
 
    QPolygonF result = combineConvexHullParts(left, right, false);
 
    return result;
 
}

References calculateConvexHullFromPointsOverTheLine(), combineConvexHullParts(), and lineSideForPoint().

calculateConvexHullFromPointsOverTheLine()

QPolygonF KisAlgebra2D::calculateConvexHullFromPointsOverTheLine	(	const QPolygonF &	points,
		const QLineF &	line )

Definition at line 1356 of file kis_algebra_2d.cpp.

{
    // all the points should be on the correct side already, no need to check it
    if (points.count() < 1) {
        QPolygonF result;
        result << line.p1() << line.p2() << line.p1();
        return result;
    }
    if (points.count() == 1) {
        QList<QPointF> list = points.toList();
 
        QPolygonF result;
        result << line.p1();
        result << list[0];
        result << line.p2();
        result << line.p1();
 
        return result;
    }
 
    double maxDistance = 0;
    QPointF nextPoint = points[0];
    Q_FOREACH(QPointF point, points) {
        double distance = kisSquareDistanceToLine(point, line);
        if (distance > maxDistance) {
            maxDistance = distance;
            nextPoint = point;
        }
    }
 
    QPolygonF left;
    QLineF lineForLeft = QLineF(line.p1(), nextPoint);
    QPolygonF right;
    QLineF lineForRight = QLineF(nextPoint, line.p2());
    QPolygonF triangle;
    triangle << line.p1() << line.p2() << nextPoint << line.p1();
    Q_FOREACH(QPointF point, points) {
        if (triangle.containsPoint(point, Qt::WindingFill)) {
            continue;
        }
        if (lineSideForPoint(lineForLeft, point) > 0) {
            left << point;
        } else if (lineSideForPoint(lineForRight, point) < 0) {
            right << point;
        }
    }
 
    QPolygonF leftPolygon = calculateConvexHullFromPointsOverTheLine(left, lineForLeft);
    QPolygonF rightPolygon = calculateConvexHullFromPointsOverTheLine(right, lineForRight);
 
    QPolygonF result = combineConvexHullParts(leftPolygon, rightPolygon, true);
 
    return result;
}

References calculateConvexHullFromPointsOverTheLine(), combineConvexHullParts(), distance(), kisSquareDistanceToLine(), and lineSideForPoint().

clampPoint()

template<class Point , class Rect >

Point KisAlgebra2D::clampPoint ( Point pt, const Rect & bounds )

inline

Definition at line 300 of file kis_algebra_2d.h.

{
    if (pt.x() > bounds.right()) {
        pt.rx() = bounds.right();
    }
 
    if (pt.x() < bounds.left()) {
        pt.rx() = bounds.left();
    }
 
    if (pt.y() > bounds.bottom()) {
        pt.ry() = bounds.bottom();
    }
 
    if (pt.y() < bounds.top()) {
        pt.ry() = bounds.top();
    }
 
    return pt;
}

References bounds.

combineConvexHullParts()

QPolygonF KisAlgebra2D::combineConvexHullParts	(	const QPolygonF &	leftPolygon,
		QPolygonF &	rightPolygon,
		bool	triangular )

Definition at line 1327 of file kis_algebra_2d.cpp.

                                                                                                         {
    // resulting polygon should start at p1, go through all the points, go to p2, then to p1 again
    // triangular: whether the last point of right is equal to the first point in left or not
 
    QPolygonF left = leftPolygon;
    QPolygonF right = rightPolygon;
 
    left.removeLast(); // remove p1 from the end (but not the beginning)
    left.removeLast(); // remove nextPoint as well, since it's present in rightPolygon (twice)
 
    right.removeLast(); // remove nextPoint from the end (but not the beginning)
 
 
    QPolygonF result;
    Q_FOREACH(QPointF point, left) {
        result << point;
    }
 
    Q_FOREACH(QPointF point, right) {
        result << point;
    }
 
    if (triangular) {
        result << left[0];
    }
 
    return result;
}

compareTransformComponents()

KisTransformComponents KRITAGLOBAL_EXPORT KisAlgebra2D::compareTransformComponents	(	const QTransform &	lhs,
		const QTransform &	rhs )

Definition at line 43 of file KisTransformComponents.cpp.

{
    KisAlgebra2D::DecomposedMatrix m1(lhs);
    KisAlgebra2D::DecomposedMatrix m2(rhs);
 
    KisTransformComponents result;
 
    if (qFuzzyCompare(m1.dx, m2.dx) && qFuzzyCompare(m1.dy, m2.dy)) {
        result.setFlag(KisTransformComponent::Translate);
    }
 
    if (qFuzzyCompare(m1.scaleX, m2.scaleX) && qFuzzyCompare(m1.scaleX, m2.scaleY)) {
        result.setFlag(KisTransformComponent::Scale);
    }
 
    if (qFuzzyCompare(m1.shearXY, m2.shearXY)) {
        result.setFlag(KisTransformComponent::Shear);
    }
 
    if (qFuzzyCompare(m1.angle, m2.angle)) {
        result.setFlag(KisTransformComponent::Rotate);
    }
 
    if (qFuzzyCompare(m1.proj[0], m2.proj[0]) &&
        qFuzzyCompare(m1.proj[1], m2.proj[1]) &&
        qFuzzyCompare(m1.proj[2], m2.proj[2])) {
 
        result.setFlag(KisTransformComponent::Project);
    }
 
    return result;
}

References KisAlgebra2D::DecomposedMatrix::angle, KisAlgebra2D::DecomposedMatrix::dx, KisAlgebra2D::DecomposedMatrix::dy, KisAlgebra2D::DecomposedMatrix::proj, Project, qFuzzyCompare(), Rotate, Scale, KisAlgebra2D::DecomposedMatrix::scaleX, KisAlgebra2D::DecomposedMatrix::scaleY, Shear, KisAlgebra2D::DecomposedMatrix::shearXY, and Translate.

componentsForTransform()

KisTransformComponents KRITAGLOBAL_EXPORT KisAlgebra2D::componentsForTransform

(

const QTransform &

t

)

Definition at line 19 of file KisTransformComponents.cpp.

{
    KisTransformComponents result;
 
    KisAlgebra2D::DecomposedMatrix m(t);
 
    result.setFlag(KisTransformComponent::Translate,
        !qFuzzyIsNull(m.dx) || !qFuzzyIsNull(m.dy));
 
    result.setFlag(KisTransformComponent::Scale,
        !qFuzzyCompare(m.scaleX, 1.0) || !qFuzzyCompare(m.scaleY, 1.0));
 
    result.setFlag(KisTransformComponent::Shear,
        !qFuzzyIsNull(m.shearXY));
 
    result.setFlag(KisTransformComponent::Rotate,
        !qFuzzyIsNull(m.angle));
 
    result.setFlag(KisTransformComponent::Project,
        !qFuzzyIsNull(m.proj[0]) || !qFuzzyIsNull(m.proj[1]) || !qFuzzyCompare(m.proj[2], 1.0));
 
    return result;
}

References KisAlgebra2D::DecomposedMatrix::angle, KisAlgebra2D::DecomposedMatrix::dx, KisAlgebra2D::DecomposedMatrix::dy, KisAlgebra2D::DecomposedMatrix::proj, Project, qFuzzyCompare(), qFuzzyIsNull(), Rotate, Scale, KisAlgebra2D::DecomposedMatrix::scaleX, KisAlgebra2D::DecomposedMatrix::scaleY, Shear, KisAlgebra2D::DecomposedMatrix::shearXY, and Translate.

copysign()

template<typename T >

T KisAlgebra2D::copysign ( T x, T y )

inline

Copies the sign of y into x and returns the result

Definition at line 107 of file kis_algebra_2d.h.

                                {
    T strippedX = qAbs(x);
    return y >= T(0) ? strippedX : -strippedX;
}

createRectFromCorners() [1/2]

template<class Point >

PointTypeTraits< Point >::rect_type KisAlgebra2D::createRectFromCorners ( Point corner1, Point corner2 )

inline

Definition at line 323 of file kis_algebra_2d.h.

{
    return typename PointTypeTraits<Point>::rect_type(qMin(corner1.x(), corner2.x()), qMin(corner1.y(), corner2.y()), qAbs(corner1.x() - corner2.x()), qAbs(corner1.y() - corner2.y()));
}

createRectFromCorners() [2/2]

QRectF KisAlgebra2D::createRectFromCorners ( QLineF line )

inline

Definition at line 328 of file kis_algebra_2d.h.

{
    QPointF a = line.p1();
    QPointF b = line.p2();
    return createRectFromCorners(a, b);
}

References createRectFromCorners().

cropLineToConvexPolygon()

void KRITAGLOBAL_EXPORT KisAlgebra2D::cropLineToConvexPolygon	(	QLineF &	line,
		const QPolygonF	polygon,
		bool	extendFirst,
		bool	extendSecond )

Definition at line 1300 of file kis_algebra_2d.cpp.

{
    bool intersects = intersectLineConvexPolygon(line, polygon, extendFirst, extendSecond);
    if (!intersects) {
        line = QLineF(); // empty line to help with drawing
    }
}

References intersectLineConvexPolygon().

cropLineToRect()

void KRITAGLOBAL_EXPORT KisAlgebra2D::cropLineToRect	(	QLineF &	line,
		const QRect	rect,
		bool	extendFirst,
		bool	extendSecond )

Crop line to rect; if it doesn't intersect, just return an empty line (QLineF()).

This is using intersectLineRect, but with the difference that it doesn't require the user to check the return value. It's useful for drawing code, since it let the developer not use if before drawing.

If the line intersects the rectangle, it will be modified to represent the intersecting line segment. If the line does not intersect the area, it will return an empty one-point line.

extendFirst and extendSecond parameters allow one to use this function in case of unbounded lines (if both are true), line segments (if both are false) or half-lines/rays (if one is true and another is false). 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.

Parameters

line	line segment
rect	area
extendFirst	extend the line to the edge of the rect area even if the first point of the line segment lies inside the rectangle
extendSecond	extend the line to the edge of the rect area even if the second point of the line segment lies inside the rectangle

Definition at line 1292 of file kis_algebra_2d.cpp.

{
    bool intersects = intersectLineRect(line, rect, extendFirst, extendSecond);
    if (!intersects) {
        line = QLineF(); // empty line to help with drawing
    }
}

References intersectLineRect().

crossProduct()

template<class T >

PointTypeTraits< T >::value_type KisAlgebra2D::crossProduct	(	const T &	a,
		const T &	b )

Definition at line 57 of file kis_algebra_2d.h.

{
    return a.x() * b.y() - a.y() * b.x();
}

cutOffRect()

KRITAGLOBAL_EXPORT QRectF KisAlgebra2D::cutOffRect	(	const QRectF &	rc,
		const KisAlgebra2D::RightHalfPlane &	p )

Cuts off a portion of a rect rc defined by a half-plane p

Returns

the bounding rect of the resulting polygon

Definition at line 578 of file kis_algebra_2d.cpp.

{
    QVector<QPointF> points;
 
    const QLineF cutLine = p.getLine();
 
    points << rc.topLeft();
    points << rc.topRight();
    points << rc.bottomRight();
    points << rc.bottomLeft();
 
    QPointF p1 = points[3];
    bool p1Valid = p.pos(p1) >= 0;
 
    QVector<QPointF> resultPoints;
 
    for (int i = 0; i < 4; i++) {
        const QPointF p2 = points[i];
        const bool p2Valid = p.pos(p2) >= 0;
 
        if (p1Valid != p2Valid) {
            QPointF intersection;
            cutLine.intersects(QLineF(p1, p2), &intersection);
            resultPoints << intersection;
        }
 
        if (p2Valid) {
            resultPoints << p2;
        }
 
        p1 = p2;
        p1Valid = p2Valid;
    }
 
    return approximateRectFromPoints(resultPoints);
}

References approximateRectFromPoints(), p, p1, and p2.

directionBetweenPoints()

qreal KRITAGLOBAL_EXPORT KisAlgebra2D::directionBetweenPoints	(	const QPointF &	p1,
		const QPointF &	p2,
		qreal	defaultAngle )

Computes an angle indicating the direction from p1 to p2. If p1 and p2 are too close together to compute an angle, defaultAngle is returned.

Definition at line 119 of file kis_algebra_2d.cpp.

{
    if (fuzzyPointCompare(p1, p2)) {
        return defaultAngle;
    }
 
    const QVector2D diff(p2 - p1);
    return std::atan2(diff.y(), diff.x());
}

References fuzzyPointCompare(), p1, and p2.

divideFloor()

template<class T >

std::enable_if< std::is_integral< T >::value, T >::type KisAlgebra2D::divideFloor	(	T	a,
		T	b )

Definition at line 114 of file kis_algebra_2d.h.

{
    const bool a_neg = a < T(0);
    const bool b_neg = b < T(0);
 
    if (a == T(0)) {
        return 0;
    } else if (a_neg == b_neg) {
        return a / b;
    } else {
        const T a_abs = qAbs(a);
        const T b_abs = qAbs(b);
 
        return - 1 - (a_abs - T(1)) / b_abs;
    }
}

dotProduct()

template<class T >

PointTypeTraits< T >::value_type KisAlgebra2D::dotProduct	(	const T &	a,
		const T &	b )

Definition at line 51 of file kis_algebra_2d.h.

{
    return a.x() * b.x() + a.y() * b.y();
}

ensureInRect() [1/2]

QPoint KRITAGLOBAL_EXPORT KisAlgebra2D::ensureInRect	(	QPoint	pt,
		const QRect &	bounds )

Definition at line 163 of file kis_algebra_2d.cpp.

{
    return ensureInRectImpl(pt, bounds);
}

References bounds, and ensureInRectImpl().

ensureInRect() [2/2]

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::ensureInRect	(	QPointF	pt,
		const QRectF &	bounds )

Definition at line 168 of file kis_algebra_2d.cpp.

{
    return ensureInRectImpl(pt, bounds);
}

References bounds, and ensureInRectImpl().

ensureInRectImpl()

template<class Point , class Rect >

Point KisAlgebra2D::ensureInRectImpl ( Point pt, const Rect & bounds )

inline

Definition at line 146 of file kis_algebra_2d.cpp.

{
    if (pt.x() > bounds.right()) {
        pt.rx() = bounds.right();
    } else if (pt.x() < bounds.left()) {
        pt.rx() = bounds.left();
    }
 
    if (pt.y() > bounds.bottom()) {
        pt.ry() = bounds.bottom();
    } else if (pt.y() < bounds.top()) {
        pt.ry() = bounds.top();
    }
 
    return pt;
}

References bounds.

ensureRectNotSmaller()

template<class Rect >

Rect KisAlgebra2D::ensureRectNotSmaller	(	Rect	rc,
		const decltype(Rect().size()) &	size )

Definition at line 368 of file kis_algebra_2d.h.

{
    typedef decltype(Rect().size()) Size;
    typedef decltype(Rect().top()) ValueType;
 
    if (rc.width() < size.width() ||
        rc.height() < size.height()) {
 
        ValueType width = qMax(rc.width(), size.width());
        ValueType  height = qMax(rc.height(), size.height());
 
        rc = Rect(rc.topLeft(), Size(width, height));
    }
 
    return rc;
}

ensureSizeNotSmaller()

template<class Size >

Size KisAlgebra2D::ensureSizeNotSmaller	(	const Size &	size,
		const Size &	bounds )

Definition at line 386 of file kis_algebra_2d.h.

{
    Size result = size;
 
    const auto widthBound = qAbs(bounds.width());
    auto width = result.width();
    if (qAbs(width) < widthBound) {
        width = copysign(widthBound, width);
        result.setWidth(width);
    }
 
    const auto heightBound = qAbs(bounds.height());
    auto height = result.height();
    if (qAbs(height) < heightBound) {
        height = copysign(heightBound, height);
        result.setHeight(height);
    }
 
    return result;
}

References bounds, and copysign().

findMinimumGoldenSection()

qreal KRITAGLOBAL_EXPORT KisAlgebra2D::findMinimumGoldenSection	(	std::function< qreal(qreal)>	f,
		qreal	xA,
		qreal	xB,
		qreal	eps,
		int	maxIter = 100 )

Definition at line 1484 of file kis_algebra_2d.cpp.

{
    // requirements:
    // only one local minimum between xA and xB
 
    int i = 0;
    const double phi = 0.618033988749894; // 1/(golden ratio)
    qreal a = xA;
    qreal b = xB;
    qreal c = b - (b - a)*phi;
    qreal d = a + (b - a)*phi;
 
    while (qAbs(b - a) > eps) {
        if (f(c) < f(d)) {
            b = d;
        } else {
            a = c;
        }
 
        // Wikipedia says to recompute both c and d here to avoid loss of precision which may lead to incorrect results or infinite loop
        c = b - (b - a) * phi;
        d = a + (b - a) * phi;
 
        i++;
        if (i > maxIter) {
            break;
        }
 
    }
 
    return (b + a)/2;
}

References eps.

findMinimumTernarySection()

qreal KRITAGLOBAL_EXPORT KisAlgebra2D::findMinimumTernarySection	(	std::function< qreal(qreal)>	f,
		qreal	xA,
		qreal	xB,
		qreal	eps,
		int	maxIter = 100 )

Definition at line 1517 of file kis_algebra_2d.cpp.

{
    // requirements:
    // only one local minimum between xA and xB
 
    int i = 0;
    qreal l = qMin(xA, xB);
    qreal r = qMax(xA, xB);
 
 
    qreal m1 = l + (r - l)/3;
    qreal m2 = r - (r - l)/3;
 
    while ((r - l) > eps) {
        qreal f1 = f(m1);
        qreal f2 = f(m2);
 
        if (f1 > f2) {
            l = m1;
        } else {
            r = m2;
        }
 
        // In Golden Section, Wikipedia says to recompute both c and d here to avoid loss of precision which may lead to incorrect results or infinite loop
        // so it's probably a good idea to do it here too
        m1 = l + (r - l)/3;
        m2 = r - (r - l)/3;
 
        i++;
 
        if (i > maxIter) {
            break;
        }
    }
 
    return (l + r)/2;
}

References eps.

findNearestPointOnLine()

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::findNearestPointOnLine	(	const QPointF &	point,
		const QLineF &	line,
		bool	unbounded )

Definition at line 1755 of file kis_algebra_2d.cpp.

{
    // TODO: can we reuse (or deduplicate with) KisBezierUtils.cpp:nearestPoint()?
 
    if (line.length() == 0) {
        return point;
    }
 
    QPointF lineVector = line.p2() - line.p1();
    QPointF lineNormalVector = QPointF(-lineVector.y(), lineVector.x());
 
    QLineF pointToLineNormalLine = QLineF(point, point + lineNormalVector);
    QPointF result;
    QLineF::IntersectionType intersectionType = pointToLineNormalLine.intersects(line, &result);
    if (unbounded || intersectionType == QLineF::IntersectionType::BoundedIntersection) {
        return result;
    }
    qreal distance1 = kisDistance(line.p1(), result);
    qreal distance2 = kisDistance(line.p2(), result);
    if (distance1 + distance2 <= line.length() || qFuzzyCompare(distance1 + distance2, line.length())) {
        return result; // it's still on the line
    }
    if (distance1 < distance2) {
        return line.p1();
    }
    return line.p2();
}

References kisDistance().

findTrianglePoint()

QVector< QPointF > KRITAGLOBAL_EXPORT KisAlgebra2D::findTrianglePoint	(	const QPointF &	p1,
		const QPointF &	p2,
		qreal	a,
		qreal	b )

Find possible positions for point p3, such that points \p1, \p2 and p3 form a triangle, such that the distance between p1 ad p3 is a and the distance between p2 and p3 is b. There might be 0, 1 or 2 such positions.

Definition at line 1017 of file kis_algebra_2d.cpp.

{
    using KisAlgebra2D::norm;
    using KisAlgebra2D::dotProduct;
 
    QVector<QPointF> result;
 
    const QPointF p = p2 - p1;
 
    const qreal pSq = dotProduct(p, p);
 
    const qreal T =  0.5 * (-pow2(b) + pow2(a) + pSq);
 
    if (p.isNull()) return result;
 
    if (qAbs(p.x()) > qAbs(p.y())) {
        const qreal A = 1.0;
        const qreal B2 = -T * p.y() / pSq;
        const qreal C = pow2(T) / pSq - pow2(a * p.x()) / pSq;
 
        const qreal D4 = pow2(B2) - A * C;
 
        if (D4 > 0 || qFuzzyIsNull(D4)) {
            if (qFuzzyIsNull(D4)) {
                const qreal y = -B2 / A;
                const qreal x = (T - y * p.y()) / p.x();
                result << p1 + QPointF(x, y);
            } else {
                const qreal y1 = (-B2 + std::sqrt(D4)) / A;
                const qreal x1 = (T - y1 * p.y()) / p.x();
                result << p1 + QPointF(x1, y1);
 
                const qreal y2 = (-B2 - std::sqrt(D4)) / A;
                const qreal x2 = (T - y2 * p.y()) / p.x();
                result << p1 + QPointF(x2, y2);
            }
        }
    } else {
        const qreal A = 1.0;
        const qreal B2 = -T * p.x() / pSq;
        const qreal C = pow2(T) / pSq - pow2(a * p.y()) / pSq;
 
        const qreal D4 = pow2(B2) - A * C;
 
        if (D4 > 0 || qFuzzyIsNull(D4)) {
            if (qFuzzyIsNull(D4)) {
                const qreal x = -B2 / A;
                const qreal y = (T - x * p.x()) / p.y();
                result << p1 + QPointF(x, y);
            } else {
                const qreal x1 = (-B2 + std::sqrt(D4)) / A;
                const qreal y1 = (T - x1 * p.x()) / p.y();
                result << p1 + QPointF(x1, y1);
 
                const qreal x2 = (-B2 - std::sqrt(D4)) / A;
                const qreal y2 = (T - x2 * p.x()) / p.y();
                result << p1 + QPointF(x2, y2);
            }
        }
    }
 
    return result;
}

References A, B2(), C, dotProduct(), norm(), p, p1, p2, pow2(), and qFuzzyIsNull().

findTrianglePointNearest()

boost::optional< QPointF > KRITAGLOBAL_EXPORT KisAlgebra2D::findTrianglePointNearest	(	const QPointF &	p1,
		const QPointF &	p2,
		qreal	a,
		qreal	b,
		const QPointF &	nearest )

Find a point p3 that forms a triangle with \p1 and \p2 and is the nearest possible point to nearest

See also

findTrianglePoint

Definition at line 1081 of file kis_algebra_2d.cpp.

{
    const QVector<QPointF> points = findTrianglePoint(p1, p2, a, b);
 
    boost::optional<QPointF> result;
 
    if (points.size() == 1) {
        result = points.first();
    } else if (points.size() > 1) {
        result = kisDistance(points.first(), nearest) < kisDistance(points.last(), nearest) ? points.first() : points.last();
    }
 
    return result;
}

References findTrianglePoint(), kisDistance(), p1, and p2.

fromQTransformStraight()

Eigen::Matrix3d KisAlgebra2D::fromQTransformStraight ( const QTransform & t )

inline

Definition at line 776 of file kis_algebra_2d.cpp.

{
    Eigen::Matrix3d m;
 
    m << t.m11() , t.m12() , t.m13()
        ,t.m21() , t.m22() , t.m23()
        ,t.m31() , t.m32() , t.m33();
 
    return m;
}

fuzzyCompareRects()

template<class Rect , typename Difference = decltype(Rect::width())>

bool KisAlgebra2D::fuzzyCompareRects	(	const Rect &	r1,
		const Rect &	r2,
		Difference	tolerance )

Compare two rectangles with tolerance tolerance. The tolerance means that the coordinates of top left and bottom right corners should not differ more than tolerance pixels.

Definition at line 842 of file kis_algebra_2d.h.

                                                                             {
    typedef decltype(r1.topLeft()) Point;
 
    const Point d1 = abs(r1.topLeft() - r2.topLeft());
    const Point d2 = abs(r1.bottomRight() - r2.bottomRight());
 
    const Difference maxError = std::max({d1.x(), d1.y(), d2.x(), d2.y()});
    return maxError < tolerance;
}

References abs(), r1, and r2.

fuzzyMatrixCompare()

bool KRITAGLOBAL_EXPORT KisAlgebra2D::fuzzyMatrixCompare	(	const QTransform &	t1,
		const QTransform &	t2,
		qreal	delta )

Compare the matrices with tolerance delta

Definition at line 744 of file kis_algebra_2d.cpp.

                                                                                 {
    return
            qAbs(t1.m11() - t2.m11()) < delta &&
            qAbs(t1.m12() - t2.m12()) < delta &&
            qAbs(t1.m13() - t2.m13()) < delta &&
            qAbs(t1.m21() - t2.m21()) < delta &&
            qAbs(t1.m22() - t2.m22()) < delta &&
            qAbs(t1.m23() - t2.m23()) < delta &&
            qAbs(t1.m31() - t2.m31()) < delta &&
            qAbs(t1.m32() - t2.m32()) < delta &&
            qAbs(t1.m33() - t2.m33()) < delta;
}

fuzzyPointCompare() [1/3]

template<template< typename > class Cont, class Point >

bool KisAlgebra2D::fuzzyPointCompare	(	const Cont< Point > &	c1,
		const Cont< Point > &	c2,
		qreal	delta )

Returns true if points in two containers are equal with specified tolerance

Definition at line 821 of file kis_algebra_2d.h.

{
    if (c1.size() != c2.size()) return false;
 
    const qreal eps = delta;
 
    return std::mismatch(c1.cbegin(),
                         c1.cend(),
                         c2.cbegin(),
                         [eps] (const QPointF &pt1, const QPointF &pt2) {
                               return fuzzyPointCompare(pt1, pt2, eps);
                         })
            .first == c1.cend();
}

References eps.

fuzzyPointCompare() [2/3]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::fuzzyPointCompare	(	const QPointF &	p1,
		const QPointF &	p2 )

Returns true if the two points are equal within some tolerance, where the tolerance is determined by Qt's built-in fuzzy comparison functions.

Definition at line 757 of file kis_algebra_2d.cpp.

{
    return qFuzzyCompare(p1.x(), p2.x()) && qFuzzyCompare(p1.y(), p2.y());
}

References p1, p2, and qFuzzyCompare().

fuzzyPointCompare() [3/3]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::fuzzyPointCompare	(	const QPointF &	p1,
		const QPointF &	p2,
		qreal	delta )

Returns true if the two points are equal within the specified tolerance

Definition at line 763 of file kis_algebra_2d.cpp.

{
    return qAbs(p1.x() - p2.x()) < delta && qAbs(p1.y() - p2.y()) < delta;
}

References p1, and p2.

getLineFromElements()

QLineF KisAlgebra2D::getLineFromElements	(	const QPainterPath &	shape,
		int	index )

Definition at line 1801 of file kis_algebra_2d.cpp.

{
    QPainterPath::Element element1 = shape.elementAt(wrapValue(index, 0, shape.elementCount() - 1));
    QPainterPath::Element element2 = shape.elementAt(wrapValue(index + 1, 0, shape.elementCount() - 1));
    // it doesn't handle isCurveTo, just assumes it's a line... sorry!
 
    return QLineF(element1, element2);
}

References wrapValue().

getLineSegmentCrossingLineIndexes()

QList< int > KRITAGLOBAL_EXPORT KisAlgebra2D::getLineSegmentCrossingLineIndexes	(	const QLineF &	line,
		const QPainterPath &	shape )

Definition at line 2013 of file kis_algebra_2d.cpp.

{
    VectorPath path(shape);
    QList<int> indexes;
 
    for (int i = 0; i < path.segmentsCount(); i++) {
        QList<VectorPath::VectorPathPoint> points = path.segmentAt(i);
        if (points.count() < 2)
            continue;
        if (points[1].type == VectorPath::VectorPathPoint::BezierTo) {
 
            qreal eps = 1e-5;
            QVector<qreal> intersections = KisBezierUtils::intersectWithLine(points[0].endPoint, points[1].controlPoint1, points[1].controlPoint2, points[1].endPoint, line, eps);
            for (int i = 0; i < intersections.length(); i++) {
                //
                QPointF p = KisBezierUtils::bezierCurve(points[0].endPoint, points[1].controlPoint1, points[1].controlPoint2, points[1].endPoint, intersections[i]);
 
                bool onLine = isOnLine(line, p, eps, true, true, true);
                if (onLine) {
                    indexes << path.segmentIndexToPathIndex(i);
                    break; // we need just one
                }
            }
 
        } else {
 
            QLineF lineSegment = path.segmentAtAsLine(i);
            QPointF intersection;
            QLineF::IntersectionType type = lineSegment.intersects(line, &intersection);
            if (type == QLineF::IntersectionType::BoundedIntersection) {
                indexes << path.segmentIndexToPathIndex(i);
            }
        }
    }
    return indexes;
}

References KisBezierUtils::bezierCurve(), KisAlgebra2D::VectorPath::VectorPathPoint::BezierTo, eps, KisBezierUtils::intersectWithLine(), isOnLine(), and p.

getOnePathFromRectangleCutThrough()

QPainterPath KRITAGLOBAL_EXPORT KisAlgebra2D::getOnePathFromRectangleCutThrough	(	const QList< QPointF > &	points,
		const QLineF &	line,
		bool	left )

Definition at line 1661 of file kis_algebra_2d.cpp.

                                                                                                            {
 
    auto onTheLine = [](QPointF first, QPointF second) {
        float delta = 0.1f;
        return qAbs(first.x() - second.x()) < delta || qAbs(first.y() - second.y()) < delta;
    };
 
    bool started = false;
    QPainterPath path;
 
    path.moveTo(line.p1());
    path.lineTo(line.p2());
 
    QList<QPointF> availablePoints;
    int maxRectPointsNumber = 4; // in case the list has five points to count the first one twice
    for(int i = 0; i < maxRectPointsNumber; i++) {
        qreal whichSide = KisAlgebra2D::crossProduct(line.p2() - line.p1(), line.p2() - points[i]);
        if (whichSide*(left ? 1 : -1) >= 0) {
            availablePoints << points[i];
        }
    }
 
    int startValue, increment;
    if (!left) {
        startValue = 2*availablePoints.length();
        increment = -1;
    } else {
        startValue = 0;
        increment = 1;
    }
 
    auto stopFor = [](int index, int max, bool left) {
        if (!left) {
            return index <= 0;
        } else {
            return index >= max;
        }
    };
 
    for (int i = startValue; !stopFor(i, 2*availablePoints.length(), left); i += increment) {
        int index = KisAlgebra2D::wrapValue(i, 0, (int)availablePoints.length());
 
        if (onTheLine(availablePoints[index], path.currentPosition())) {
            if (!started) {
                started = true;
 
                // TODO: if it's not the same point?
                path.lineTo(availablePoints[index]);
                if (onTheLine(availablePoints[index], line.p1())) {
                    break;
                }
 
            } else {
                // usually would add, unless it's the ending
                if (onTheLine(availablePoints[index], line.p1())) {
                    path.lineTo(availablePoints[index]);
                    break;
                }
                path.lineTo(availablePoints[index]);
            }
        }
    }
 
 
    path.lineTo(line.p1());
 
    return path;
}

References crossProduct(), and wrapValue().

getParallelLines()

QList< QLineF > KRITAGLOBAL_EXPORT KisAlgebra2D::getParallelLines	(	const QLineF &	line,
		const qreal	distance )

Definition at line 1649 of file kis_algebra_2d.cpp.

                                                                         {
 
    QPointF lineNormalVector = QPointF(line.dy(), -line.dx());
    QLineF line1 = QLineF(movePointInTheDirection(line.p1(), lineNormalVector, distance), movePointInTheDirection(line.p2(), lineNormalVector, distance));
    QLineF line2 = QLineF(movePointInTheDirection(line.p1(), -lineNormalVector, distance), movePointInTheDirection(line.p2(), -lineNormalVector, distance));
 
    if (line1.isNull() || line2.isNull()) {
        return QList<QLineF>();
    }
    return {line1, line2};
}

References distance(), and movePointInTheDirection().

getPathsFromRectangleCutThrough()

QList< QPainterPath > KRITAGLOBAL_EXPORT KisAlgebra2D::getPathsFromRectangleCutThrough	(	const QRectF &	rect,
		const QLineF &	leftLine,
		const QLineF &	rightLine )

getPathsFromRectangleCutThrough get paths defining both sides of a rectangle cut through using two (supposedly parallel) lines It is used in the Knife Tool If you just want to cut a rectangle, you can use the same line in both

Parameters

rect	rectangle to cut
leftLine	left line of the rectangle (used for the left-(top) side of the rectangle
rightLine	right line of the rectangle (used for the right-(bottom) side of the rectangle

Returns

Definition at line 1730 of file kis_algebra_2d.cpp.

                                                                                                                         {
 
 
    QPainterPath left;
    QPainterPath right;
 
    left.moveTo(leftLine.p1());
    left.lineTo(leftLine.p2());
 
    right.moveTo(rightLine.p1());
    right.lineTo(rightLine.p2());
 
    QList<QPointF> rectPoints;
    rectPoints << rect.topLeft() << rect.bottomLeft() << rect.bottomRight() << rect.topRight();
 
    left = getOnePathFromRectangleCutThrough(rectPoints, leftLine, true);
    right = getOnePathFromRectangleCutThrough(rectPoints, rightLine, false);
 
    QList<QPainterPath> paths;
    paths << left << right;
 
 
    return paths;
}

References getOnePathFromRectangleCutThrough().

intersectLineConcavePolygon()

QList< QLineF > KisAlgebra2D::intersectLineConcavePolygon	(	const QPolygonF	polygon,
		const QLineF &	line,
		bool	extendFirst,
		bool	extendSecond )

Definition at line 1459 of file kis_algebra_2d.cpp.

                                                                                                                            {
 
    // should use kis_convex_hull instead, that one uses boost
    QPolygonF convexHull = calculateConvexHull(polygon);
    if (convexHull.count() == polygon.count()) {
        QLineF resultLine = line;
        bool result = intersectLineConvexPolygon(resultLine, polygon, extendFirst, extendSecond);
        if (result) {
            return QList<QLineF>() << resultLine;
        } else {
            return QList<QLineF>();
        }
    }
 
    // it was a concave polygon
    // intersectLines
 
    // should be as easy as cutting every line, then sorting the points and creating the lines, except gotta take care of exceptions
 
    KIS_ASSERT(false && "Not implemented yet");
 
    return QList<QLineF>();
}

References calculateConvexHull(), intersectLineConvexPolygon(), and KIS_ASSERT.

intersectLineConvexPolygon()

bool KRITAGLOBAL_EXPORT KisAlgebra2D::intersectLineConvexPolygon	(	QLineF &	line,
		const QPolygonF	polygon,
		bool	extendFirst,
		bool	extendSecond )

Definition at line 251 of file kis_algebra_2d.cpp.

{
    qreal epsilon = 1e-07;
 
    if (polygon.size() == 0) {
        return false;
    }
 
    // trivial case: no extends, all points inside the polygon
    if (!extendFirst && !extendSecond && polygon.containsPoint(line.p1(), Qt::WindingFill) && polygon.containsPoint(line.p2(), Qt::WindingFill)) {
        return true;
    }
 
    // Cyrus-Beck algorithm: https://en.wikipedia.org/wiki/Cyrus%E2%80%93Beck_algorithm
 
    // parametric equation for the line:
    // p(t) = t*P1 + (1-t)*P2
 
    // we can't use infinity here, because the points would all end up as (+/- inf, +/- inf)
    // which would be useless if we have a very specific direction
    // hence we use just "a big number"
    float aBigNumber = 100000; // that will keep t*Px still on the line // this is LIMITATION of the algorithm
    float tmin = extendFirst ? -aBigNumber : 0; // line.p1() - first point, or infinity
    float tmax = extendSecond ? aBigNumber : 1; // line.p2() - second point, or infinity
 
 
 
    QList<QLineF> clippingLines;
    QList<QPointF> normals;
 
    bool clockwise = false;
    {
        // only temporary values to check whether the polygon is clockwise or counterclockwise
        QPointF vec1 = polygon[1] - polygon[0];
        QPointF vec2 = polygon[2] - polygon[0];
 
        QLineF line1(QPointF(0, 0), vec1);
        QLineF line2(QPointF(0, 0), vec2);
 
        qreal angle = line1.angleTo(line2); // range: <0, 360) // <0, 180) means counter-clockwise
        if (angle >= 180) {
            clockwise = true;
        }
    }
 
 
    for (int i = 0; i < polygon.size() - 1; i++) {
        clippingLines.append(QLineF(polygon[i], polygon[i + 1]));
        float xdiff = polygon[i].x() - polygon[i + 1].x();
        float ydiff = polygon[i].y() - polygon[i + 1].y();
 
        if (!clockwise) {
            normals.append(QPointF(ydiff, -xdiff));
        } else {
            normals.append(QPointF(-ydiff, xdiff));
        }
 
    }
 
    if (!polygon.isClosed()) {
        int i = polygon.size() - 1;
        clippingLines.append(QLineF(polygon[i], polygon[0]));
        float xdiff = polygon[i].x() - polygon[0].x();
        float ydiff = polygon[i].y() - polygon[0].y();
 
        if (!clockwise) {
            normals.append(QPointF(ydiff, -xdiff));
        } else {
            normals.append(QPointF(-ydiff, xdiff));
        }
 
    }
 
    QPointF lineVec = line.p2() - line.p1();
    // ax + by + c = 0
    // c = -ax - by
//    qreal cFromStandardEquation = -lineVec.x()*line.p1().x() - lineVec.y()*line.p1().y();
 
 
    QPointF p1 = line.p1();
    QPointF p2 = line.p2();
 
    qreal pA, pB, pC; // standard equation for the line: ax + by + c = 0
    if (qAbs(lineVec.x()) < epsilon) {
        // x1 ~= x2, line looks like: x = -pC
        pB = 0;
        pA = 1;
        pC = -p1.x();
    } else {
        pB = 1; // let b = 1 to simplify
        qreal tmp = (p1.y() - p2.y())/(p1.x() - p2.x());
        pA = -tmp;
        pC = tmp * p1.x() - p1.y();
    }
 
 
    int pEFound = 0;
 
 
    for (int i = 0; i < clippingLines.size(); i++) {
 
        // is the clipping line parallel to the line?
        QPointF clipVec = clippingLines[i].p2() - clippingLines[i].p1();
 
        if (qFuzzyCompare(clipVec.x()*lineVec.y(), clipVec.y()*lineVec.x())) {
 
            // vectors are parallel
            // let's check if one of the clipping points is on the line (extended) to see if it's the same line; if not, proceed normally
 
            qreal distanceBetweenLines = qAbs(pA*clippingLines[i].p1().x() + pB*clippingLines[i].p1().y() + pC)
                    /(sqrt(pA*pA + pB*pB));
 
 
            if (qAbs(distanceBetweenLines) < epsilon) {
                // they are the same line
 
                qreal t1;
                qreal t2;
 
                if (qAbs(p2.x() - p1.x()) > epsilon) {
                    t1 = (clippingLines[i].p1().x() - p1.x())/(p2.x() - p1.x());
                    t2 = (clippingLines[i].p2().x() - p1.x())/(p2.x() - p1.x());
                } else {
                    t1 = (clippingLines[i].p1().y() - p1.y())/(p2.y() - p1.y());
                    t2 = (clippingLines[i].p2().y() - p1.y())/(p2.y() - p1.y());
                }
 
                qreal tmin1 = qMin(t1, t2);
                qreal tmax2 = qMax(t1, t2);
 
 
 
                if (tmin < tmin1) {
                    tmin = tmin1;
                }
                if (tmax > tmax2) {
                    tmax = tmax2;
                }
                continue;
            }
            else {
                // if clipping line points are P1 and P2, and some other point is P(t) (given by parametric equation),
                // and N is the normal vector
                // and one of the points of the line we're intersecting is K,
                // then we have a following equation:
                // K = P(t) + a * N
                // where t and a are unknown.
                // after simplifying we get:
                // t*(p2 - p1) + a*(n) = k - p1
                // and since we have two axis, we get a linear system of two equations
                // A * [t; a] = B
 
                Eigen::Matrix2f A;
                Eigen::Vector2f b;
                A << p2.x() - p1.x(), normals[i].x(),
                     p2.y() - p1.y(), normals[i].y();
                b << clippingLines[i].p1().x() - p1.x(),
                     clippingLines[i].p1().y() - p1.y();
 
                Eigen::Vector2f ta = A.colPivHouseholderQr().solve(b);
 
                qreal tt = ta(1);
                if (tt < 0) {
                    return false;
                }
            }
 
        }
 
 
        boost::optional<QPointF> pEOptional = intersectLines(clippingLines[i], line); // bounded, unbounded
 
 
        if (pEOptional) {
            pEFound++;
 
            QPointF pE = pEOptional.value();
            QPointF n = normals[i];
 
            QPointF A = line.p2() - line.p1();
            QPointF B = line.p1() - pE;
 
            qreal over = (n.x()*B.x() + n.y()*B.y());
            qreal under = (n.x()*A.x() + n.y()*A.y());
            qreal t = -over/under;
 
//            if (pE.x() != p2.x()) {
//                qreal maybet = (pE.x() - p1.x())/(p2.x() - p1.x());
//            }
 
            qreal tminvalue = tmin * under + over;
            qreal tmaxvalue = tmax * under + over;
 
            if (tminvalue > 0 && tmaxvalue > 0) {
                // both outside of the edge
                return false;
            }
            if (tminvalue <= 0 && tmaxvalue <= 0) {
                // noop, both inside
            }
            if (tminvalue*tmaxvalue < 0) {
 
                // on two different sides
                if (tminvalue > 0) {
                    // tmin outside, tmax inside
                    if (t > tmin) {
                        tmin = t;
                    }
                } else {
                    if (t < tmax) {
                        tmax = t;
                    }
                }
            }
 
 
 
            if (tmax < tmin) {
                return false;
            }
        }
        else {
        }
 
    }
 
    if (pEFound == 0) {
        return false;
    }
 
    QLineF response = QLineF(tmin*line.p2() + (1-tmin)*line.p1(), tmax*line.p2() + (1-tmax)*line.p1());
    line = response;
    return true;
}

References A, B, intersectLines(), p1, p2, and qFuzzyCompare().

intersectLineRect() [1/2]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::intersectLineRect	(	QLineF &	line,
		const QRect	rect,
		bool	extend )

Attempt to intersect a line to the area of the a rectangle.

If the line intersects the rectangle, it will be modified to represent the intersecting line segment and true is returned. If the line does not intersect the area, it remains unmodified and false will be returned. If the line is fully inside the rectangle, it's considered "intersecting" so true will be returned.

Parameters

line	line segment
rect	area
extend	extend the line to the edges of the rect area even if the line segment fits inside the rectangle (so, consider the line to be a line defined by those two points, not a line segment)

Returns

true if successful

Definition at line 173 of file kis_algebra_2d.cpp.

{
    return intersectLineRect(line, rect, extend, extend);
}

References intersectLineRect().

intersectLineRect() [2/2]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::intersectLineRect	(	QLineF &	line,
		const QRect	rect,
		bool	extendFirst,
		bool	extendSecond )

Attempt to intersect a line to the area of the a rectangle.

If the line intersects the rectangle, it will be modified to represent the intersecting line segment and true is returned. If the line does not intersect the area, it remains unmodified and false will be returned. If the line is fully inside the rectangle, it's considered "intersecting" so true will be returned.

extendFirst and extendSecond parameters allow one to use this function in case of unbounded lines (if both are true), line segments (if both are false) or half-lines/rays (if one is true and another is false). 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.

Parameters

line	line segment
rect	area
extendFirst	extend the line to the edge of the rect area even if the first point of the line segment lies inside the rectangle
extendSecond	extend the line to the edge of the rect area even if the second point of the line segment lies inside the rectangle

Returns

true if successful

Definition at line 178 of file kis_algebra_2d.cpp.

{
    // using Liang-Barsky algorithm
    // using parametric equation for a line:
    // X = x1 + t(x2-x1) = x1 + t*p2
    // Y = y1 + t(y2-y1) = y1 + t*p4
    // note that we have a line *segment* here, not a line
    // t1 = 0, t2 = 1, no matter what points we got
 
    double p1 = -(line.x2() - line.x1());
    double p2 = -p1;
    double p3 = -(line.y2() - line.y1());
    double p4 = -p3;
 
    QVector<double> p = QVector<double>({p1, p2, p3, p4});
    QVector<double> q = QVector<double>({line.x1() - rect.x(), rect.x() + rect.width() - line.x1(), line.y1() - rect.y(), rect.y() + rect.height() - line.y1()});
 
    float tmin = extendFirst ? -std::numeric_limits<float>::infinity() : 0; // line.p1() - first point, or infinity
    float tmax = extendSecond ? std::numeric_limits<float>::infinity() : 1; // line.p2() - second point, or infinity
 
    for (int i = 0; i < p.length(); i++) {
        // now clipping
        if (p[i] == 0 && q[i] < 0) {
            // line is parallel to the boundary and outside of it
            return false;
        } else if (p[i] < 0) {
            // line entry point (should be tmin)
            double t = q[i]/p[i];
            if (t > tmax) {
                if (extendSecond) {
                    tmax = t;
                } else {
                    return false;
                }
            }
            if (t > tmin) {
                tmin = t;
            }
 
 
        } else if (p[i] > 0) {
            // line leaving point (should be tmax)
            double t = q[i]/p[i];
            if (t < tmin) {
                if (extendFirst) {
                    tmin = t;
                } else {
                    return false;
                }
            }
            if (t < tmax) {
                tmax = t;
            }
        }
    }
 
    QPointF pt1 = line.p1();
    QPointF pt2 = line.p2();
 
    if (extendFirst || tmin > 0) {
        pt1 = QPointF(line.x1() + tmin*(line.x2() - line.x1()), line.y1() + tmin*(line.y2() - line.y1()));
    }
    if (extendSecond || tmax < 1) {
        pt2 = QPointF(line.x1() + tmax*(line.x2() - line.x1()), line.y1() + tmax*(line.y2() - line.y1()));
    }
 
    line.setP1(pt1);
    line.setP2(pt2);
 
    return true;
 
}

References p, p1, p2, and p3.

intersectLines() [1/2]

KRITAGLOBAL_EXPORT boost::optional< QPointF > KisAlgebra2D::intersectLines	(	const QLineF &	boundedLine,
		const QLineF &	unboundedLine )

Find intersection of a bounded line boundedLine with unbounded line unboundedLine (if an intersection exists)

Definition at line 975 of file kis_algebra_2d.cpp.

{
    const QPointF B1 = unboundedLine.p1();
    const QPointF A1 = unboundedLine.p2() - unboundedLine.p1();
 
    const QPointF B2 = boundedLine.p1();
    const QPointF A2 = boundedLine.p2() - boundedLine.p1();
 
    Eigen::Matrix<float, 2, 2> A;
    A << A1.x(), -A2.x(),
         A1.y(), -A2.y();
 
    Eigen::Matrix<float, 2, 1> B;
    B << B2.x() - B1.x(),
         B2.y() - B1.y();
 
    if (qFuzzyIsNull(A.determinant())) {
        return boost::none;
    }
 
    Eigen::Matrix<float, 2, 1> T;
 
    T = A.inverse() * B;
 
    const qreal t2 = T(1,0);
    double epsilon = 1e-06; // to avoid precision issues
 
    if (t2 < 0.0 || t2 > 1.0) {
        if (qAbs(t2) > epsilon && qAbs(t2 - 1.0) > epsilon) {
            return boost::none;
        }
    }
 
    return t2 * A2 + B2;
}

References A, B, B1(), B2(), and qFuzzyIsNull().

intersectLines() [2/2]

KRITAGLOBAL_EXPORT boost::optional< QPointF > KisAlgebra2D::intersectLines	(	const QPointF &	p1,
		const QPointF &	p2,
		const QPointF &	q1,
		const QPointF &	q2 )

Find intersection of a bounded line p1, p2 with unbounded line q1, q2 (if an intersection exists)

Definition at line 1011 of file kis_algebra_2d.cpp.

{
    return intersectLines(QLineF(p1, p2), QLineF(q1, q2));
}

References intersectLines(), p1, p2, q1, and q2.

intersectTwoCircles()

KRITAGLOBAL_EXPORT QVector< QPointF > KisAlgebra2D::intersectTwoCircles	(	const QPointF &	c1,
		qreal	r1,
		const QPointF &	c2,
		qreal	r2 )

Finds the points of intersections between two circles

Returns

the found circles, the result can have 0, 1 or 2 points

Definition at line 638 of file kis_algebra_2d.cpp.

{
    QVector<QPointF> points;
 
    const QPointF diff = (center2 - center1);
    const QPointF c1;
    const QPointF c2 = diff;
 
    const qreal centerDistance = norm(diff);
 
    if (centerDistance > r1 + r2) return points;
    if (centerDistance < qAbs(r1 - r2)) return points;
 
    if (centerDistance < qAbs(r1 - r2) + 0.001) {
        dbgKrita << "Skipping intersection" << ppVar(center1) << ppVar(center2) << ppVar(r1) << ppVar(r2) << ppVar(centerDistance) << ppVar(qAbs(r1-r2));
        return points;
    }
 
    const qreal x_kp1 = diff.x();
    const qreal y_kp1 = diff.y();
 
    const qreal F2 =
        0.5 * (pow2(x_kp1) +
               pow2(y_kp1) + pow2(r1) - pow2(r2));
 
    const qreal eps = 1e-6;
 
    if (qAbs(diff.y()) < eps) {
        qreal x = F2 / diff.x();
        qreal y1, y2;
        int result = KisAlgebra2D::quadraticEquation(
            1, 0,
            pow2(x) - pow2(r2),
            &y1, &y2);
 
        KIS_SAFE_ASSERT_RECOVER(result > 0) { return points; }
 
        if (result == 1) {
            points << QPointF(x, y1);
        } else if (result == 2) {
            KisAlgebra2D::RightHalfPlane p(c1, c2);
 
            QPointF p1(x, y1);
            QPointF p2(x, y2);
 
            if (p.pos(p1) >= 0) {
                points << p1;
                points << p2;
            } else {
                points << p2;
                points << p1;
            }
        }
    } else {
        const qreal A = diff.x() / diff.y();
        const qreal C = F2 / diff.y();
 
        qreal x1, x2;
        int result = KisAlgebra2D::quadraticEquation(
            1 + pow2(A), -2 * A * C,
            pow2(C) - pow2(r1),
            &x1, &x2);
 
        KIS_SAFE_ASSERT_RECOVER(result > 0) { return points; }
 
        if (result == 1) {
            points << QPointF(x1, C - x1 * A);
        } else if (result == 2) {
            KisAlgebra2D::RightHalfPlane p(c1, c2);
 
            QPointF p1(x1, C - x1 * A);
            QPointF p2(x2, C - x2 * A);
 
            if (p.pos(p1) >= 0) {
                points << p1;
                points << p2;
            } else {
                points << p2;
                points << p1;
            }
        }
    }
 
    for (int i = 0; i < points.size(); i++) {
        points[i] = center1 + points[i];
    }
 
    return points;
}

References A, C, dbgKrita, eps, KIS_SAFE_ASSERT_RECOVER, norm(), p, p1, p2, pow2(), ppVar, quadraticEquation(), r1, and r2.

inwardUnitNormal()

template<class T >

T KisAlgebra2D::inwardUnitNormal	(	const T &	a,
		int	polygonDirection )

Definition at line 148 of file kis_algebra_2d.h.

{
    return polygonDirection * leftUnitNormal(a);
}

References leftUnitNormal(), and polygonDirection().

isInRange()

template<typename T >

bool KisAlgebra2D::isInRange	(	T	x,
		T	a,
		T	b )

Definition at line 199 of file kis_algebra_2d.h.

                              {
    T length = qAbs(a - b);
    return qAbs(x - a) <= length && qAbs(x - b) <= length;
}

References length().

isInsideShape() [1/2]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::isInsideShape	(	const QPainterPath &	path,
		const QPointF &	point )

Definition at line 2496 of file kis_algebra_2d.cpp.

{
    for (int i = 0; i < path.elementCount(); i++) {
        if (path.elementAt(i).type == QPainterPath::CurveToDataElement) {
            // contains control points
            return isInsideShape(VectorPath(path), point);
        }
    }
 
    return path.toFillPolygon().containsPoint(point, Qt::WindingFill);
}

References isInsideShape().

isInsideShape() [2/2]

bool KRITAGLOBAL_EXPORT KisAlgebra2D::isInsideShape	(	const VectorPath &	path,
		const QPointF &	point )

Definition at line 2415 of file kis_algebra_2d.cpp.

{
    if (path.pointsCount() == 0) {
        return false;
    }
 
    QRectF boundRect;
    accumulateBounds(path.pointAt(0).endPoint, &boundRect);
 
    bool isPolygon = true;
 
    for (int i = 0; i < path.segmentsCount(); i++) {
        QList<VectorPath::VectorPathPoint> points = path.segmentAt(i);
        accumulateBounds(points[0].endPoint, &boundRect);
        accumulateBounds(points[1].endPoint, &boundRect);
 
        if (points[1].type == VectorPath::VectorPathPoint::BezierTo) {
            accumulateBounds(points[1].controlPoint1, &boundRect);
            accumulateBounds(points[1].controlPoint2, &boundRect);
            isPolygon = false;
        }
    }
 
    if (!boundRect.contains(point)) {
        return false;
    }
 
    if (isPolygon) {
        return path.asPainterPath().toFillPolygon().containsPoint(point, Qt::WindingFill);
    }
 
    boundRect = kisGrowRect(boundRect, 5); // just safety margins
 
    // NOTE: it would be way faster to do it taking into account the fact that the lines are vertical and horizontal
    // except for the last one maybe
    // but let's wait until it proves to be a problem
    QList<QLineF> lines;
    lines << QLineF(point, QPointF(boundRect.left(), point.y()));
    lines << QLineF(point, QPointF(boundRect.right(), point.y()));
    lines << QLineF(point, QPointF(point.x(), boundRect.top()));
    lines << QLineF(point, QPointF(point.x(), boundRect.bottom()));
    lines << QLineF(point, boundRect.topLeft()); // last resort, diagonal
 
    int intersectionsCount = 0;
 
    for (int k = 0; k < lines.length(); k++) {
        int intersections = 0;
        QLineF line = lines[k];
        bool checkNext = false;
 
        for (int i = 0; i < path.segmentsCount(); i++) {
            std::optional<VectorPath::Segment> segmentOpt = path.segmentAtAsSegment(i);
            KIS_SAFE_ASSERT_RECOVER(segmentOpt.has_value()) {continue;}
            VectorPath::Segment segment = segmentOpt.value();
 
            QList<QPointF> intersectionsHere = VectorPath::intersectSegmentWithLineBounded(line, segment);
            qreal eps = 1e-4;
 
            for (int i = 0; i < intersectionsHere.count(); i++) {
                if (fuzzyPointCompare(intersectionsHere[i], segment.startPoint, eps) || fuzzyPointCompare(intersectionsHere[i], segment.endPoint, eps)) {
                    checkNext = true;
                    break;
                }
            }
 
            if (checkNext) {
                break;
            }
 
            intersections += intersectionsHere.count();
        }
 
        intersectionsCount = intersections;
        if (!checkNext) {
            break;
        }
    }
 
    return intersectionsCount%2 == 1;
}

References accumulateBounds(), KisAlgebra2D::VectorPath::VectorPathPoint::BezierTo, KisAlgebra2D::VectorPath::Segment::endPoint, eps, fuzzyPointCompare(), KisAlgebra2D::VectorPath::intersectSegmentWithLineBounded(), KIS_SAFE_ASSERT_RECOVER, kisGrowRect(), and KisAlgebra2D::VectorPath::Segment::startPoint.

isOnLine()

bool KisAlgebra2D::isOnLine	(	const QLineF &	line,
		const QPointF &	point,
		const qreal	eps,
		bool	boundedStart,
		bool	boundedEnd,
		bool	includeEnds )

Definition at line 2508 of file kis_algebra_2d.cpp.

{
    if (fuzzyPointCompare(point, line.p1(), eps)) {
        return includeEnds || !boundedStart;
    }
    if (fuzzyPointCompare(point, line.p2(), eps)) {
        return includeEnds || !boundedEnd;
    }
 
    if (kisDistanceToLine(point, line) > eps) {
        return false;
    }
 
    QPointF lineVector = line.p2() - line.p1();
    QPointF pointVector = point - line.p1();
    qreal t = -1;
    if (qAbs(pointVector.x()) < eps) {
        // use y
        t = pointVector.y()/lineVector.y();
    } else {
        t = pointVector.x()/lineVector.x();
    }
 
    if (t < 0) {
        return !boundedStart;
    }
    if (t > 1.0) {
        return !boundedEnd;
    }
 
    return true;
}

References eps, fuzzyPointCompare(), and kisDistanceToLine().

isPolygonRect()

template<class Polygon , typename Difference = decltype(Polygon::first())>

bool KisAlgebra2D::isPolygonRect	(	const Polygon &	poly,
		Difference	tolerance )

Definition at line 855 of file kis_algebra_2d.h.

                                                              {
    typedef decltype(poly.first()) Point;
 
    auto sameVert = [tolerance] (Point p1, Point p2) {
        return std::abs(p2.x() - p1.x()) < tolerance;
    };
 
 
    auto sameHoriz = [tolerance] (Point p1, Point p2) {
        return std::abs(p2.y() - p1.y()) < tolerance;
    };
 
    const int rectCorners = 4;
    if (poly.length() != rectCorners) {
        if (poly.length() != rectCorners + 1 || !fuzzyPointCompare(poly[0], poly[rectCorners], tolerance)) {
            return false;
        }
    }
 
    bool correctRect = sameVert(poly[0], poly[1]) && sameHoriz(poly[1], poly[2]) && sameVert(poly[2], poly[3]) && sameHoriz(poly[3], poly[0]);
    if (correctRect) {
        return true;
    }
    return sameHoriz(poly[0], poly[1]) && sameVert(poly[1], poly[2]) && sameHoriz(poly[2], poly[3]) && sameVert(poly[3], poly[0]);
 
}

References fuzzyPointCompare(), p1, and p2.

isPolygonTrulyConvex()

template<class T >

bool KisAlgebra2D::isPolygonTrulyConvex

(

const QVector< T > &

polygon

)

Definition at line 884 of file kis_algebra_2d.h.

                                                     {
    const int numPoints = polygon.size();
    if (numPoints < 3)
        return true;
 
    qreal baseAngle = std::atan2(polygon[1].y() - polygon[0].y(), polygon[1].x() - polygon[0].x());
    qreal secondAngle = std::atan2(polygon[2].y() - polygon[1].y(), polygon[2].x() - polygon[1].x());
 
 
    qreal prevAngle = secondAngle;
    secondAngle -= baseAngle;
 
    qreal sign = signZZ(secondAngle);
    for (int i = 2; i < numPoints; i++) {
        int next = i == (numPoints - 1) ? 0 : i + 1;
        if (next == 0 && fuzzyPointCompare(polygon[next], polygon[i])) {
            break;
        }
        qreal nextAngle = std::atan2(polygon[next].y() - polygon[i].y(), polygon[next].x() - polygon[i].x());
 
        qreal newPrevAngle = nextAngle;
        nextAngle -= baseAngle;
        nextAngle -= prevAngle;
        prevAngle = newPrevAngle;
        if (nextAngle < -M_PI) {
            nextAngle += 2*M_PI;
        } else if (nextAngle > M_PI) {
            nextAngle -= 2*M_PI;
        }
        if (int(signZZ(nextAngle)) != sign) {
            return false;
        }
    }
    return true;
}

References fuzzyPointCompare(), M_PI, sign(), and signZZ().

lazyRound()

template<typename R >

R KisAlgebra2D::lazyRound

(

qreal

value

)

Helper function to convert a qreal to int lazily. If the passed type is an integer, then the value is rounded. Otherwise it is just passed forward.

lazyRound< int >()

template<>

int KisAlgebra2D::lazyRound< int > ( qreal value )

inline

Definition at line 162 of file kis_algebra_2d.h.

{
    return qRound(value);
}

References value().

lazyRound< qreal >()

template<>

qreal KisAlgebra2D::lazyRound< qreal > ( qreal value )

inline

Definition at line 168 of file kis_algebra_2d.h.

{
    return value;
}

References value().

leftUnitNormal()

template<class T >

T KisAlgebra2D::leftUnitNormal

(

const T &

a

)

Definition at line 132 of file kis_algebra_2d.h.

{
    T result = a.x() != 0 ? T(-a.y() / a.x(), 1) : T(-1, 0);
    qreal length = norm(result);
    result *= (crossProduct(a, result) >= 0 ? 1 : -1) / length;
 
    return -result;
}

References crossProduct(), length(), and norm().

lerp()

template<typename Point >

Point KisAlgebra2D::lerp	(	const Point &	pt1,
		const Point &	pt2,
		qreal	t )

Definition at line 82 of file kis_algebra_2d.h.

{
    return pt1 + (pt2 - pt1) * t;
}

linearReshapeFunc()

template<typename T >

T KisAlgebra2D::linearReshapeFunc ( T x, T x0, T x1, T y0, T y1 )

inline

Linearly reshape function x so that in range [x0, x1] it would cross points (x0, y0) and (x1, y1).

Definition at line 995 of file kis_algebra_2d.h.

{
    return y0 + (y1 - y0) * (x - x0) / (x1 - x0);
}

lineSideForPoint()

int KisAlgebra2D::lineSideForPoint	(	const QLineF &	line,
		const QPointF &	point )

Definition at line 1308 of file kis_algebra_2d.cpp.

{
    // TODO: do we really neede these explicit checks? Do they help with
    //       precision?
 
    if (fuzzyPointCompare(point, line.p1())) {
        return 0;
    }
    if (fuzzyPointCompare(point, line.p2())) {
        return 0;
    }
    if (qFuzzyCompare(line.length(), 0)) {
        return 0;
    }
 
    qreal whichSide = KisAlgebra2D::crossProduct(line.p2() - line.p1(), point - line.p1());
    return qFuzzyIsNull(whichSide) ? 0 : (whichSide > 0 ? 1 : -1);
}

References crossProduct(), fuzzyPointCompare(), qFuzzyCompare(), and qFuzzyIsNull().

makeFullTransformComponents()

KisTransformComponents KRITAGLOBAL_EXPORT KisAlgebra2D::makeFullTransformComponents

(

)

Definition at line 13 of file KisTransformComponents.cpp.

{
    return KisTransformComponent::Translate | KisTransformComponent::Scale | KisTransformComponent::Rotate
        | KisTransformComponent::Shear | KisTransformComponent::Project;
}

References Project, Rotate, Scale, Shear, and Translate.

mapToRect()

KRITAGLOBAL_EXPORT QTransform KisAlgebra2D::mapToRect

(

const QRectF &

rect

)

Definition at line 729 of file kis_algebra_2d.cpp.

{
    return
        QTransform(rect.width(), 0, 0, rect.height(),
                   rect.x(), rect.y());
}

mapToRectInverse()

KRITAGLOBAL_EXPORT QTransform KisAlgebra2D::mapToRectInverse

(

const QRectF &

rect

)

Definition at line 736 of file kis_algebra_2d.cpp.

{
    return
        QTransform::fromTranslate(-rect.x(), -rect.y()) *
        QTransform::fromScale(rect.width() != 0 ? 1.0 / rect.width() : 0.0,
                              rect.height() != 0 ? 1.0 / rect.height() : 0.0);
}

maxDimension()

template<class Size >

auto KisAlgebra2D::maxDimension

(

Size

size

)

-> decltype(size.width())

Definition at line 338 of file kis_algebra_2d.h.

                                                       {
    return qMax(size.width(), size.height());
}

mergeShapesWithGutter()

VectorPath KisAlgebra2D::mergeShapesWithGutter	(	const VectorPath &	shape1,
		const VectorPath &	shape2,
		const VectorPath &	oneEnd,
		const VectorPath &	otherEnd,
		int	index1,
		int	index2,
		bool	reverseSecondPoly,
		bool	isSameShape )

mergeShapesWithGutter merges two shapes with a gutter shape (defined as two paths)

Parameters

shape1
shape2
oneEnd
otherEnd
index1	index of the segment in the first shape
index2	index of the segment in the second shape

Returns

Definition at line 1898 of file kis_algebra_2d.cpp.

{
    using VPoint = VectorPath::VectorPathPoint;
    QList<VPoint> result;
 
    result.append(shape1.pointAt(0));
 
    auto appendFrom = [] (QList<VPoint>& res, int start, int end, const VectorPath& shape) {
        start = qBound(0, start, shape.segmentsCount() - 1);
        end = qBound(0, end, shape.segmentsCount() - 1);
 
        for (int i = start; i < end; i++) {
            QList<VPoint> segment = shape.segmentAt(i);
            KIS_SAFE_ASSERT_RECOVER_RETURN(segment.length() == 2);
            res.append(segment[1]);
        }
    };
 
    VectorPath reversedShape2 = reverseSecondPoly ? shape2.reversed() : VectorPath(shape2);
    int reversedIndex2 = reverseSecondPoly ? (shape2.segmentsCount() - index2 - 1) : index2;
 
    if (isSameShape) {
        int minIndex = qMin(index1, index2);
        int maxIndex = qMax(index1, index2);
 
        // the indexes define a way to cut the shape into two shapes
        // and one of them is kind of more outer than the other
        // (they could intersect but... that's the user problem at that point, they can fix it point by point)
        // in normal situation, it's like an outer ring of edges and inner ring of edges (which might be just one edge, which is the most common case)
        // and we can find that out by checking whether the ends of the selected edges are inside or outside of the shape
        // and if they're inside a shape, we're assuming that's the resulting shape (and the other is discarded)
        // no islands in comic panels on my watch!
 
        QList<VPoint> result1;
        // min index to max index
        if (minIndex < 0 || maxIndex >= shape1.segmentsCount()) {
            return shape1;
        }
 
        result1 << VPoint::moveTo(shape1.segmentAt(minIndex)[1].endPoint);
        appendFrom(result1, minIndex + 1, maxIndex, shape1);
 
        QList<VPoint> result2;
        result2 << VPoint::moveTo(shape1.segmentAt(maxIndex)[1].endPoint);
        appendFrom(result2, maxIndex + 1, shape1.segmentsCount(), shape1);
        appendFrom(result2, 0, minIndex, shape1);
 
 
        VectorPath minEnd = index1 > index2 ? oneEnd : otherEnd;
        VectorPath maxEnd = index1 > index2 ? otherEnd : oneEnd;
 
        appendFrom(result1, 0, minEnd.segmentsCount(), minEnd);
        appendFrom(result2, 0, maxEnd.segmentsCount(), maxEnd);
 
        VectorPath result1Vec(result1);
        VectorPath result2Vec(result2);
 
 
        // TODO: assumes winding fill
        if (isInsideShape(result2Vec, shape1.segmentAt(minIndex)[1].endPoint)) {
            // could check all
            return result2Vec;
        }
        return result1Vec;
 
    } else {
        appendFrom(result, 0, index1, shape1);
        appendFrom(result, 0, oneEnd.segmentsCount(), oneEnd);
        appendFrom(result, reversedIndex2 + 1, reversedShape2.segmentsCount(), reversedShape2);
        appendFrom(result, 0, reversedIndex2, reversedShape2);
        appendFrom(result, 0, otherEnd.segmentsCount(), otherEnd);
        appendFrom(result, index1 + 1, shape1.segmentsCount(), shape1);
    }
 
    return VectorPath(result);
 
}

References isInsideShape(), KIS_SAFE_ASSERT_RECOVER_RETURN, KisAlgebra2D::VectorPath::pointAt(), KisAlgebra2D::VectorPath::reversed(), KisAlgebra2D::VectorPath::segmentAt(), and KisAlgebra2D::VectorPath::segmentsCount().

minDimension()

template<class Size >

auto KisAlgebra2D::minDimension

(

Size

size

)

-> decltype(size.width())

Definition at line 343 of file kis_algebra_2d.h.

                                                       {
    return qMin(size.width(), size.height());
}

moveElasticPoint() [1/2]

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::moveElasticPoint	(	const QPointF &	pt,
		const QPointF &	base,
		const QPointF &	newBase,
		const QPointF &	wingA,
		const QPointF &	wingB )

moveElasticPoint moves point pt based on the model of elasticity

Parameters

pt	point in question, tied to points base, wingA and wingB using springs
base	initial position of the dragged point
newBase	final position of the dragged point
wingA	first anchor point
wingB	second anchor point

Returns

the new position of pt

The function requires (newBase - base) be much smaller than any of the distances between other points. If larger distances are necessary, then use integration.

Definition at line 1096 of file kis_algebra_2d.cpp.

{
    using KisAlgebra2D::norm;
    using KisAlgebra2D::dotProduct;
    using KisAlgebra2D::crossProduct;
 
    const QPointF vecL = base - pt;
    const QPointF vecLa = wingA - pt;
    const QPointF vecLb = wingB - pt;
 
    const qreal L = norm(vecL);
    const qreal La = norm(vecLa);
    const qreal Lb = norm(vecLb);
 
    const qreal sinMuA = crossProduct(vecLa, vecL) / (La * L);
    const qreal sinMuB = crossProduct(vecL, vecLb) / (Lb * L);
 
    const qreal cosMuA = dotProduct(vecLa, vecL) / (La * L);
    const qreal cosMuB = dotProduct(vecLb, vecL) / (Lb * L);
 
    const qreal dL = dotProduct(newBase - base, -vecL) / L;
 
 
    const qreal divB = (cosMuB + La / Lb * sinMuB * cosMuA / sinMuA) / L +
            (cosMuB + sinMuB * cosMuA / sinMuA) / Lb;
    const qreal dLb = dL / ( L * divB);
 
    const qreal divA = (cosMuA + Lb / La * sinMuA * cosMuB / sinMuB) / L +
            (cosMuA + sinMuA * cosMuB / sinMuB) / La;
    const qreal dLa = dL / ( L * divA);
 
    boost::optional<QPointF> result =
        KisAlgebra2D::findTrianglePointNearest(wingA, wingB, La + dLa, Lb + dLb, pt);
 
    const QPointF resultPoint = result ? *result : pt;
 
    return resultPoint;
}

References crossProduct(), dotProduct(), findTrianglePointNearest(), and norm().

moveElasticPoint() [2/2]

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::moveElasticPoint	(	const QPointF &	pt,
		const QPointF &	base,
		const QPointF &	newBase,
		const QVector< QPointF > &	anchorPoints )

moveElasticPoint moves point pt based on the model of elasticity

Parameters

pt	point in question, tied to points base, anchorPoints using springs
base	initial position of the dragged point
newBase	final position of the dragged point
anchorPoints	anchor points

Returns

the new position of pt

The function expects (newBase - base) be much smaller than any of the distances between other points. If larger distances are necessary, then use integration.

Definition at line 1202 of file kis_algebra_2d.cpp.

{
    const QPointF offset = newBase - base;
 
    QPointF newResultPoint = pt + offset;
 
#ifdef HAVE_GSL
 
    ElasticMotionData data;
    data.newBasePos = newBase;
    data.oldBasePos = base;
    data.anchorPoints = anchorPoints;
    data.oldResultPoint = pt;
 
    const gsl_multimin_fminimizer_type *T =
        gsl_multimin_fminimizer_nmsimplex2;
    gsl_multimin_fminimizer *s = 0;
    gsl_vector *ss, *x;
    gsl_multimin_function minex_func;
 
    size_t iter = 0;
    int status;
    double size;
 
    /* Starting point */
    x = gsl_vector_alloc (2);
    gsl_vector_set (x, 0, newResultPoint.x());
    gsl_vector_set (x, 1, newResultPoint.y());
 
    /* Set initial step sizes to 0.1 */
    ss = gsl_vector_alloc (2);
    gsl_vector_set (ss, 0, 0.1 * offset.x());
    gsl_vector_set (ss, 1, 0.1 * offset.y());
 
    /* Initialize method and iterate */
    minex_func.n = 2;
    minex_func.f = elasticMotionError;
    minex_func.params = (void*)&data;
 
    s = gsl_multimin_fminimizer_alloc (T, 2);
    gsl_multimin_fminimizer_set (s, &minex_func, x, ss);
 
    do
    {
        iter++;
        status = gsl_multimin_fminimizer_iterate(s);
 
        if (status)
            break;
 
        size = gsl_multimin_fminimizer_size (s);
        status = gsl_multimin_test_size (size, 1e-6);
 
        if (status == GSL_SUCCESS && elasticMotionError(s->x, &data) > 0.5) {
            status = GSL_CONTINUE;
        }
 
        if (status == GSL_SUCCESS)
        {
//             qDebug() << "*******Converged to minimum";
//             qDebug() << gsl_vector_get (s->x, 0)
//                      << gsl_vector_get (s->x, 1)
//                      << "|" << s->fval << size;
//             qDebug() << ppVar(iter);
 
             newResultPoint.rx() = gsl_vector_get (s->x, 0);
             newResultPoint.ry() = gsl_vector_get (s->x, 1);
        }
    }
    while (status == GSL_CONTINUE && iter < 10000);
 
    if (status != GSL_SUCCESS) {
        ENTER_FUNCTION() << "failed to find point" << ppVar(pt) << ppVar(base) << ppVar(newBase);
    }
 
    gsl_vector_free(x);
    gsl_vector_free(ss);
    gsl_multimin_fminimizer_free (s);
#endif
 
    return newResultPoint;
}

References ENTER_FUNCTION, and ppVar.

movePointAlongTheLine()

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::movePointAlongTheLine	(	const QPointF &	point,
		const QLineF &	direction,
		qreal	distance,
		bool	ensureOnLine )

movePointAlongTheLine moves the point a particular distance in the specified direction

Parameters

point	the point to move
direction	the direction to move the point along
distance	distance to move the point
ensureOnLine	if true, the algorithm will first change the point to the nearest point on the line, and then move it along the line (if not true, it's an equivalent of movePointInTheDirection, with QPointF being a vector of direction)

Returns

the new position of the moved point

Definition at line 1790 of file kis_algebra_2d.cpp.

{
    QPointF response = point;
    if (ensureOnLine) {
        response = findNearestPointOnLine(point, direction);
    }
    return movePointInTheDirection(response, direction.p2() - direction.p1(), distance);
}

References distance(), findNearestPointOnLine(), and movePointInTheDirection().

movePointInTheDirection()

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::movePointInTheDirection	(	const QPointF &	point,
		const QPointF &	direction,
		qreal	distance )

movePointAlongTheLine moves the point a particular distance in the specified direction

Parameters

point	the point to move
direction	the direction to move the point along
distance	distance to move the point

Returns

the new position of the moved point

Definition at line 1783 of file kis_algebra_2d.cpp.

{
    QPointF response = point;
    QLineF line = QLineF(QPointF(0, 0), direction);
    return response + distance*direction/line.length();
}

References distance().

norm()

template<class T >

qreal KisAlgebra2D::norm

(

const T &

a

)

Definition at line 63 of file kis_algebra_2d.h.

{
    return std::sqrt(pow2(a.x()) + pow2(a.y()));
}

References pow2().

normalize()

template<class Point >

Point KisAlgebra2D::normalize

(

const Point &

a

)

Definition at line 75 of file kis_algebra_2d.h.

{
    const qreal length = norm(a);
    return (1.0 / length) * a;
}

References length(), and norm().

normSquared()

template<class T >

qreal KisAlgebra2D::normSquared

(

const T &

a

)

Definition at line 69 of file kis_algebra_2d.h.

{
    return pow2(a.x()) + pow2(a.y());
}

References pow2().

operator<<() [1/2]

QDebug KRITAGLOBAL_EXPORT KisAlgebra2D::operator<<	(	QDebug	debug,
		const VectorPath &	path )

Definition at line 2391 of file kis_algebra_2d.cpp.

{
    debug << path.asPainterPath();
    return debug;
}

operator<<() [2/2]

QDebug KRITAGLOBAL_EXPORT KisAlgebra2D::operator<<	(	QDebug	debug,
		const VectorPath::VectorPathPoint &	point )

Definition at line 2397 of file kis_algebra_2d.cpp.

{
    bool autoInsertSpaces = debug.autoInsertSpaces();
    debug.setAutoInsertSpaces(false);
    debug << (point.type == VectorPath::VectorPathPoint::MoveTo ? "(move " : (point.type == VectorPath::VectorPathPoint::BezierTo ? "(curve " : "(line "));
    debug << "(" << point.endPoint.x() << ", " << point.endPoint.y() << ")";
    if (point.type == VectorPath::VectorPathPoint::BezierTo) {
        debug << ": (";
        debug << "(" << point.controlPoint1.x() << ", " << point.controlPoint1.y() << ")";
        debug << ", ";
        debug << "(" << point.controlPoint2.x() << ", " << point.controlPoint2.y() << ")";
        debug << ")";
    }
    debug << ")";
    debug.setAutoInsertSpaces(autoInsertSpaces);
    return debug;
}

References KisAlgebra2D::VectorPath::VectorPathPoint::BezierTo, KisAlgebra2D::VectorPath::VectorPathPoint::controlPoint1, KisAlgebra2D::VectorPath::VectorPathPoint::controlPoint2, KisAlgebra2D::VectorPath::VectorPathPoint::endPoint, KisAlgebra2D::VectorPath::VectorPathPoint::MoveTo, and KisAlgebra2D::VectorPath::VectorPathPoint::type.

pointToLineDistSquared()

qreal KRITAGLOBAL_EXPORT KisAlgebra2D::pointToLineDistSquared	(	const QPointF &	pt,
		const QLineF &	line )

Definition at line 1555 of file kis_algebra_2d.cpp.

{
    // distance = |(p2 - p1) x (p1 - pt)| / |p2 - p1|
 
    // magnitude of (p2 - p1) x (p1 - pt)
    const qreal cross = (line.dx() * (line.y1() - pt.y()) - line.dy() * (line.x1() - pt.x()));
 
    return cross * cross / (line.dx() * line.dx() + line.dy() * line.dy());
}

polygonDirection()

template<class T >

int KisAlgebra2D::polygonDirection

(

const QVector< T > &

polygon

)

Returns

1 if the polygon is counterclockwise -1 if the polygon is clockwise

Note: the sign is flipped because our 0y axis is reversed

Definition at line 181 of file kis_algebra_2d.h.

                                                {
 
    typename PointTypeTraits<T>::value_type doubleSum = 0;
 
    const int numPoints = polygon.size();
    for (int i = 1; i <= numPoints; i++) {
        int prev = i - 1;
        int next = i == numPoints ? 0 : i;
 
        doubleSum +=
            (polygon[next].x() - polygon[prev].x()) *
            (polygon[next].y() + polygon[prev].y());
    }
 
    return doubleSum >= 0 ? 1 : -1;
}

Q_DECLARE_FLAGS()

KisAlgebra2D::Q_DECLARE_FLAGS	(	KisTransformComponents	,
		KisTransformComponent	)

quadraticEquation()

KRITAGLOBAL_EXPORT int KisAlgebra2D::quadraticEquation	(	qreal	a,
		qreal	b,
		qreal	c,
		qreal *	x1,
		qreal *	x2 )

Solves a quadratic equation in a form:

a * x^2 + b * x + c = 0

WARNING: Please note that a must be nonzero! Otherwise the equation is not quadratic! And this function doesn't check that!

Returns

the number of solutions. It can be 0, 1 or 2.

x1, x2 — the found solution. The variables are filled with data iff the corresponding solution is found. That is: 0 solutions — variables are not touched, 1 solution — x1 is filled with the result, 2 solutions — x1 and x2 are filled.

Definition at line 615 of file kis_algebra_2d.cpp.

{
    int numSolutions = 0;
 
    const qreal D = pow2(b) - 4 * a * c;
    const qreal eps = 1e-14;
 
    if (qAbs(D) <= eps) {
        *x1 = -b / (2 * a);
        numSolutions = 1;
    } else if (D < 0) {
        return 0;
    } else {
        const qreal sqrt_D = std::sqrt(D);
 
        *x1 = (-b + sqrt_D) / (2 * a);
        *x2 = (-b - sqrt_D) / (2 * a);
        numSolutions = 2;
    }
 
    return numSolutions;
}

References D(), eps, and pow2().

relativeToAbsolute() [1/3]

QPointF KisAlgebra2D::relativeToAbsolute ( const QPointF & pt, const QRectF & rc )

inline

Scale the relative point \pt into the bounds of rc. The point might be outside the rectangle.

Definition at line 752 of file kis_algebra_2d.h.

                                                                       {
    return rc.topLeft() + QPointF(pt.x() * rc.width(), pt.y() * rc.height());
}

relativeToAbsolute() [2/3]

QRectF KisAlgebra2D::relativeToAbsolute ( const QRectF & rel, const QRectF & rc )

inline

Scales relative isotropic value from relative to absolute coordinate system using SVG 1.1 rules (see chapter 7.10)

Definition at line 789 of file kis_algebra_2d.h.

                                                                      {
    return QRectF(relativeToAbsolute(rel.topLeft(), rc), relativeToAbsolute(rel.bottomRight(), rc));
}

References relativeToAbsolute().

relativeToAbsolute() [3/3]

qreal KisAlgebra2D::relativeToAbsolute ( qreal value, const QRectF & rc )

inline

Scales relative isotropic value from relative to absolute coordinate system using SVG 1.1 rules (see chapter 7.10)

Definition at line 771 of file kis_algebra_2d.h.

                                                               {
    const qreal coeff = std::sqrt(pow2(rc.width()) + pow2(rc.height())) / std::sqrt(2.0);
    return value * coeff;
}

References pow2(), and value().

removeGutterOneEndSmart()

QPainterPath KisAlgebra2D::removeGutterOneEndSmart	(	const QPainterPath &	shape1,
		int	index1,
		const QPainterPath &	shape2,
		int	index2,
		QLineF	middleLine,
		bool	reverseFirstPoly,
		bool	reverseSecondPoly )

Definition at line 1817 of file kis_algebra_2d.cpp.

{
    // moving from shape1.index1.p1 to shape1.index2.p2
 
    auto reverseIfNeeded = [] (const QLineF &line, bool reverse) {
        if (reverse) {
            return reverseDirection(line);
        }
        return line;
    };
 
    QLineF line1 = reverseIfNeeded(getLineFromElements(shape1, index1), reverseFirstPoly);
    QLineF line2 = reverseIfNeeded(getLineFromElements(shape2, index2), reverseSecondPoly);
 
    QLineF leftLine;
    QLineF rightLine;
 
    int indexMultiplierFirst = reverseFirstPoly ? -1 : 1;
    int indexMultiplierSecond = reverseSecondPoly ? -1 : 1;
 
    leftLine = reverseIfNeeded(getLineFromElements(shape1, index1 - indexMultiplierFirst*1), reverseFirstPoly);
    rightLine = reverseIfNeeded(getLineFromElements(shape2, index2 + indexMultiplierSecond*1), reverseSecondPoly);
 
    qreal leftPointDistanceFromMiddle;
    qreal rightPointDistanceFromMiddle;
 
    QPointF leftPoint = line1.p1();
    QPointF rightPoint = line2.p2();
 
    leftPointDistanceFromMiddle = kisDistanceToLine(leftPoint, middleLine);
    rightPointDistanceFromMiddle = kisDistanceToLine(rightPoint, middleLine);
 
    QPainterPath simpleResult;
    simpleResult.moveTo(leftPoint);
    simpleResult.lineTo(rightPoint);
 
    auto makeTrianglePath = [leftPoint, rightPoint] (QPointF middle) {
        QPainterPath result;
        result.moveTo(leftPoint);
        result.lineTo(middle);
        result.lineTo(rightPoint);
        return result;
    };
 
    QPointF intersectionPoint;
    QLineF::IntersectionType intersectionType = leftLine.intersects(rightLine, &intersectionPoint);
 
    qreal distanceToMiddle = 0;
    if (intersectionType != QLineF::NoIntersection) {
        distanceToMiddle = kisDistanceToLine(intersectionPoint, middleLine);
    }
 
 
    if (intersectionType == QLineF::NoIntersection || distanceToMiddle > qMax(leftPointDistanceFromMiddle, rightPointDistanceFromMiddle)) {
 
        // first arg: bounded line, second: unbounded
        boost::optional<QPointF> leftIntersection = intersectLines(line2, leftLine);
        boost::optional<QPointF> rightIntersection = intersectLines(line1, rightLine);
 
        if (leftIntersection.has_value()) {
            return makeTrianglePath(leftIntersection.value());
        } else if (rightIntersection.has_value()) {
            return makeTrianglePath(rightIntersection.value());
        } else {
            return simpleResult;
        }
 
    }
 
    QPainterPath betterResult = makeTrianglePath(intersectionPoint);
 
    return betterResult;
 
}

References getLineFromElements(), intersectLines(), kisDistanceToLine(), and reverseDirection().

removeGutterSmart()

QPainterPath KRITAGLOBAL_EXPORT KisAlgebra2D::removeGutterSmart	(	const QPainterPath &	shape1,
		int	index1,
		const QPainterPath &	shape2,
		int	index2,
		bool	isSameShape )

removeGutterSmart

Parameters

shape1
index1
shape2
index2

Returns

Definition at line 1977 of file kis_algebra_2d.cpp.

{
    if (index1 + 1 >= shape1.elementCount() || index2 + 1 >= shape2.elementCount()) {
        return QPainterPath();
    }
 
    QLineF line1 = getLineFromElements(shape1, index1);
    QLineF line2 = getLineFromElements(shape2, index2);
 
    QVector<QPointF> poly1 = QVector<QPointF>() << line1.p1() << line1.p2() << line2.p1();
    QVector<QPointF> poly2 = QVector<QPointF>() << line1.p2() << line2.p1() << line2.p2();
    bool reverseSecondPoly = false;
    if (polygonDirection(poly1) != polygonDirection(poly2)) {
        line2 = QLineF(line2.p2(), line2.p1()); // quick fix to ensure that the shape will be correct (convex)
        reverseSecondPoly = true;
    }
 
    QLineF middleLine = QLineF((line1.p1() + line2.p2())/2, (line1.p2() + line2.p1())/2);
 
    // more difficult version:
    QPainterPath oneEnd = removeGutterOneEndSmart(shape1, index1, shape2, index2, middleLine, false, reverseSecondPoly);
    QPainterPath otherEnd = removeGutterOneEndSmart(shape2, index2, shape1, index1, middleLine, reverseSecondPoly, false);
 
    VectorPath vectorShape1 = VectorPath(shape1);
    VectorPath vectorShape2 = VectorPath(shape2);
    VectorPath vectorOneEnd = VectorPath(oneEnd);
    VectorPath vectorOtherEnd = VectorPath(otherEnd);
 
    VectorPath vectorResultHere = mergeShapesWithGutter(vectorShape1, vectorShape2, vectorOneEnd, vectorOtherEnd, vectorShape1.pathIndexToSegmentIndex(index1), vectorShape2.pathIndexToSegmentIndex(index2), reverseSecondPoly, isSameShape);
    return vectorResultHere.trulySimplified(1e-02).asPainterPath();
 
 
 
}

References KisAlgebra2D::VectorPath::asPainterPath(), getLineFromElements(), mergeShapesWithGutter(), KisAlgebra2D::VectorPath::pathIndexToSegmentIndex(), polygonDirection(), removeGutterOneEndSmart(), and KisAlgebra2D::VectorPath::trulySimplified().

reverseDirection()

QLineF KisAlgebra2D::reverseDirection

(

const QLineF &

line

)

Definition at line 1811 of file kis_algebra_2d.cpp.

{
    return QLineF(line.p2(), line.p1());
}

rightUnitNormal()

template<class T >

T KisAlgebra2D::rightUnitNormal

(

const T &

a

)

Definition at line 142 of file kis_algebra_2d.h.

{
    return -leftUnitNormal(a);
}

References leftUnitNormal().

sampleRectWithPoints() [1/3]

QVector< QPoint > KRITAGLOBAL_EXPORT KisAlgebra2D::sampleRectWithPoints

(

const QRect &

rect

)

Definition at line 509 of file kis_algebra_2d.cpp.

    {
        return sampleRectWithPoints<QRect, QPoint>(rect);
    }

sampleRectWithPoints() [2/3]

QVector< QPointF > KRITAGLOBAL_EXPORT KisAlgebra2D::sampleRectWithPoints

(

const QRectF &

rect

)

Definition at line 514 of file kis_algebra_2d.cpp.

    {
        return sampleRectWithPoints<QRectF, QPointF>(rect);
    }

sampleRectWithPoints() [3/3]

template<class Rect , class Point >

QVector< Point > KisAlgebra2D::sampleRectWithPoints

(

const Rect &

rect

)

Definition at line 487 of file kis_algebra_2d.cpp.

    {
        QVector<Point> points;
 
        Point m1 = 0.5 * (rect.topLeft() + rect.topRight());
        Point m2 = 0.5 * (rect.bottomLeft() + rect.bottomRight());
 
        points << rect.topLeft();
        points << m1;
        points << rect.topRight();
 
        points << 0.5 * (rect.topLeft() + rect.bottomLeft());
        points << 0.5 * (m1 + m2);
        points << 0.5 * (rect.topRight() + rect.bottomRight());
 
        points << rect.bottomLeft();
        points << m2;
        points << rect.bottomRight();
 
        return points;
    }

signPZ()

template<typename T >

T KisAlgebra2D::signPZ

(

T

x

)

Usual sign() function with positive zero

Definition at line 91 of file kis_algebra_2d.h.

              {
    return x >= T(0) ? T(1) : T(-1);
}

signZZ()

template<typename T >

T KisAlgebra2D::signZZ

(

T

x

)

Usual sign() function with zero returning zero

Definition at line 99 of file kis_algebra_2d.h.

              {
    return x == T(0) ? T(0) : x > T(0) ? T(1) : T(-1);
}

simplifyShape()

QPainterPath KisAlgebra2D::simplifyShape

(

const QPainterPath &

path

)

Definition at line 1892 of file kis_algebra_2d.cpp.

                                                     {
 
    VectorPath vector(path);
    return vector.trulySimplified().asPainterPath();
}

References KisAlgebra2D::VectorPath::asPainterPath(), and KisAlgebra2D::VectorPath::trulySimplified().

smallArrow()

QPainterPath KRITAGLOBAL_EXPORT KisAlgebra2D::smallArrow

(

)

Definition at line 129 of file kis_algebra_2d.cpp.

{
    QPainterPath p;
 
    p.moveTo(5, 2);
    p.lineTo(-3, 8);
    p.lineTo(-5, 5);
    p.lineTo( 2, 0);
    p.lineTo(-5,-5);
    p.lineTo(-3,-8);
    p.lineTo( 5,-2);
    p.arcTo(QRectF(3, -2, 4, 4), 90, -180);
 
    return p;
}

References p.

toQTransformStraight()

QTransform KisAlgebra2D::toQTransformStraight ( const Eigen::Matrix3d & m )

inline

Definition at line 769 of file kis_algebra_2d.cpp.

{
    return QTransform(m(0,0), m(0,1), m(0,2),
                      m(1,0), m(1,1), m(1,2),
                      m(2,0), m(2,1), m(2,2));
}

transformAsBase()

QPointF KRITAGLOBAL_EXPORT KisAlgebra2D::transformAsBase	(	const QPointF &	pt,
		const QPointF &	base1,
		const QPointF &	base2 )

Let pt, base1 are two vectors. base1 is uniformly scaled and then rotated into base2 using transformation matrix S * R. The function applies the same transformation to \pt and returns the result.

Definition at line 89 of file kis_algebra_2d.cpp.

                                                                                       {
    qreal len1 = norm(base1);
    if (len1 < 1e-5) return pt;
    qreal sin1 = base1.y() / len1;
    qreal cos1 = base1.x() / len1;
 
    qreal len2 = norm(base2);
    if (len2 < 1e-5) return QPointF();
    qreal sin2 = base2.y() / len2;
    qreal cos2 = base2.x() / len2;
 
    qreal sinD = sin2 * cos1 - cos2 * sin1;
    qreal cosD = cos1 * cos2 + sin1 * sin2;
    qreal scaleD = len2 / len1;
 
    QPointF result;
    result.rx() = scaleD * (pt.x() * cosD - pt.y() * sinD);
    result.ry() = scaleD * (pt.x() * sinD + pt.y() * cosD);
 
    return result;
}

References norm().

transformEllipse()

std::pair< QPointF, QTransform > KRITAGLOBAL_EXPORT KisAlgebra2D::transformEllipse	(	const QPointF &	axes,
		const QTransform &	fullLocalToGlobal )

Definition at line 913 of file kis_algebra_2d.cpp.

{
    KisAlgebra2D::DecomposedMatrix decomposed(fullLocalToGlobal);
    const QTransform localToGlobal =
            decomposed.scaleTransform() *
            decomposed.shearTransform() *
 
            /* decomposed.projectTransform() * */
            /*decomposed.translateTransform() * */
 
            decomposed.rotateTransform();
 
    const QTransform localEllipse = QTransform(1.0 / pow2(axes.x()), 0.0, 0.0,
                                               0.0, 1.0 / pow2(axes.y()), 0.0,
                                               0.0, 0.0, 1.0);
 
 
    const QTransform globalToLocal = localToGlobal.inverted();
 
    Eigen::Matrix3d eqM =
        fromQTransformStraight(globalToLocal *
                               localEllipse *
                               globalToLocal.transposed());
 
//    std::cout << "eqM:" << std::endl << eqM << std::endl;
 
    Eigen::EigenSolver<Eigen::Matrix3d> eigenSolver(eqM);
 
    const Eigen::Matrix3d T = eigenSolver.eigenvalues().real().asDiagonal();
    const Eigen::Matrix3d U = eigenSolver.eigenvectors().real();
 
    const Eigen::Matrix3d Ti = eigenSolver.eigenvalues().imag().asDiagonal();
    const Eigen::Matrix3d Ui = eigenSolver.eigenvectors().imag();
 
    KIS_SAFE_ASSERT_RECOVER_NOOP(Ti.isZero());
    KIS_SAFE_ASSERT_RECOVER_NOOP(Ui.isZero());
    KIS_SAFE_ASSERT_RECOVER_NOOP((U * U.transpose()).isIdentity());
 
//    std::cout << "T:" << std::endl << T << std::endl;
//    std::cout << "U:" << std::endl << U << std::endl;
 
//    std::cout << "Ti:" << std::endl << Ti << std::endl;
//    std::cout << "Ui:" << std::endl << Ui << std::endl;
 
//    std::cout << "UTU':" << std::endl << U * T * U.transpose() << std::endl;
 
    const qreal newA = 1.0 / std::sqrt(T(0,0) * T(2,2));
    const qreal newB = 1.0 / std::sqrt(T(1,1) * T(2,2));
 
    const QTransform newGlobalToLocal = toQTransformStraight(U);
    const QTransform newLocalToGlobal = QTransform::fromScale(-1,-1) *
            newGlobalToLocal.inverted() *
            decomposed.translateTransform();
 
    return std::make_pair(QPointF(newA, newB), newLocalToGlobal);
}

References fromQTransformStraight(), KIS_SAFE_ASSERT_RECOVER_NOOP, pow2(), KisAlgebra2D::DecomposedMatrix::rotateTransform(), KisAlgebra2D::DecomposedMatrix::scaleTransform(), KisAlgebra2D::DecomposedMatrix::shearTransform(), toQTransformStraight(), and KisAlgebra2D::DecomposedMatrix::translateTransform().

tryMergePoints()

bool KisAlgebra2D::tryMergePoints	(	QPainterPath &	path,
		const QPointF &	startPoint,
		const QPointF &	endPoint,
		qreal &	distance,
		qreal	distanceThreshold,
		bool	lastSegment )

Definition at line 1565 of file kis_algebra_2d.cpp.

{
    qreal length = (endPoint - startPoint).manhattanLength();
 
    if (lastSegment || length > distanceThreshold) {
        if (lastSegment) {
            qreal wrappedLength =
                (endPoint - QPointF(path.elementAt(0))).manhattanLength();
 
            if (length < distanceThreshold ||
                wrappedLength < distanceThreshold) {
 
                return true;
            }
        }
 
        distance = 0;
        return false;
    }
 
    distance += length;
 
    if (distance > distanceThreshold) {
        path.lineTo(endPoint);
        distance = 0;
    }
 
    return true;
}

References distance(), and length().

trySimplifyPath()

QPainterPath KRITAGLOBAL_EXPORT KisAlgebra2D::trySimplifyPath	(	const QPainterPath &	path,
		qreal	lengthThreshold )

trySimplifyPath Tries to simplify a QPainterPath

Parameters

path	– path to simplify.
lengthThreshold	– length at which points get merged.

Returns

path with less nodes.

Definition at line 1600 of file kis_algebra_2d.cpp.

{
    QPainterPath newPath;
    QPointF startPoint;
    qreal distance = 0;
 
    int count = path.elementCount();
    for (int i = 0; i < count; i++) {
        QPainterPath::Element e = path.elementAt(i);
        QPointF endPoint = QPointF(e.x, e.y);
 
        switch (e.type) {
        case QPainterPath::MoveToElement:
            newPath.moveTo(endPoint);
            break;
        case QPainterPath::LineToElement:
            if (!tryMergePoints(newPath, startPoint, endPoint,
                                distance, lengthThreshold, i == count - 1)) {
 
                newPath.lineTo(endPoint);
            }
            break;
        case QPainterPath::CurveToElement: {
            Q_ASSERT(i + 2 < count);
 
            if (!tryMergePoints(newPath, startPoint, endPoint,
                                distance, lengthThreshold, i == count - 1)) {
 
                e = path.elementAt(i + 1);
                Q_ASSERT(e.type == QPainterPath::CurveToDataElement);
                QPointF ctrl1 = QPointF(e.x, e.y);
                e = path.elementAt(i + 2);
                Q_ASSERT(e.type == QPainterPath::CurveToDataElement);
                QPointF ctrl2 = QPointF(e.x, e.y);
                newPath.cubicTo(ctrl1, ctrl2, endPoint);
            }
 
            i += 2;
        }
        default:
            ;
        }
        startPoint = endPoint;
    }
 
    return newPath;
}

References distance(), and tryMergePoints().

wrapValue() [1/2]

template<typename T >

T KisAlgebra2D::wrapValue ( T value, T min, T max )

inline

Definition at line 507 of file kis_algebra_2d.h.

                                          {
    return wrapValue(value - min, max - min) + min;
}

References value(), and wrapValue().

wrapValue() [2/2]

template<typename T , typename std::enable_if< std::is_integral< T >::value, T >::type * = nullptr>

T KisAlgebra2D::wrapValue ( T value, T wrapBounds )

inline

Definition at line 482 of file kis_algebra_2d.h.

                                          {
    value %= wrapBounds;
    if (value < 0) {
        value += wrapBounds;
    }
    return value;
}

References value().