From aa5b82f7a91bb2aad800957a640fd7a1db5d9f80 Mon Sep 17 00:00:00 2001 From: fred Date: Tue, 12 Nov 1996 00:16:52 +0000 Subject: [PATCH] lilypond-0.0.9 --- hdr/boxes.hh | 88 ++++++++++++++++ src/linespace.cc | 264 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 352 insertions(+) create mode 100644 hdr/boxes.hh create mode 100644 src/linespace.cc diff --git a/hdr/boxes.hh b/hdr/boxes.hh new file mode 100644 index 0000000000..15beb8c372 --- /dev/null +++ b/hdr/boxes.hh @@ -0,0 +1,88 @@ +/* + some 2D geometrical concepts +*/ + +#ifndef BOXES_HH +#define BOXES_HH + +#include "textdb.hh" +#include "real.hh" +#include "vray.hh" + +/// 2d vector +struct Offset { + Real x,y; + + Offset operator+(Offset o)const { + Offset r(*this); + r+=o; + return r; + } + + Offset operator+=(Offset o) { + x+=o.x; + y+=o.y; + return *this; + } + Offset(Real ix , Real iy) { + x=ix; + y=iy; + } + Offset() { + x=0.0; + y=0.0; + } +}; + +/// a Real interval +struct Interval { + Real min, max; + + void translate(Real t) { + min += t; + max += t; + } + + void unite(Interval h) { + if (h.minmax) + max = h.max; + } + Real length() const; + void set_empty() ; + bool empty() { return min > max; } + Interval() { + set_empty(); + } + Interval(Real m, Real M) { + min =m; + max = M; + } + Interval &operator += (Real r) { + min += r; + max +=r; + return *this; + } +}; + + +/// a 4-tuple of #Real#s +struct Box { + Interval x, y; + + void translate(Offset o) { + x.translate(o.x); + y.translate(o.y); + } + void unite(Box b) { + x.unite(b.x); + y.unite(b.y); + } + Box(svec ); + Box(); + Box(Interval ix, Interval iy); +}; + + +#endif diff --git a/src/linespace.cc b/src/linespace.cc new file mode 100644 index 0000000000..6b16c9afab --- /dev/null +++ b/src/linespace.cc @@ -0,0 +1,264 @@ +#include +#include "linespace.hh" +#include "debug.hh" +#include "qlp.hh" +#include "unionfind.hh" + +const Real COLFUDGE=1e-3; +//#define COLFUDGE 1e-3 +bool +Spacing_problem::contains(const PCol *w) +{ + for (int i=0; i< cols.sz(); i++) + if (cols[i].pcol_ == w) + return true; + return false; +} + +int +Spacing_problem::col_id(const PCol *w)const +{ + for (int i=0; i< cols.sz(); i++) + if (cols[i].pcol_ == w) + return i; + assert(false); +} + +void +Spacing_problem::OK() const +{ +#ifndef NDEBUG + Union_find connected(cols.sz()); + svec fixed; + for (int i=0; i < ideals.sz(); i++) { + assert(ideals[i]->hooke > 0); + int l = col_id(ideals[i]->left); + int r = col_id(ideals[i]->right); + connected.connect(l,r); + } + for (int i = 0; i < cols.sz(); i++) + if (cols[i].fixed) + fixed.add(i); + for (int i = 0; i < cols.sz(); i++) { + bool c=false; + for (int j =0; j COLFUDGE) { + return false; + } + if (!i) + continue; + + Real mindist=cols[i-1].minright() + +cols[i].minleft(); + + // ugh... compares + Real dif =v(i) - v(i-1)- mindist; + bool b = (dif > - COLFUDGE); + + +#if 1 + if (!b) + return false; + +#else + mtor << "dif= "<fudge= "<< + b << "\n"; + + /* fucks up for unknown reasons */ + if (dif < -COLFUDGE) + return false; +#endif + + } + return true; +} + +bool +Spacing_problem::check_feasible() const +{ + Vector sol(try_initial_solution()); + return check_constraints(sol); +} + +// generate a solution which obeys the min distances and fixed positions +Vector +Spacing_problem::try_initial_solution() const +{ + int dim=cols.sz(); + Vector initsol(dim); + for (int i=0; i < dim; i++) { + if (cols[i].fixed) { + initsol(i)=cols[i].fixpos; + } else { + Real mindist=cols[i-1].minright() + +cols[i].minleft(); + assert(mindist >= 0.0); + initsol(i)=initsol(i-1)+mindist; + + //nog niet + //if (i>0) + // assert(initsol(i) > initsol(i-1)); + } + } + + return initsol; +} +Vector +Spacing_problem::find_initial_solution() const +{ + Vector v(try_initial_solution()); + assert(check_constraints(v)); + return v; +} +// generate the matrices +void +Spacing_problem::make_matrices(Matrix &quad, Vector &lin, Real &c) const +{ + quad.fill(0); + lin.fill(0); + for (int j=0; j < ideals.sz(); j++){ + Idealspacing const*i=ideals[j]; + int l = col_id(i->left); + int r = col_id(i->right); + + quad(r,r) += i->hooke; + quad(r,l) -= i->hooke; + quad(l,r) -= i->hooke; + quad(l,l) += i->hooke; + + lin(r) -= i->space*i->hooke; + lin(l) += i->space*i->hooke; + + c += sqr(i->space); + } +} + +// put the constraints into the LP problem +void +Spacing_problem::make_constraints(Mixed_qp& lp) const +{ + int dim=cols.sz(); + for (int j=0; j < dim; j++) { + Colinfo *c=&(cols[j]); + if (c->fixed) { + lp.add_fixed_var(j,c->fixpos); + } + if (j > 0){ + Vector c1(dim); + + + c1(j)=1.0 ; + c1(j-1)=-1.0 ; + lp.add_inequality_cons(c1, cols[j-1].minright() + + cols[j].minleft()); + } + } +} + +svec +Spacing_problem::solve() const +{ + print(); + OK(); + assert(check_feasible()); + + + /* optimalisatiefunctie */ + Mixed_qp lp(cols.sz()); + make_matrices(lp.quad,lp.lin, lp.const_term); + make_constraints(lp); + Vector start=find_initial_solution(); + Vector sol(lp.solve(start)); + if (!check_constraints(sol)) { + WARN << "solution doesn't satisfy constraints.\n" ; + } + + + svec posns(sol); + posns.add(lp.eval(sol)); + return posns; +} + +/* + add one column to the problem. +*/ +void +Spacing_problem::add_column(const PCol *col, bool fixed, Real fixpos) +{ + Colinfo c; + c.fixed=fixed; + c.fixpos=fixpos; + assert(col); + c.pcol_=col; + cols.add(c); +} + +void +Spacing_problem::add_ideal(const Idealspacing *i) +{ + const PCol *l =i->left; + const PCol *r= i->right; + + if (!contains(l) || !contains(r)) { + return; + } + ideals.add(i); +} + +void +Spacing_problem::print_ideal(const Idealspacing*id)const +{ +#ifndef NPRINT + int l = col_id(id->left); + int r = col_id(id->right); + + mtor << "between " << l <<","<