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++)
13 if (cols[i].pcol_ == w)
19 Spacing_problem::col_id(const PCol *w)const
21 for (int i=0; i< cols.sz(); i++)
22 if (cols[i].pcol_ == w)
29 Spacing_problem::OK() const
32 Union_find connected(cols.sz());
34 for (int i=0; i < ideals.sz(); i++) {
35 assert(ideals[i]->hooke > 0);
36 int l = col_id(ideals[i]->left);
37 int r = col_id(ideals[i]->right);
38 connected.connect(l,r);
40 for (int i = 0; i < cols.sz(); i++)
43 for (int i = 0; i < cols.sz(); i++) {
45 for (int j =0; j<fixed.sz(); j++)
46 c |= connected.equiv(j,i);
53 Spacing_problem::check_constraints(Vector v) const
56 // mtor << "checking solution " << v << '\n';
57 for (int i=0; i < dim; i++) {
59 if (cols[i].fixed&& ABS(cols[i].fixpos - v(i)) > COLFUDGE) {
65 Real mindist=cols[i-1].minright()
69 Real dif =v(i) - v(i-1)- mindist;
70 bool b = (dif > - COLFUDGE);
78 mtor << "dif= "<<dif<<" fudge= " << COLFUDGE<< " dif >fudge= "<<
81 /* fucks up for unknown reasons */
91 Spacing_problem::check_feasible() const
93 Vector sol(try_initial_solution());
94 return check_constraints(sol);
97 // generate a solution which obeys the min distances and fixed positions
99 Spacing_problem::try_initial_solution() const
103 for (int i=0; i < dim; i++) {
105 initsol(i)=cols[i].fixpos;
107 Real mindist=cols[i-1].minright()
109 assert(mindist >= 0.0);
110 initsol(i)=initsol(i-1)+mindist;
114 // assert(initsol(i) > initsol(i-1));
121 Spacing_problem::find_initial_solution() const
123 Vector v(try_initial_solution());
124 assert(check_constraints(v));
127 // generate the matrices
129 Spacing_problem::make_matrices(Matrix &quad, Vector &lin, Real &c) const
133 for (int j=0; j < ideals.sz(); j++){
134 Idealspacing const*i=ideals[j];
135 int l = col_id(i->left);
136 int r = col_id(i->right);
138 quad(r,r) += i->hooke;
139 quad(r,l) -= i->hooke;
140 quad(l,r) -= i->hooke;
141 quad(l,l) += i->hooke;
143 lin(r) -= i->space*i->hooke;
144 lin(l) += i->space*i->hooke;
150 // put the constraints into the LP problem
152 Spacing_problem::make_constraints(Mixed_qp& lp) const
155 for (int j=0; j < dim; j++) {
156 Colinfo *c=&(cols[j]);
158 lp.add_fixed_var(j,c->fixpos);
166 lp.add_inequality_cons(c1, cols[j-1].minright() +
173 Spacing_problem::solve() const
177 assert(check_feasible());
180 /* optimalisatiefunctie */
181 Mixed_qp lp(cols.sz());
182 make_matrices(lp.quad,lp.lin, lp.const_term);
183 make_constraints(lp);
184 Vector start=find_initial_solution();
185 Vector sol(lp.solve(start));
186 if (!check_constraints(sol)) {
187 WARN << "solution doesn't satisfy constraints.\n" ;
191 svec<Real> posns(sol);
192 posns.add(lp.eval(sol));
197 add one column to the problem.
200 Spacing_problem::add_column(const PCol *col, bool fixed, Real fixpos)
211 Spacing_problem::add_ideal(const Idealspacing *i)
213 const PCol *l =i->left;
214 const PCol *r= i->right;
216 if (!contains(l) || !contains(r)) {
223 Spacing_problem::print_ideal(const Idealspacing*id)const
226 int l = col_id(id->left);
227 int r = col_id(id->right);
229 mtor << "between " << l <<","<<r<<":" ;
235 Spacing_problem::print() const
238 for (int i=0; i < cols.sz(); i++) {
239 mtor << "col " << i<<' ';
242 for (int i=0; i < ideals.sz(); i++) {
243 print_ideal(ideals[i]);
250 Colinfo::print() const
255 mtor << "fixed at " << fixpos<<", ";
257 mtor << "[" << minleft() << ", " << minright() << "]";