diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.h')
| -rw-r--r-- | src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.h | 210 |
1 files changed, 210 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.h b/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.h new file mode 100644 index 0000000..0904ece --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/cc_nonoverlapconstraints.h @@ -0,0 +1,210 @@ +/* + * 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 + * +*/ + +#ifndef COLA_CC_NONOVERLAPCONSTRAINTS_H +#define COLA_CC_NONOVERLAPCONSTRAINTS_H + +#include <vector> + +#include "libcola/cola.h" +#include "libcola/compound_constraints.h" +#include "libcola/shapepair.h" + +namespace vpsc { +class Rectangle; +} + +namespace cola { + +class Cluster; + +class OverlapShapeOffsets : public SubConstraintInfo +{ + public: + OverlapShapeOffsets(unsigned ind, double xOffset, double yOffset, + unsigned int group) + : SubConstraintInfo(ind), + cluster(nullptr), + rectPadding(0), + group(group) + { + halfDim[0] = xOffset; + halfDim[1] = yOffset; + } + OverlapShapeOffsets(unsigned ind, Cluster *cluster, unsigned int group) + : SubConstraintInfo(ind), + cluster(cluster), + rectPadding(cluster->margin()), + group(group) + { + halfDim[0] = 0; + halfDim[1] = 0; + } + OverlapShapeOffsets() + : SubConstraintInfo(1000000), + cluster(nullptr), + rectPadding(0) + { + } + bool usesClusterBounds(void) const + { + return (cluster && !cluster->clusterIsFromFixedRectangle()); + } + void resize(double xOffset, double yOffset) + { + halfDim[0] = xOffset; + halfDim[1] = yOffset; + } + Cluster *cluster; + double halfDim[2]; // Half width and height values. + Box rectPadding; // Used for cluster padding. + unsigned int group; +}; + + +class ShapePairInfo +{ + public: + ShapePairInfo(unsigned ind1, unsigned ind2, unsigned ord = 1) + : order(ord), + satisfied(false), + processed(false) + { + COLA_ASSERT(ind1 != ind2); + // Assign the lesser value to varIndex1. + varIndex1 = (ind1 < ind2) ? ind1 : ind2; + // Assign the greater value to varIndex2. + varIndex2 = (ind1 > ind2) ? ind1 : ind2; + } + bool operator<(const ShapePairInfo& rhs) const + { + // Make sure the processed ones are at the end after sorting. + int processedInt = processed ? 1 : 0; + int rhsProcessedInt = rhs.processed ? 1 : 0; + if (processedInt != rhsProcessedInt) + { + return processedInt < rhsProcessedInt; + } + // Use cluster ordering for primary sorting. + if (order != rhs.order) + { + return order < rhs.order; + } + return overlapMax > rhs.overlapMax; + } + unsigned short order; + unsigned short varIndex1; + unsigned short varIndex2; + bool satisfied; + bool processed; + double overlapMax; +}; + + +// Stores IDs of all rectangles exempt from non-overlap constraints. +class NonOverlapConstraintExemptions { + public: + NonOverlapConstraintExemptions(); + void addExemptGroupOfNodes(ListOfNodeIndexes listOfNodeGroups); + bool shapePairIsExempt(ShapePair shapePair) const; + std::set<ShapePair> getExemptPairs(void) {return m_exempt_pairs;} + + private: + std::set<ShapePair> m_exempt_pairs; +}; + +// Non-overlap constraints prevent a set of given shapes from overlapping. +class NonOverlapConstraints : public CompoundConstraint { + public: + NonOverlapConstraints(NonOverlapConstraintExemptions *exemptions, + unsigned int priority = PRIORITY_NONOVERLAP); + //! @brief Use this method to add all the shapes between which you want + //! to prevent overlaps. + //! @param id This will be used as index into both the vars and + //! boundingBoxes vectors when you call the + //! generateSeparationConstraints method. + //! @param halfW If you add two shapes with half-widths hwi and hwj, then + //! if a horizontal separation constraint is generated between + //! them its gap will be hwi + hwj. + //! @param halfH Similar to halfW. + //! @param group Assign a group number to this shape. A separation constraint + //! will be generated between two shapes only if they belong to + //! the same group. This is useful for clusters. + //! @param exemptions Optional set of IDs of shapes to be skipped, i.e. such that + //! a separation constraint should /not/ be generated between + //! that shape and the one being added. + void addShape(unsigned id, double halfW, double halfH, + unsigned int group = 1, std::set<unsigned> exemptions = std::set<unsigned>()); + void resizeShape(unsigned id, double halfW, double halfH); + void removeShape(unsigned id); + void addCluster(Cluster *cluster, unsigned int group); + void computeAndSortOverlap(vpsc::Variables vs[]); + void markCurrSubConstraintAsActive(const bool satisfiable); + void markAllSubConstraintsAsInactive(void); + bool subConstraintsRemaining(void) const; + SubConstraintAlternatives getCurrSubConstraintAlternatives( + vpsc::Variables vs[]); + std::string toString(void) const; + void setClusterClusterExemptions(std::set<ShapePair> exemptions); + + void generateVariables(const vpsc::Dim dim, vpsc::Variables& vars); + void generateSeparationConstraints(const vpsc::Dim dim, + vpsc::Variables& vars, vpsc::Constraints& gcs); + //! @brief Generate separation constraints in one dimension, to ensure + //! nonoverlap between all shapes in that dimension. + //! @param dim The dimension for which to generate constraints. + //! @param vars The variables between which the constraints will hold. + //! @param gcs The generated constraints will be added to this vector. + //! @param boundingBoxes For those id's corresponding to added shapes + //! (not clusters), the rectangle boundingBox[id] will be consulted + //! in order to determine: + //! (1) whether a separation constraint is called for, i.e. whether the + //! shapes in question span any of the same coods in the dimension + //! opposite to dim; + //! (2) which var is left and which is right in the separation constraint. + //! Note however that the dimensions of the boundingBoxes do NOT determine + //! the gaps of the separation constraints, which are instead based on the + //! half-width and half-height passed when adding the shapes. + void generateSeparationConstraints(const vpsc::Dim dim, + vpsc::Variables& vars, vpsc::Constraints& gcs, + std::vector<vpsc::Rectangle*>& boundingBoxes); + + private: + void computeOverlapForShapePairInfo(ShapePairInfo& info, + vpsc::Variables vs[]); + + std::list<ShapePairInfo> pairInfoList; + std::map<unsigned, OverlapShapeOffsets> shapeOffsets; + bool pairInfoListSorted; + bool initialSortCompleted; + + // Cluster variables + size_t clusterVarStartIndex; + size_t currClusterIndex; + size_t clusterMode; + + NonOverlapConstraintExemptions *m_exemptions; + std::set<ShapePair> m_cluster_cluster_exemptions; +}; + +} // namespace cola +#endif // COLA_CC_NONOVERLAPCONSTRAINTS |