lily/tie-formatting-problem.cc

   1 /*
   2   tie-formatting-problem.cc -- implement Tie_formatting_problem
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2005--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7
   8 */
   9
  10 #include "tie-formatting-problem.hh"
  11
  12 #include "bezier.hh"
  13 #include "directional-element-interface.hh"
  14 #include "item.hh"
  15 #include "libc-extension.hh"
  16 #include "note-head.hh"
  17 #include "rhythmic-head.hh"
  18 #include "spanner.hh"
  19 #include "staff-symbol-referencer.hh"
  20 #include "stem.hh"
  21 #include "tie-configuration.hh"
  22 #include "tie.hh"
  23 #include "warn.hh"
  24
  25 /*
  26    0 at threshold,  1 at 0, with 1/x falloff.
  27  */
  28 Real peak_around (Real epsilon,  Real threshold, Real x)
  29 {
  30   if (x < 0)
  31     return 1.0;
  32   return max (- epsilon * (x - threshold) / ((x + epsilon)  * threshold), 0.0);
  33 }
  34
  35 Interval
  36 Tie_formatting_problem::get_attachment (Real y) const
  37 {
  38   Interval attachments;
  39   Direction d = LEFT;
  40   do
  41     {
  42       attachments[d] = skyline_height (chord_outlines_[d], y, -d);
  43     }
  44   while (flip (&d) != LEFT);
  45
  46   return attachments;
  47 }
  48
  49 Tie_formatting_problem::Tie_formatting_problem()
  50 {
  51   x_refpoint_ = 0;
  52 }
  53
  54 Tie_formatting_problem::~Tie_formatting_problem ()
  55 {
  56   for (Tie_configuration_map::const_iterator i (possibilities_.begin ());
  57        i != possibilities_.end (); i++)
  58     delete (*i).second;
  59 }
  60
  61 void
  62 Tie_formatting_problem::set_chord_outline (Link_array<Item> bounds,
  63                                            Direction d)
  64 {
  65   Real staff_space = Staff_symbol_referencer::staff_space (bounds[0]);
  66
  67   Array<Box> boxes;
  68
  69   Grob *stem = 0;
  70   for (int i = 0; i < bounds.size (); i++)
  71     {
  72       Grob *head = bounds[i];
  73       if (!Note_head::has_interface (head))
  74         continue;
  75
  76       if (!stem)
  77         stem = unsmob_grob (head->get_object ("stem"));
  78
  79       Real p = Staff_symbol_referencer::get_position (head);
  80       Interval y ((p-1) * 0.5 * staff_space,
  81                   (p+1) * 0.5 * staff_space);
  82
  83       Interval x = head->extent (x_refpoint_, X_AXIS);
  84       boxes.push (Box (x, y));
  85
  86       Grob *dots = Rhythmic_head::get_dots (head);
  87       if (d == LEFT && dots)
  88         {
  89           Interval x = dots->extent (x_refpoint_, X_AXIS);
  90           Interval y (-0.5, 0.5);
  91           int p = int (Staff_symbol_referencer::get_position (dots));
  92           y.translate (p);
  93
  94           dot_positions_.insert (p);
  95           dot_x_.unite (x);
  96
  97           y *= staff_space * 0.5;
  98           // boxes.push (Box (x, y));
  99         }
 100     }
 101
 102   chord_outlines_[d] = empty_skyline (-d);
 103
 104   if (bounds[0]->break_status_dir ())
 105     {
 106       Real x = robust_relative_extent (bounds[0],  x_refpoint_, X_AXIS)[-d];
 107       chord_outlines_[d].elem_ref (0).height_ = x;
 108     }
 109
 110   for (int i = 0; i < boxes.size (); i++)
 111     insert_extent_into_skyline (&chord_outlines_[d]  ,
 112                                 boxes[i], Y_AXIS, -d);
 113
 114   if (stem
 115       && !Stem::is_invisible (stem))
 116     {
 117       Interval x;
 118       x.add_point (stem->relative_coordinate (x_refpoint_, X_AXIS));
 119       x.widen (staff_space / 20); // ugh.
 120       Interval y;
 121       y.add_point (Stem::stem_end_position (stem) * staff_space * .5);
 122
 123       Direction stemdir = get_grob_direction (stem);
 124       y.add_point (Stem::head_positions (stem)[-stemdir]
 125                    * staff_space * .5);
 126
 127       insert_extent_into_skyline (&chord_outlines_[d], Box (x,y), Y_AXIS, -d);
 128
 129       stem_extents_[d].unite (Box (x,y));
 130
 131       if (d == LEFT)
 132         {
 133           Box flag_box = Stem::get_translated_flag (stem).extent_box ();
 134           flag_box.translate( Offset (x[RIGHT], X_AXIS));
 135           insert_extent_into_skyline (&chord_outlines_[d], flag_box,
 136                                       Y_AXIS, -d);
 137         }
 138     }
 139
 140   Direction updowndir = DOWN;
 141   do
 142     {
 143       Interval x;
 144       Interval y;
 145       if (boxes.size())
 146         {
 147           Box b = boxes.boundary (updowndir, 0);
 148           x = b[X_AXIS];
 149           x[-d] =  b[X_AXIS].linear_combination (-d / 2);
 150           y[-updowndir] = b[Y_AXIS][updowndir];
 151           y[updowndir] = updowndir * infinity_f;
 152         }
 153
 154       if (!x.is_empty ())
 155         insert_extent_into_skyline (&chord_outlines_[d],
 156                                     Box (x,y),
 157                                     Y_AXIS, -d);
 158     }
 159   while (flip (&updowndir) != DOWN);
 160 }
 161
 162
 163 void
 164 Tie_formatting_problem::from_tie (Grob *tie)
 165 {
 166   Link_array<Grob> ties;
 167   ties.push (tie);
 168   from_ties (ties);
 169
 170   details_.from_grob (tie);
 171 }
 172
 173 Grob *
 174 Tie_formatting_problem::common_x_refpoint () const
 175 {
 176   return x_refpoint_;
 177 }
 178
 179 void
 180 Tie_formatting_problem::from_ties (Link_array<Grob> const &ties)
 181 {
 182   if (ties.is_empty ())
 183     return;
 184
 185   x_refpoint_ = ties[0];
 186   for (int i = 0; i < ties.size (); i++)
 187     {
 188       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS);
 189       x_refpoint_ = dynamic_cast<Spanner*> (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS);
 190     }
 191
 192   details_.from_grob (ties[0]);
 193
 194   Direction d = LEFT;
 195   do
 196     {
 197       Link_array<Item> bounds;
 198
 199       for (int i = 0; i < ties.size (); i++)
 200         {
 201           Item *it = dynamic_cast<Spanner*> (ties[i])->get_bound (d);
 202
 203           bounds.push (it);
 204         }
 205
 206       set_chord_outline (bounds, d);
 207     }
 208   while (flip (&d) != LEFT);
 209
 210
 211   for (int i = 0; i < ties.size (); i++)
 212     {
 213       Tie_specification spec;
 214
 215       if (scm_is_number (ties[i]->get_property_data (ly_symbol2scm ("direction"))))
 216         {
 217           spec.manual_dir_ = to_dir (ties[i]->get_property ("direction"));
 218           spec.has_manual_dir_ = true;
 219         }
 220
 221       spec.position_ = Tie::get_position (ties[i]);
 222
 223       do
 224         {
 225           spec.note_head_drul_[d] = Tie::head (ties[i], d);
 226         }
 227       while (flip (&d) != LEFT);
 228
 229       specifications_.push (spec);
 230     }
 231 }
 232
 233 void
 234 Tie_formatting_problem::from_lv_ties (Link_array<Grob> const &lv_ties)
 235 {
 236   if (lv_ties.is_empty ())
 237     return ;
 238
 239   details_.from_grob (lv_ties[0]);
 240   Link_array<Item> heads;
 241
 242   for (int i = 0; i < lv_ties.size (); i++)
 243     {
 244       Tie_specification spec;
 245       Item *head = unsmob_item (lv_ties[i]->get_object ("note-head"));
 246
 247       if (!head)
 248         programming_error ("LV tie without head?!");
 249
 250       if (head)
 251         {
 252           spec.position_ = int (Staff_symbol_referencer::get_position (head));
 253         }
 254
 255       spec.note_head_drul_[LEFT] = head;
 256       heads.push (head);
 257       specifications_.push (spec);
 258     }
 259
 260   x_refpoint_ = lv_ties [0];
 261   for (int i = 0; i < lv_ties.size (); i++)
 262     {
 263       x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS);
 264     }
 265
 266   set_chord_outline (heads, LEFT);
 267
 268   Real right_most = - infinity_f;
 269
 270   for (int i = 0; i < chord_outlines_[LEFT].size (); i++)
 271     {
 272       right_most = max (right_most, chord_outlines_[LEFT][i].height_);
 273     }
 274
 275   Skyline_entry right_entry;
 276   right_entry.width_.set_full ();
 277   right_entry.height_ = right_most + 1.5;
 278
 279   chord_outlines_[RIGHT].push (right_entry);
 280 }
 281
 282
 283 Tie_specification
 284 Tie_formatting_problem::get_tie_specification (int i) const
 285 {
 286   return specifications_[i];
 287 }
 288
 289
 290 Tie_configuration*
 291 Tie_formatting_problem::get_configuration (int pos, Direction dir)
 292 {
 293   pair<int,int> key (pos, dir);
 294   Tie_configuration_map::const_iterator f = possibilities_.find (key);
 295
 296   if (f != possibilities_.end ())
 297     {
 298       return (*f).second;
 299     }
 300
 301
 302   Tie_configuration *conf = generate_configuration (pos,dir);
 303   possibilities_[key] = conf;
 304   return conf;
 305 }
 306
 307 Tie_configuration*
 308 Tie_formatting_problem::generate_configuration (int pos, Direction dir) const
 309 {
 310   Tie_configuration *conf = new Tie_configuration;
 311   conf->position_ = pos;
 312   conf->dir_ = dir;
 313   Real y = conf->position_ * 0.5 * details_.staff_space_;
 314
 315   if (dot_positions_.find (pos) != dot_positions_.end ())
 316     {
 317       conf->delta_y_ += 0.25 * details_.staff_space_;
 318     }
 319
 320   conf->attachment_x_ = get_attachment (y + conf->delta_y_);
 321
 322   Real h =  conf->height (details_);
 323   if (!conf->delta_y_)
 324     {
 325       /*
 326         TODO: make sliding criterion?
 327        */
 328       if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_)
 329         {
 330           if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)
 331               && fabs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_))
 332             {
 333               conf->center_tie_vertically (details_);
 334             }
 335           else if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos))
 336             {
 337               conf->delta_y_ += dir *
 338                 details_.tip_staff_line_clearance_ * 0.5 *  details_.staff_space_;
 339             }
 340         }
 341       else
 342         {
 343           Real top_y = y + conf->delta_y_ + conf->dir_ * h;
 344           Real top_pos = top_y / (0.5*details_.staff_space_);
 345           int round_pos = int (my_round (top_pos));
 346
 347           /* TODO: should use other variable? */
 348           Real clearance = details_.center_staff_line_clearance_;
 349           if (fabs (top_pos - round_pos) < clearance
 350               && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_,
 351                                                          round_pos))
 352             {
 353               Real new_y = (round_pos + clearance * conf->dir_) * 0.5 * details_.staff_space_;
 354               conf->delta_y_ = (new_y - top_y);
 355             }
 356         }
 357     }
 358
 359   /*
 360     we don't recompute attachment_x_ to take changed Y (through
 361     delta_Y) into account. Doing would make ties go into small holes between heads, which
 362     means we get collisions with neighboring heads.
 363    */
 364   conf->attachment_x_.widen ( - details_.x_gap_);
 365
 366   Direction d = LEFT;
 367   do
 368     {
 369       Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_;
 370       if (stem_extents_[d][X_AXIS].is_empty ()
 371           || !stem_extents_[d][Y_AXIS].contains (y))
 372         continue;
 373
 374       conf->attachment_x_[d] =
 375         d* min (d * conf->attachment_x_[d],
 376                 d * (stem_extents_[d][X_AXIS][-d] - d * details_.stem_gap_));
 377     }
 378   while (flip (&d) != LEFT);
 379   return conf;
 380 }
 381
 382 Real
 383 Tie_formatting_problem::score_aptitude (Tie_configuration const &conf,
 384                                         Tie_specification const &spec) const
 385 {
 386   Real penalty = 0.0;
 387   Real curve_y = conf.position_ * details_.staff_space_ * 0.5 + conf.delta_y_;
 388   Real tie_y = spec.position_ * details_.staff_space_ * 0.5;
 389   if (sign (curve_y - tie_y) != conf.dir_)
 390     penalty += details_.wrong_direction_offset_penalty_;
 391
 392   penalty += details_.vertical_distance_penalty_factor_ * fabs (curve_y - tie_y);
 393
 394
 395   Direction d = LEFT;
 396   do
 397     {
 398       if (!spec.note_head_drul_[d])
 399         continue;
 400
 401       Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS);
 402       Real dist = head_x.distance (conf.attachment_x_[d]);
 403       penalty += details_.horizontal_distance_penalty_factor_ * dist;
 404     }
 405   while  (flip (&d) != LEFT);
 406
 407   return penalty;
 408 }
 409
 410 Real
 411 Tie_formatting_problem::score_configuration (Tie_configuration const &conf) const
 412 {
 413   Real penalty = 0.0;
 414   Real length = conf.attachment_x_.length ();
 415   if (length < details_.min_length_)
 416     penalty += details_.length_penalty_factor_ / max (0.01, length);
 417
 418   Real tip_pos = conf.position_ + conf.delta_y_ / 0.5 * details_.staff_space_;
 419   Real tip_y = tip_pos * details_.staff_space_ * 0.5;
 420   Real height =  conf.height (details_);
 421
 422   Real top_y = tip_y + conf.dir_ * height;
 423   Real top_pos = 2 * top_y / details_.staff_space_;
 424   Real round_top_pos = rint (top_pos);
 425   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 426                                                 int (round_top_pos))
 427       && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y)
 428     {
 429       penalty +=
 430         details_.staff_line_collision_penalty_
 431         * peak_around (0.1 * details_.center_staff_line_clearance_,
 432                      details_.center_staff_line_clearance_,
 433                      fabs (top_pos - round_top_pos));
 434     }
 435
 436   if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_,
 437                                         int (rint (tip_pos))))
 438     {
 439       penalty += details_.staff_line_collision_penalty_
 440         * peak_around (0.1 * details_.tip_staff_line_clearance_,
 441                        details_.tip_staff_line_clearance_,
 442                        fabs (tip_pos - rint (tip_pos)));
 443     }
 444
 445   if (!dot_x_.is_empty ())
 446     {
 447       /* use left edge? */
 448       Real x = dot_x_.center ();
 449
 450       Bezier b = conf.get_transformed_bezier (details_);
 451       if (b.control_point_extent (X_AXIS).contains (x))
 452         {
 453           Real y = b.get_other_coordinate (X_AXIS, x);
 454
 455           for (set<int>::const_iterator i (dot_positions_.begin ());
 456                i != dot_positions_.end (); i ++)
 457             {
 458               int dot_pos = (*i);
 459               penalty +=
 460                 details_.dot_collision_penalty_
 461                 * peak_around (.1 * details_.dot_collision_clearance_,
 462                                details_.dot_collision_clearance_,
 463                                fabs (dot_pos * details_.staff_space_ * 0.5 - y));
 464             }
 465         }
 466     }
 467
 468   return penalty;
 469 }
 470
 471 Tie_configuration
 472 Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const &spec) const
 473 {
 474   Link_array<Tie_configuration> confs;
 475
 476   int pos = spec.position_;
 477   Direction dir = spec.manual_dir_;
 478
 479   int region_size = 3;
 480   for (int i = 0; i < region_size; i ++)
 481     {
 482       confs.push (generate_configuration (pos + i * dir, dir));
 483     }
 484
 485   Array<Real> scores;
 486
 487   int best_idx = -1;
 488   Real best_score = 1e6;
 489   for (int i = 0; i < confs.size (); i ++)
 490     {
 491       Real score = 0.0;
 492       score += score_configuration (*confs[i]);
 493       score += score_aptitude (*confs[i], spec);
 494
 495       if (score < best_score)
 496         {
 497           best_score = score;
 498           best_idx = i;
 499         }
 500     }
 501
 502   Tie_configuration best = *confs[best_idx];
 503   for (int i = 0; i < confs.size (); i++)
 504     delete confs[i];
 505
 506   return best;
 507 }
 508
 509 Tie_specification::Tie_specification ()
 510 {
 511   has_manual_position_ = false;
 512   has_manual_dir_ = false;
 513   position_ = 0;
 514   manual_position_ = 0;
 515   manual_dir_ = CENTER;
 516   note_head_drul_[LEFT] =
 517     note_head_drul_[RIGHT] = 0;
 518 }
 519
 520
 521 Real
 522 Tie_formatting_problem::score_ties_aptitude (Ties_configuration const &ties) const
 523 {
 524   Real score = 0.0;
 525   if  (ties.size () != specifications_.size ())
 526     {
 527       programming_error ("Huh? Mismatch between sizes.");
 528       return infinity_f;
 529     }
 530
 531   for (int i = 0; i < ties.size (); i++)
 532     score += score_aptitude (ties[i], specifications_[i]);
 533
 534   return score;
 535 }
 536
 537 Real
 538 Tie_formatting_problem::score_ties (Ties_configuration const &ties) const
 539 {
 540   return score_ties_configuration (ties)
 541     + score_ties_aptitude (ties);
 542 }
 543
 544 Real
 545 Tie_formatting_problem::score_ties_configuration (Ties_configuration const &ties) const
 546 {
 547   Real score = 0.0;
 548   for (int i = 0; i < ties.size (); i++)
 549     {
 550       score += score_configuration (ties[i]);
 551     }
 552
 553
 554   Real last_edge = 0.0;
 555   Real last_center = 0.0;
 556   for (int i = 0; i < ties.size (); i++)
 557     {
 558       Bezier b (ties[i].get_transformed_bezier (details_));
 559
 560       Real center = b.curve_point (0.5)[Y_AXIS];
 561       Real edge = b.curve_point (0.0)[Y_AXIS];
 562
 563       if (i)
 564         {
 565           if (edge <= last_edge)
 566             score += details_.tie_column_monotonicity_penalty_;
 567           if (center <= last_center)
 568             score += details_.tie_column_monotonicity_penalty_;
 569
 570           score +=
 571             details_.tie_tie_collision_penalty_ *
 572             peak_around (0.1 * details_.tie_tie_collision_distance_,
 573                          details_.tie_tie_collision_distance_,
 574                          fabs (center - last_center));
 575           score +=
 576             details_.tie_tie_collision_penalty_ *
 577             peak_around (0.1 * details_.tie_tie_collision_distance_,
 578                          details_.tie_tie_collision_distance_,
 579                          fabs (edge - last_edge));
 580         }
 581
 582       last_edge = edge;
 583       last_center = center;
 584     }
 585
 586   return score;
 587 }
 588
 589 /*
 590   Generate with correct X-attachments and beziers, copying delta_y_
 591   from TIES_CONFIG if necessary.
 592 */
 593 Ties_configuration
 594 Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config)
 595 {
 596   Ties_configuration copy;
 597   for (int i = 0; i < ties_config.size (); i++)
 598     {
 599       Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_);
 600       if (specifications_[i].has_manual_position_)
 601         {
 602           ptr->delta_y_
 603             = (specifications_[i].manual_position_ - ties_config[i].position_)
 604             * 0.5 * details_.staff_space_;
 605         }
 606       copy.push (*ptr);
 607     }
 608
 609   return copy;
 610 }
 611
 612 Ties_configuration
 613 Tie_formatting_problem::generate_base_chord_configuration ()
 614 {
 615   Ties_configuration ties_config;
 616   for (int i = 0;  i < specifications_.size (); i ++)
 617     {
 618       Tie_configuration conf;
 619       if (specifications_[i].has_manual_dir_)
 620         conf.dir_ = specifications_[i].manual_dir_;
 621       if (specifications_[i].has_manual_position_)
 622         {
 623           conf.position_ = (int) my_round (specifications_[i].manual_position_);
 624           conf.delta_y_ = (specifications_[i].manual_position_ - conf.position_)
 625             * 0.5 * details_.staff_space_;
 626         }
 627       else
 628         {
 629           conf.position_ = specifications_[i].position_;
 630         }
 631       ties_config.push (conf);
 632     }
 633
 634   set_ties_config_standard_directions (&ties_config);
 635   for (int i = 0; i < ties_config.size (); i++)
 636     if (!specifications_[i].manual_position_)
 637       ties_config[i].position_ += ties_config[i].dir_;
 638
 639   ties_config = generate_ties_configuration (ties_config);
 640
 641   return ties_config;
 642 }
 643
 644 Ties_configuration
 645 Tie_formatting_problem::generate_optimal_chord_configuration ()
 646 {
 647   Ties_configuration base = generate_base_chord_configuration ();
 648   Array<Tie_configuration_variation> vars = get_variations (base);
 649
 650   Ties_configuration best = base;
 651   Real best_score = score_ties (best);
 652
 653   /*
 654     This simply is 1-opt: we have K substitions, and we try applying
 655     exactly every one for each.
 656   */
 657   for (int i = 0; i < vars.size (); i++)
 658     {
 659       Ties_configuration variant = base;
 660       variant[vars[i].index_] = *vars[i].suggestion_;
 661
 662       Real score = score_ties (variant);
 663       if (score < best_score)
 664         {
 665           best = variant;
 666           best_score = score;
 667         }
 668     }
 669
 670   return best;
 671 }
 672
 673 void
 674 Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs)
 675 {
 676   if (tie_configs->is_empty ())
 677     return ;
 678
 679   if (!tie_configs->elem (0).dir_)
 680     tie_configs->elem_ref (0).dir_ = DOWN;
 681   if (!tie_configs->top().dir_)
 682     tie_configs->top().dir_ = UP;
 683
 684   /*
 685     Seconds
 686    */
 687   for (int i = 1; i < tie_configs->size (); i++)
 688     {
 689       Real diff = (tie_configs->elem (i-1).position_
 690                    - tie_configs->elem (i).position_);
 691
 692       if (fabs (diff) <= 1)
 693         {
 694           if (!tie_configs->elem (i-1).dir_)
 695             tie_configs->elem_ref (i-1).dir_ = DOWN;
 696           if (!tie_configs->elem (i).dir_)
 697             tie_configs->elem_ref (i).dir_ = UP;
 698         }
 699     }
 700
 701   for (int i = 1; i < tie_configs->size() - 1; i++)
 702     {
 703       Tie_configuration &conf = tie_configs->elem_ref (i);
 704       if (conf.dir_)
 705         continue;
 706
 707       Direction position_dir =
 708         Direction (sign (conf.position_));
 709       if (!position_dir)
 710         position_dir = DOWN;
 711
 712       conf.dir_ = position_dir;
 713     }
 714 }
 715
 716 Tie_configuration_variation::Tie_configuration_variation ()
 717 {
 718   index_ = 0;
 719   suggestion_ = 0;
 720 }
 721
 722 Array<Tie_configuration_variation>
 723 Tie_formatting_problem::get_variations (Ties_configuration const &ties)
 724 {
 725   Real center_distance_tolerance = 0.25;
 726
 727   Array<Tie_configuration_variation> vars;
 728   Real last_center = 0.0;
 729   for (int i = 0; i < ties.size (); i++)
 730     {
 731       Bezier b (ties[i].get_transformed_bezier (details_));
 732
 733       Real center = b.curve_point (0.5)[Y_AXIS];
 734
 735       if (i)
 736         {
 737           if (center <= last_center + center_distance_tolerance)
 738             {
 739               if (!specifications_[i].has_manual_dir_)
 740                 {
 741                   Tie_configuration_variation var;
 742                   var.index_ = i;
 743                   var.suggestion_ = get_configuration (specifications_[i].position_
 744                                                        - ties[i].dir_,
 745                                                        -ties[i].dir_);
 746
 747                   vars.push (var);
 748                 }
 749
 750               if (!specifications_[i-1].has_manual_dir_)
 751                 {
 752                   Tie_configuration_variation var;
 753                   var.index_ = i-1;
 754                   var.suggestion_ = get_configuration (specifications_[i-1].position_
 755                                                        - ties[i-1].dir_,
 756                                                        - ties[i-1].dir_);
 757
 758                   vars.push (var);
 759                 }
 760             }
 761         }
 762
 763       last_center = center;
 764     }
 765
 766   /*  TODO: switch off? */
 767   Direction d = DOWN;
 768   do
 769     {
 770       if (ties.boundary (d, 0).dir_ == d)
 771         {
 772           Tie_configuration_variation var;
 773           var.index_ = (d == DOWN) ? 0 : ties.size () - 1;
 774           var.suggestion_ = get_configuration (ties.boundary (d, 0).position_ + d,
 775                                                d);
 776           vars.push (var);
 777         }
 778     }
 779   while (flip (&d) !=  DOWN);
 780
 781   return vars;
 782 }
 783
 784 void
 785 Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs)
 786 {
 787   int k = 0;
 788   for (SCM s = manual_configs;
 789        scm_is_pair (s) && k < specifications_.size(); s = scm_cdr (s))
 790     {
 791       SCM entry = scm_car (s);
 792       if (!scm_is_pair (entry))
 793         continue;
 794
 795       Tie_specification &spec = specifications_[k];
 796
 797       if (scm_is_number (scm_cdr (entry)))
 798         {
 799           spec.has_manual_dir_ = true;
 800           spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry)));
 801         }
 802       if (scm_is_number (scm_car (entry)))
 803         {
 804           spec.has_manual_position_ = true;
 805           spec.manual_position_ = scm_to_double (scm_car (entry));
 806         }
 807
 808       k ++;
 809     }
 810 }
 811