2 #include "linespace.hh"
5 #include "unionfind.hh"
7 const Real COLFUDGE=1e-3;
8 //#define COLFUDGE 1e-3
10 Spacing_problem::contains(const PCol *w)
12 for (int i=0; i< cols.sz(); i++)
19 Spacing_problem::col_id(const PCol *w)const
21 for (int i=0; i< cols.sz(); i++)
28 Spacing_problem::OK() const
31 Union_find connected(cols.sz());
33 for (int i=0; i < ideals.sz(); i++) {
34 assert(ideals[i]->hooke > 0);
35 int l = col_id(ideals[i]->left);
36 int r = col_id(ideals[i]->right);
37 connected.connect(l,r);
40 for (int i = 0; i < cols.sz(); i++) {
41 assert( connected.equiv(0,i));
47 Spacing_problem::check_constraints(Vector v) const
50 // mtor << "checking solution " << v << '\n';
51 for (int i=0; i < dim; i++) {
53 if (cols[i].fixed&& ABS(cols[i].fixpos - v(i)) > COLFUDGE) {
59 Real mindist=cols[i-1].minright()
63 Real dif =v(i) - v(i-1)- mindist;
64 bool b = (dif > - COLFUDGE);
72 mtor << "dif= "<<dif<<" fudge= " << COLFUDGE<< " dif >fudge= "<<
75 /* fucks up for unknown reasons */
85 Spacing_problem::check_feasible() const
87 Vector sol(try_initial_solution());
88 return check_constraints(sol);
91 // generate a solution which obeys the min distances and fixed positions
93 Spacing_problem::try_initial_solution() const
97 for (int i=0; i < dim; i++) {
99 initsol(i)=cols[i].fixpos;
101 Real mindist=cols[i-1].minright()
103 assert(mindist >= 0.0);
104 initsol(i)=initsol(i-1)+mindist;
108 // assert(initsol(i) > initsol(i-1));
115 Spacing_problem::find_initial_solution() const
117 Vector v(try_initial_solution());
118 assert(check_constraints(v));
121 // generate the matrices
123 Spacing_problem::make_matrices(Matrix &quad, Vector &lin, Real &c) const
127 for (int j=0; j < ideals.sz(); j++){
128 Idealspacing const*i=ideals[j];
129 int l = col_id(i->left);
130 int r = col_id(i->right);
132 quad(r,r) += i->hooke;
133 quad(r,l) -= i->hooke;
134 quad(l,r) -= i->hooke;
135 quad(l,l) += i->hooke;
137 lin(r) -= i->space*i->hooke;
138 lin(l) += i->space*i->hooke;
144 // put the constraints into the LP problem
146 Spacing_problem::make_constraints(Mixed_qp& lp) const
149 for (int j=0; j < dim; j++) {
150 Colinfo *c=&(cols[j]);
152 lp.add_fixed_var(j,c->fixpos);
160 lp.add_inequality_cons(c1, cols[j-1].minright() +
167 Spacing_problem::solve() const
171 assert(check_feasible());
174 /* optimalisatiefunctie */
175 Mixed_qp lp(cols.sz());
176 make_matrices(lp.quad,lp.lin, lp.const_term);
177 make_constraints(lp);
178 Vector start=find_initial_solution();
179 Vector sol(lp.solve(start));
180 if (!check_constraints(sol)) {
181 WARN << "solution doesn't satisfy constraints.\n" ;
185 svec<Real> posns(sol);
186 posns.add(lp.eval(sol));
191 add one column to the problem.
194 Spacing_problem::add_column(const PCol *col, bool fixed, Real fixpos)
205 Spacing_problem::add_ideal(const Idealspacing *i)
207 const PCol *l =i->left;
208 const PCol *r= i->right;
210 if (!contains(l) || !contains(r)) {
217 Spacing_problem::print_ideal(const Idealspacing*id)const
220 int l = col_id(id->left);
221 int r = col_id(id->right);
223 mtor << "between " << l <<","<<r<<":" ;
228 Spacing_problem::print() const
231 for (int i=0; i < cols.sz(); i++) {
232 mtor << "col " << i<<' ';
235 for (int i=0; i < ideals.sz(); i++) {
236 print_ideal(ideals[i]);
243 Colinfo::print() const
248 mtor << "fixed at " << fixpos<<", ";
250 mtor << "[" << minleft() << ", " << minright() << "]";