diff options
Diffstat (limited to '')
-rw-r--r-- | src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.cpp | 590 |
1 files changed, 590 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.cpp b/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.cpp new file mode 100644 index 0000000..69502d0 --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.cpp @@ -0,0 +1,590 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libcola - A library providing force-directed network layout using the + * stress-majorization method subject to separation constraints. + * + * Copyright (C) 2010-2014 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Michael Wybrow + * +*/ + +#include <sstream> + +#include "libcola/cola.h" +#include "libcola/compound_constraints.h" +#include "libcola/cc_nonoverlapconstraints.h" + +using vpsc::XDIM; +using vpsc::YDIM; + + +namespace cola { + +//----------------------------------------------------------------------------- +// NonOverlapConstraintExemptions code +//----------------------------------------------------------------------------- + +NonOverlapConstraintExemptions::NonOverlapConstraintExemptions() +{ +} + +void NonOverlapConstraintExemptions::addExemptGroupOfNodes( + ListOfNodeIndexes listOfNodeGroups) +{ + m_exempt_pairs.clear(); + + const size_t listSize = listOfNodeGroups.size(); + for (size_t l = 0; l < listSize; ++l) + { + NodeIndexes ids(listOfNodeGroups[l]); + + // Sort and remove duplicate IDs for this group. + std::sort(ids.begin(), ids.end()); + NodeIndexes::iterator last = std::unique(ids.begin(), ids.end()); + ids.erase(last, ids.end()); + + // Add all combinations of pairs of IDs for this group to m_exempt_pairs + const size_t idsSize = ids.size(); + for (size_t i = 0; i < idsSize; ++i) + { + for (size_t j = i + 1; j < idsSize; ++j) + { + m_exempt_pairs.insert(ShapePair(ids[i], ids[j])); + } + } + + } +} + +bool NonOverlapConstraintExemptions::shapePairIsExempt( + ShapePair shapePair) const +{ + return (m_exempt_pairs.count(shapePair) == 1); +} + +//----------------------------------------------------------------------------- +// NonOverlapConstraints code +//----------------------------------------------------------------------------- + +NonOverlapConstraints::NonOverlapConstraints( + NonOverlapConstraintExemptions *exemptions, unsigned int priority) + : CompoundConstraint(vpsc::HORIZONTAL, priority), + pairInfoListSorted(false), + initialSortCompleted(false), + m_exemptions(exemptions) +{ + // All work is done by repeated addShape() calls. +} + +void NonOverlapConstraints::addShape(unsigned id, double halfW, double halfH, + unsigned int group, std::set<unsigned> exemptions) +{ + // Setup pairInfos for all other shapes. + for (std::map<unsigned, OverlapShapeOffsets>::iterator curr = + shapeOffsets.begin(); curr != shapeOffsets.end(); ++curr) + { + unsigned otherId = curr->first; + if ((shapeOffsets[otherId].group == group) && (id != otherId) && exemptions.count(otherId)==0) + { + if (m_exemptions && + m_exemptions->shapePairIsExempt(ShapePair(otherId, id))) + { + continue; + } + + // Apply non-overlap only to objects in the same group (cluster). + pairInfoList.push_back(ShapePairInfo(otherId, id)); + } + } + + shapeOffsets[id] = OverlapShapeOffsets(id, halfW, halfH, group); +} + +void NonOverlapConstraints::resizeShape(unsigned id, double halfW, double halfH) +{ + OverlapShapeOffsets oso = shapeOffsets[id]; + oso.resize(halfW, halfH); +} + +void NonOverlapConstraints::removeShape(unsigned id) +{ + // Remove the OverlapShapeOffsets object for this id. + shapeOffsets.erase(id); + // Remove all ShapePairInfo objects having this id as one of their two indices. + std::list<ShapePairInfo>::iterator it = pairInfoList.begin(); + while (it != pairInfoList.end()) { + ShapePairInfo spi = *it; + if (spi.varIndex1==id || spi.varIndex2==id) { + it = pairInfoList.erase(it); // now it points to next list element after one erased + } else { + it++; + } + } +} + +// This is expected to be called after all addNode calls. +void NonOverlapConstraints::addCluster(Cluster *cluster, unsigned int group) +{ + unsigned id = cluster->clusterVarId; + // Setup pairInfos for all other shapes. + for (std::map<unsigned, OverlapShapeOffsets>::iterator curr = + shapeOffsets.begin(); curr != shapeOffsets.end(); ++curr) + { + unsigned otherId = curr->first; + if (shapeOffsets[otherId].group != group) + { + // Don't apply if not in same group. + continue; + } + if (cluster->nodes.count(otherId) > 0) + { + // Don't apply non-overlap to child nodes. + continue; + } + if (m_cluster_cluster_exemptions.count(ShapePair(id, otherId)) > 0) + { + // Don't apply if exempt due to non-strict cluster hierarchy. + continue; + } + // Apply non-overlap only to objects in the same group (cluster). + pairInfoList.push_back(ShapePairInfo(otherId, id)); + } + + shapeOffsets[id] = OverlapShapeOffsets(id, cluster, group); +} + + +void NonOverlapConstraints::setClusterClusterExemptions( + std::set<ShapePair> exemptions) +{ + m_cluster_cluster_exemptions = exemptions; +} + +void NonOverlapConstraints::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); +} + +void NonOverlapConstraints::computeOverlapForShapePairInfo(ShapePairInfo& info, + vpsc::Variables vs[]) +{ + OverlapShapeOffsets& shape1 = shapeOffsets[info.varIndex1]; + OverlapShapeOffsets& shape2 = shapeOffsets[info.varIndex2]; + + double xPos1 = vs[0][info.varIndex1]->finalPosition; + double xPos2 = vs[0][info.varIndex2]->finalPosition; + double yPos1 = vs[1][info.varIndex1]->finalPosition; + double yPos2 = vs[1][info.varIndex2]->finalPosition; + + double left1 = xPos1 - shape1.halfDim[0]; + double right1 = xPos1 + shape1.halfDim[0]; + double bottom1 = yPos1 - shape1.halfDim[1]; + double top1 = yPos1 + shape1.halfDim[1]; + + if (shape1.cluster) + { + COLA_ASSERT(shape1.halfDim[0] == 0); + COLA_ASSERT(shape1.halfDim[1] == 0); + COLA_ASSERT(info.varIndex1 + 1 < vs[0].size()); + right1 = vs[0][info.varIndex1 + 1]->finalPosition; + COLA_ASSERT(info.varIndex1 + 1 < vs[1].size()); + top1 = vs[1][info.varIndex1 + 1]->finalPosition; + left1 -= shape1.rectPadding.min(XDIM); + bottom1 -= shape1.rectPadding.min(YDIM); + right1 += shape1.rectPadding.max(XDIM); + top1 += shape1.rectPadding.max(YDIM); + } + + double left2 = xPos2 - shape2.halfDim[0]; + double right2 = xPos2 + shape2.halfDim[0]; + double bottom2 = yPos2 - shape2.halfDim[1]; + double top2 = yPos2 + shape2.halfDim[1]; + + if (shape2.cluster) + { + COLA_ASSERT(shape2.halfDim[0] == 0); + COLA_ASSERT(shape2.halfDim[1] == 0); + COLA_ASSERT(info.varIndex2 + 1 < vs[0].size()); + right2 = vs[0][info.varIndex2 + 1]->finalPosition; + COLA_ASSERT(info.varIndex2 + 1 < vs[1].size()); + top2 = vs[1][info.varIndex2 + 1]->finalPosition; + left2 -= shape2.rectPadding.min(XDIM); + bottom2 -= shape2.rectPadding.min(YDIM); + right2 += shape2.rectPadding.max(XDIM); + top2 += shape2.rectPadding.max(YDIM); + } + + // If lr < 0, then left edge of shape1 is on the left + // of right edge of shape2. + double spaceR = left2 - right1; + double spaceL = left1 - right2; + // Below + double spaceA = bottom2 - top1; + // Above + double spaceB = bottom1 - top2; + + double costL = 0; + double costR = 0; + double costB = 0; + double costA = 0; + info.overlapMax = 0; + bool xOverlap = false; + bool yOverlap = false; + if ((spaceR < 0) && (spaceL < 0)) + { + costL = std::max(-spaceL, 0.0); + costR = std::max(-spaceR, 0.0); + + info.overlapMax = std::max(costL, costR); + + xOverlap = true; + } + if ((spaceB < 0) && (spaceA < 0)) + { + costB = std::max(-spaceB, 0.0); + costA = std::max(-spaceA, 0.0); + + info.overlapMax = std::max(info.overlapMax, costB); + info.overlapMax = std::max(info.overlapMax, costA); + + yOverlap = true; + } + + if (!xOverlap || !yOverlap) + { + // Overlap must occur in both dimensions. + info.overlapMax = 0; + } + else + { + // Increase the overlap value for overlap where one shape is fully + // within the other. This results in these situations being + // resolved first and will sometimes prevent us from committing to + // bad non-overlap choices and getting stuck later. + // XXX Another alternative would be to look at previously added + // non-overlap constraints that become unsatified and then + // allow them to be rechosen maybe just a single time. + double penalty = 100000; + if ( (left1 >= left2) && (right1 <= right2) && + (bottom1 >= bottom2) && (top1 <= top2) ) + { + // Shape 1 is inside shape 2. + double smallShapeArea = (right1 - left1) * (top1 - bottom1); + info.overlapMax = penalty + smallShapeArea; + } + else if ( (left2 >= left1) && (right2 <= right1) && + (bottom2 >= bottom1) && (top2 <= top1) ) + { + // Shape 2 is inside shape 1. + double smallShapeArea = (right2 - left2) * (top2 - bottom2); + info.overlapMax = penalty + smallShapeArea; + } + // There is overlap. + //printf("[%02d][%02d] L %g, R %G, B %g, A %g\n", info.varIndex1, + // info.varIndex2, spaceL, spaceR, spaceB, spaceA); + } +} + +std::string NonOverlapConstraints::toString(void) const +{ + std::ostringstream stream; + stream << "NonOverlapConstraints()"; + return stream.str(); +} + +void NonOverlapConstraints::computeAndSortOverlap(vpsc::Variables vs[]) +{ + for (std::list<ShapePairInfo>::iterator curr = pairInfoList.begin(); + curr != pairInfoList.end(); ++curr) + { + ShapePairInfo& info = static_cast<ShapePairInfo&> (*curr); + + if (info.processed) + { + // Once we reach the processed nodes, which will always be at + // the back, we can some computing overlap since this no longer + // matters. + break; + } + computeOverlapForShapePairInfo(info, vs); + } + pairInfoList.sort(); +} + + +void NonOverlapConstraints::markCurrSubConstraintAsActive(const bool satisfiable) +{ + ShapePairInfo info = pairInfoList.front(); + pairInfoList.pop_front(); + + info.processed = true; + info.satisfied = satisfiable; + info.overlapMax = 0; + + pairInfoList.push_back(info); + pairInfoListSorted = false; +} + + + +SubConstraintAlternatives +NonOverlapConstraints::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + SubConstraintAlternatives alternatives; + if (initialSortCompleted == false) + { + // Initally sort the shape pair info objects. + computeAndSortOverlap(vs); + pairInfoListSorted = true; + initialSortCompleted = true; + } + + // Take the first in the list. + ShapePairInfo& info = pairInfoList.front(); + if (pairInfoListSorted == false) + { + // Only need to compute if not sorted. + computeOverlapForShapePairInfo(info, vs); + } + + if (info.overlapMax == 0) + { + if (pairInfoListSorted) + { + // Seeing no overlap in the sorted list means we have solved + // all non-overlap. Nothing more to do. + _currSubConstraintIndex = pairInfoList.size(); + return alternatives; + } + computeAndSortOverlap(vs); + pairInfoListSorted = true; + return alternatives; + } + OverlapShapeOffsets& shape1 = shapeOffsets[info.varIndex1]; + OverlapShapeOffsets& shape2 = shapeOffsets[info.varIndex2]; + + double xSepL = shape1.halfDim[0] + shape2.halfDim[0]; + double ySepB = shape1.halfDim[1] + shape2.halfDim[1]; + double xSepR = xSepL; + double ySepT = ySepB; + + unsigned varIndexL1 = info.varIndex1; + unsigned varIndexL2 = info.varIndex2; + // Clusters have left and right variables, instead of centre variables. + unsigned varIndexR1 = + (shape1.cluster) ? (info.varIndex1 + 1) : info.varIndex1; + unsigned varIndexR2 = + (shape2.cluster) ? (info.varIndex2 + 1) : info.varIndex2; + + assertValidVariableIndex(vs[XDIM], varIndexL1); + assertValidVariableIndex(vs[YDIM], varIndexL1); + assertValidVariableIndex(vs[XDIM], varIndexR1); + assertValidVariableIndex(vs[YDIM], varIndexR1); + assertValidVariableIndex(vs[XDIM], varIndexL2); + assertValidVariableIndex(vs[YDIM], varIndexL2); + assertValidVariableIndex(vs[XDIM], varIndexR2); + assertValidVariableIndex(vs[YDIM], varIndexR2); + + // + double xSepCostL = xSepL; + double xSepCostR = xSepR; + double ySepCostB = ySepB; + double ySepCostT = ySepT; + + double desiredX1 = vs[XDIM][info.varIndex1]->desiredPosition; + double desiredY1 = vs[YDIM][info.varIndex1]->desiredPosition; + double desiredX2 = vs[XDIM][info.varIndex2]->desiredPosition; + double desiredY2 = vs[YDIM][info.varIndex2]->desiredPosition; + + // Clusters have two variables instead of a centre variable -- one for + // each boundary side, so we need to remap the desired positions and the + // separations values for the purposes of cost sorting. + if (shape1.cluster) + { + double width = vs[XDIM][info.varIndex1 + 1]->finalPosition - + vs[XDIM][info.varIndex1]->finalPosition; + double height = vs[YDIM][info.varIndex1 + 1]->finalPosition - + vs[YDIM][info.varIndex1]->finalPosition; + desiredX1 += width / 2; + desiredY1 += height / 2; + xSepCostL += width / 2; + xSepCostR += width / 2; + ySepCostB += height / 2; + ySepCostT += height / 2; + xSepL += shape1.rectPadding.min(XDIM); + xSepR += shape1.rectPadding.max(XDIM); + ySepB += shape1.rectPadding.min(YDIM); + ySepT += shape1.rectPadding.max(YDIM); + } + if (shape2.cluster) + { + double width = vs[XDIM][info.varIndex2 + 1]->finalPosition - + vs[XDIM][info.varIndex2]->finalPosition; + double height = vs[YDIM][info.varIndex2 + 1]->finalPosition - + vs[YDIM][info.varIndex2]->finalPosition; + desiredX2 += width / 2; + desiredY2 += height / 2; + xSepCostL += width / 2; + xSepCostR += width / 2; + ySepCostB += height / 2; + ySepCostT += height / 2; + xSepL += shape2.rectPadding.min(XDIM); + xSepR += shape2.rectPadding.max(XDIM); + ySepB += shape2.rectPadding.min(YDIM); + ySepT += shape2.rectPadding.max(YDIM); + } + + // We get problems with numerical inaccuracy in the topology constraint + // generation, so make sure the rectagles are separated by at least a + // tiny distance. + xSepL += 10e-10; + xSepR += 10e-10; + ySepB += 10e-10; + ySepT += 10e-10; + + // Compute the cost to move in each direction based on the + // desired positions for the two objects. + double costR = xSepCostR - (desiredX2 - desiredX1); + double costL = xSepCostL - (desiredX1 - desiredX2); + + double costT = ySepCostT - (desiredY2 - desiredY1); + double costB = ySepCostB - (desiredY1 - desiredY2); + + vpsc::Constraint constraintL(vs[XDIM][varIndexR2], + vs[XDIM][varIndexL1], xSepL); + alternatives.push_back(SubConstraint(XDIM, constraintL, costL)); + + vpsc::Constraint constraintR(vs[XDIM][varIndexR1], + vs[XDIM][varIndexL2], xSepR); + alternatives.push_back(SubConstraint(XDIM, constraintR, costR)); + + vpsc::Constraint constraintB(vs[YDIM][varIndexR2], + vs[YDIM][varIndexL1], ySepB); + alternatives.push_back(SubConstraint(YDIM, constraintB, costB)); + + vpsc::Constraint constraintT(vs[YDIM][varIndexR1], + vs[YDIM][varIndexL2], ySepT); + alternatives.push_back(SubConstraint(YDIM, constraintT, costT)); + + //fprintf(stderr, "===== NONOVERLAP ALTERNATIVES -====== \n"); + + return alternatives; +} + + +bool NonOverlapConstraints::subConstraintsRemaining(void) const +{ + //printf(". %3d of %4d\n", _currSubConstraintIndex, pairInfoList.size()); + return _currSubConstraintIndex < pairInfoList.size(); +} + + +void NonOverlapConstraints::markAllSubConstraintsAsInactive(void) +{ + for (std::list<ShapePairInfo>::iterator curr = pairInfoList.begin(); + curr != pairInfoList.end(); ++curr) + { + ShapePairInfo& info = (*curr); + info.satisfied = false; + info.processed = false; + } + _currSubConstraintIndex = 0; + initialSortCompleted = false; +} + + +void NonOverlapConstraints::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& cs, + std::vector<vpsc::Rectangle*>& boundingBoxes) +{ + for (std::list<ShapePairInfo>::iterator info = pairInfoList.begin(); + info != pairInfoList.end(); ++info) + { + assertValidVariableIndex(vs, info->varIndex1); + assertValidVariableIndex(vs, info->varIndex2); + + OverlapShapeOffsets& shape1 = shapeOffsets[info->varIndex1]; + OverlapShapeOffsets& shape2 = shapeOffsets[info->varIndex2]; + + vpsc::Rectangle rect1 = (shape1.cluster) ? + shape1.cluster->bounds : *boundingBoxes[info->varIndex1]; + vpsc::Rectangle rect2 = (shape2.cluster) ? + shape2.cluster->bounds : *boundingBoxes[info->varIndex2]; + + double pos1 = rect1.getCentreD(dim); + double pos2 = rect2.getCentreD(dim); + + double below1 = shape1.halfDim[dim]; + double above1 = shape1.halfDim[dim]; + double below2 = shape2.halfDim[dim]; + double above2 = shape2.halfDim[dim]; + + vpsc::Variable *varLeft1 = nullptr; + vpsc::Variable *varLeft2 = nullptr; + vpsc::Variable *varRight1 = nullptr; + vpsc::Variable *varRight2 = nullptr; + if (shape1.cluster) + { + // Must constraint to cluster boundary variables. + varLeft1 = vs[shape1.cluster->clusterVarId]; + varRight1 = vs[shape1.cluster->clusterVarId + 1]; + rect1 = shape1.cluster->margin().rectangleByApplyingBox(rect1); + below1 = shape1.cluster->margin().min(dim); + above1 = shape1.cluster->margin().max(dim); + } + else + { + // Must constrain to rectangle centre postion variable. + varLeft1 = varRight1 = vs[info->varIndex1]; + } + + if (shape2.cluster) + { + // Must constraint to cluster boundary variables. + varLeft2 = vs[shape2.cluster->clusterVarId]; + varRight2 = vs[shape2.cluster->clusterVarId + 1]; + rect2 = shape2.cluster->margin().rectangleByApplyingBox(rect2); + below2 = shape2.cluster->margin().min(dim); + above2 = shape2.cluster->margin().max(dim); + } + else + { + // Must constrain to rectangle centre postion variable. + varLeft2 = varRight2 = vs[info->varIndex2]; + } + + if (rect1.overlapD(!dim, &rect2) > 0.0005) + { + vpsc::Constraint *constraint = nullptr; + if (pos1 < pos2) + { + constraint = new vpsc::Constraint(varRight1, varLeft2, + above1 + below2); + } + else + { + constraint = new vpsc::Constraint(varRight2, varLeft1, + below1 + above2); + } + constraint->creator = this; + cs.push_back(constraint); + } + } +} + + +} // namespace cola |