1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
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
|
