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
|
/*
* Authors:
* Tim Dwyer <tgdwyer@gmail.com>
*
* Copyright (C) 2005 Authors
*
* Released under GNU LGPL. Read the file 'COPYING' for more information.
*/
#ifndef SEEN_REMOVEOVERLAP_BLOCK_H
#define SEEN_REMOVEOVERLAP_BLOCK_H
#include <vector>
#include <iostream>
template <class T> class PairingHeap;
namespace vpsc {
class Variable;
class Constraint;
/**
* A block is a group of variables that must be moved together to improve
* the goal function without violating already active constraints.
* The variables in a block are spanned by a tree of active constraints.
*/
class Block
{
typedef std::vector<Variable*> Variables;
typedef std::vector<Constraint*>::iterator Cit;
typedef std::vector<Variable*>::iterator Vit;
friend std::ostream& operator <<(std::ostream &os,const Block &b);
public:
Variables *vars;
double posn;
double weight;
double wposn;
Block(Variable* const v=NULL);
virtual ~Block(void);
/**
* finds the constraint with the minimum lagrange multiplier, that is, the constraint
* that most wants to split
*/
Constraint* findMinLM();
Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
Constraint* findMinInConstraint();
Constraint* findMinOutConstraint();
void deleteMinInConstraint();
void deleteMinOutConstraint();
double desiredWeightedPosition();
/**
* Merges b into this block across c. Can be either a
* right merge or a left merge
* @param b block to merge into this
* @param c constraint being merged
* @param distance separation required to satisfy c
*/
void merge(Block *b, Constraint *c, double dist);
void merge(Block *b, Constraint *c);
void mergeIn(Block *b);
void mergeOut(Block *b);
/**
* Creates two new blocks, l and r, and splits this block across constraint c,
* placing the left subtree of constraints (and associated variables) into l
* and the right into r.
*/
void split(Block *&l, Block *&r, Constraint *c);
/**
* Block needs to be split because of a violated constraint between vl and vr.
* We need to search the active constraint tree between l and r and find the constraint
* with min lagrangrian multiplier and split at that point.
* Returns the split constraint
*/
Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
void setUpInConstraints();
void setUpOutConstraints();
/**
* Computes the cost (squared euclidean distance from desired positions) of the
* current positions for variables in this block
*/
double cost();
bool deleted;
long timeStamp;
PairingHeap<Constraint*> *in;
PairingHeap<Constraint*> *out;
bool isActiveDirectedPathBetween(Variable* u, Variable *v);
private:
typedef enum {NONE, LEFT, RIGHT} Direction;
typedef std::pair<double, Constraint*> Pair;
void reset_active_lm(Variable* const v, Variable* const u);
double compute_dfdv(Variable* const v, Variable* const u,
Constraint *&min_lm);
Pair compute_dfdv_between(
Variable*, Variable* const, Variable* const,
const Direction, bool);
bool canFollowLeft(Constraint *c, const Variable* const last);
bool canFollowRight(Constraint *c, const Variable* const last);
void populateSplitBlock(Block *b, Variable* const v, Variable* const u);
void addVariable(Variable* const v);
void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
};
}
#endif // SEEN_REMOVEOVERLAP_BLOCK_H
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
|
