From 2aa9303031d9d9f4b123034f4a7fd84f1d1270ba Mon Sep 17 00:00:00 2001 From: "Eduardo M. Fleury" Date: Tue, 27 Oct 2009 18:04:17 -0300 Subject: QGAL: Limit absolute size of anchors and add offset to calculation This commit is groundwork for the support of negative-sized anchors by the simplex solver. The idea is to add to all variables an offset large enough to ensure they are never negative. The implementation limits all variable sizes in the range [-limit, limit] and feed them into the simplex with an offset of "limit". Subtracting this offset later to find out the real values. "limit" is defined as QWIDGETSIZE_MAX for platforms where qreal is double and as QWIDGETSIZE_MAX / 32 when it is float. This is to avoid numerical errors in the simplex solver. This commit also modifies the ASSERT clause inside QSimplex so it becomes less prone to false positives due to numerical errors. Signed-off-by: Eduardo M. Fleury Signed-off-by: Caio Marcelo de Oliveira Filho --- src/gui/graphicsview/qgraphicsanchorlayout_p.cpp | 67 ++++++++++++++++++++---- src/gui/graphicsview/qsimplex_p.h | 2 +- 2 files changed, 57 insertions(+), 12 deletions(-) diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp index d9f4e32..f3a1a69 100644 --- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp +++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp @@ -49,9 +49,17 @@ #endif #include "qgraphicsanchorlayout_p.h" + #ifndef QT_NO_GRAPHICSVIEW QT_BEGIN_NAMESPACE +// To ensure that all variables inside the simplex solver are non-negative, +// we limit the size of anchors in the interval [-limit, limit]. Then before +// sending them to the simplex solver we add "limit" as an offset, so that +// they are actually calculated in the interval [0, 2 * limit] +// To avoid numerical errors in platforms where we use single precision, +// we use a tighter limit for the variables range. +const qreal limit = (sizeof(qreal) == sizeof(double)) ? QWIDGETSIZE_MAX : QWIDGETSIZE_MAX / 32; QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version) : QObjectPrivate(version), layoutPrivate(0), data(0), @@ -2086,6 +2094,25 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs( /*! \internal + Shift all the constraints by a certain amount. This allows us to deal with negative values in + the linear program if they are bounded by a certain limit. Functions should be careful to + call it again with a negative amount, to shift the constraints back. +*/ +static void shiftConstraints(const QList &constraints, qreal amount) +{ + for (int i = 0; i < constraints.count(); ++i) { + QSimplexConstraint *c = constraints.at(i); + qreal multiplier = 0; + foreach (qreal v, c->variables.values()) { + multiplier += v; + } + c->constant += multiplier * amount; + } +} + +/*! + \internal + Calculate the sizes for all anchors which are part of the trunk. This works on top of a (possibly) simplified graph. */ @@ -2106,6 +2133,8 @@ bool QGraphicsAnchorLayoutPrivate::calculateTrunk(Orientation orientation, const QList sizeHintConstraints = constraintsFromSizeHints(variables); QList allConstraints = constraints + sizeHintConstraints; + shiftConstraints(allConstraints, limit); + // Solve min and max size hints qreal min, max; feasible = solveMinMax(allConstraints, path, &min, &max); @@ -2129,6 +2158,7 @@ bool QGraphicsAnchorLayoutPrivate::calculateTrunk(Orientation orientation, const } qDeleteAll(sizeHintConstraints); + shiftConstraints(constraints, -limit); } else { // No Simplex is necessary because the path was simplified all the way to a single @@ -2160,6 +2190,10 @@ bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList &variables) { QList sizeHintConstraints = constraintsFromSizeHints(variables); + + shiftConstraints(sizeHintConstraints, limit); + shiftConstraints(constraints, limit); + bool feasible = solvePreferred(constraints + sizeHintConstraints, variables); if (feasible) { @@ -2174,6 +2208,9 @@ bool QGraphicsAnchorLayoutPrivate::calculateNonTrunk(const QList QGraphicsAnchorLayoutPrivate::constraintsFromSizeHin if (ad->dependency == AnchorData::Slave) continue; - if ((ad->minSize == ad->maxSize) || qFuzzyCompare(ad->minSize, ad->maxSize)) { + // To use negative variables inside simplex, we shift them so the minimum negative value is + // mapped to zero before solving. To make sure that it works, we need to guarantee that the + // variables are all inside a certain boundary. + qreal boundedMin = qBound(-limit, ad->minSize, limit); + qreal boundedMax = qBound(-limit, ad->maxSize, limit); + + if ((boundedMin == boundedMax) || qFuzzyCompare(boundedMin, boundedMax)) { QSimplexConstraint *c = new QSimplexConstraint; c->variables.insert(ad, 1.0); - c->constant = ad->minSize; + c->constant = boundedMin; c->ratio = QSimplexConstraint::Equal; anchorConstraints += c; unboundedProblem = false; } else { QSimplexConstraint *c = new QSimplexConstraint; c->variables.insert(ad, 1.0); - c->constant = ad->minSize; + c->constant = boundedMin; c->ratio = QSimplexConstraint::MoreOrEqual; anchorConstraints += c; @@ -2359,7 +2402,7 @@ QList QGraphicsAnchorLayoutPrivate::constraintsFromSizeHin c = new QSimplexConstraint; c->variables.insert(ad, 1.0); - c->constant = ad->maxSize; + c->constant = boundedMax; c->ratio = QSimplexConstraint::LessOrEqual; anchorConstraints += c; unboundedProblem = false; @@ -2370,7 +2413,8 @@ QList QGraphicsAnchorLayoutPrivate::constraintsFromSizeHin if (unboundedProblem) { QSimplexConstraint *c = new QSimplexConstraint; c->variables.insert(layoutEdge, 1.0); - c->constant = QWIDGETSIZE_MAX; + // The maximum size that the layout can take + c->constant = limit; c->ratio = QSimplexConstraint::LessOrEqual; anchorConstraints += c; } @@ -2691,27 +2735,28 @@ bool QGraphicsAnchorLayoutPrivate::solveMinMax(const QList for (iter = path.negatives.constBegin(); iter != path.negatives.constEnd(); ++iter) objective.variables.insert(*iter, -1.0); + const qreal objectiveOffset = (path.positives.count() - path.negatives.count()) * limit; simplex.setObjective(&objective); // Calculate minimum values - *min = simplex.solveMin(); + *min = simplex.solveMin() - objectiveOffset; // Save sizeAtMinimum results QList variables = getVariables(constraints); for (int i = 0; i < variables.size(); ++i) { AnchorData *ad = static_cast(variables.at(i)); - ad->sizeAtMinimum = ad->result; + ad->sizeAtMinimum = ad->result - limit; Q_ASSERT(ad->sizeAtMinimum >= ad->minSize || qAbs(ad->sizeAtMinimum - ad->minSize) < 0.00000001); } // Calculate maximum values - *max = simplex.solveMax(); + *max = simplex.solveMax() - objectiveOffset; // Save sizeAtMaximum results for (int i = 0; i < variables.size(); ++i) { AnchorData *ad = static_cast(variables.at(i)); - ad->sizeAtMaximum = ad->result; + ad->sizeAtMaximum = ad->result - limit; // Q_ASSERT(ad->sizeAtMaximum <= ad->maxSize || // qAbs(ad->sizeAtMaximum - ad->maxSize) < 0.00000001); } @@ -2756,7 +2801,7 @@ bool QGraphicsAnchorLayoutPrivate::solvePreferred(const QListvariables.insert(ad, 1.0); c->variables.insert(shrinker, 1.0); c->variables.insert(grower, -1.0); - c->constant = ad->prefSize; + c->constant = ad->prefSize + limit; preferredConstraints += c; preferredVariables += grower; @@ -2778,7 +2823,7 @@ bool QGraphicsAnchorLayoutPrivate::solvePreferred(const QListsizeAtPreferred = ad->result; + ad->sizeAtPreferred = ad->result - limit; } // Make sure we delete the simplex solver -before- we delete the diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h index a5816d1..2004471 100644 --- a/src/gui/graphicsview/qsimplex_p.h +++ b/src/gui/graphicsview/qsimplex_p.h @@ -107,7 +107,7 @@ struct QSimplexConstraint Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant)); - if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.00000001) + if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001) return true; switch (ratio) { -- cgit v0.12