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)
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);
39 for (int i = 0; i < cols.sz(); i++)
42 for (int i = 0; i < cols.sz(); i++) {
44 for (int j =0; j<fixed.sz(); j++)
45 c |= connected.equiv(j,i);
52 Spacing_problem::check_constraints(Vector v) const
55 // mtor << "checking solution " << v << '\n';
56 for (int i=0; i < dim; i++) {
58 if (cols[i].fixed&& ABS(cols[i].fixpos - v(i)) > COLFUDGE) {
64 Real mindist=cols[i-1].minright()
68 Real dif =v(i) - v(i-1)- mindist;
69 bool b = (dif > - COLFUDGE);
77 mtor << "dif= "<<dif<<" fudge= " << COLFUDGE<< " dif >fudge= "<<
80 /* fucks up for unknown reasons */
90 Spacing_problem::check_feasible() const
92 Vector sol(try_initial_solution());
93 return check_constraints(sol);
96 // generate a solution which obeys the min distances and fixed positions
98 Spacing_problem::try_initial_solution() const
102 for (int i=0; i < dim; i++) {
104 initsol(i)=cols[i].fixpos;
106 Real mindist=cols[i-1].minright()
108 assert(mindist >= 0.0);
109 initsol(i)=initsol(i-1)+mindist;
113 // assert(initsol(i) > initsol(i-1));
120 Spacing_problem::find_initial_solution() const
122 Vector v(try_initial_solution());
123 assert(check_constraints(v));
126 // generate the matrices
128 Spacing_problem::make_matrices(Matrix &quad, Vector &lin, Real &c) const
132 for (int j=0; j < ideals.sz(); j++){
133 Idealspacing const*i=ideals[j];
134 int l = col_id(i->left);
135 int r = col_id(i->right);
137 quad(r,r) += i->hooke;
138 quad(r,l) -= i->hooke;
139 quad(l,r) -= i->hooke;
140 quad(l,l) += i->hooke;
142 lin(r) -= i->space*i->hooke;
143 lin(l) += i->space*i->hooke;
149 // put the constraints into the LP problem
151 Spacing_problem::make_constraints(Mixed_qp& lp) const
154 for (int j=0; j < dim; j++) {
155 Colinfo *c=&(cols[j]);
157 lp.add_fixed_var(j,c->fixpos);
165 lp.add_inequality_cons(c1, cols[j-1].minright() +
172 Spacing_problem::solve() const
176 assert(check_feasible());
179 /* optimalisatiefunctie */
180 Mixed_qp lp(cols.sz());
181 make_matrices(lp.quad,lp.lin, lp.const_term);
182 make_constraints(lp);
183 Vector start=find_initial_solution();
184 Vector sol(lp.solve(start));
185 if (!check_constraints(sol)) {
186 WARN << "solution doesn't satisfy constraints.\n" ;
190 svec<Real> posns(sol);
191 posns.add(lp.eval(sol));
196 add one column to the problem.
199 Spacing_problem::add_column(const PCol *col, bool fixed, Real fixpos)
210 Spacing_problem::add_ideal(const Idealspacing *i)
212 const PCol *l =i->left;
213 const PCol *r= i->right;
215 if (!contains(l) || !contains(r)) {
222 Spacing_problem::print_ideal(const Idealspacing*id)const
225 int l = col_id(id->left);
226 int r = col_id(id->right);
228 mtor << "between " << l <<","<<r<<":" ;
233 Spacing_problem::print() const
236 for (int i=0; i < cols.sz(); i++) {
237 mtor << "col " << i<<' ';
240 for (int i=0; i < ideals.sz(); i++) {
241 print_ideal(ideals[i]);
248 Colinfo::print() const
253 mtor << "fixed at " << fixpos<<", ";
255 mtor << "[" << minleft() << ", " << minright() << "]";