lily/skyline.cc

   1 /*
   2   skyline.cc -- implement Skyline_entry and funcs.
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "skyline.hh"
  10
  11 void
  12 insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
  13                             Direction d)
  14 {
  15   Interval extent = b[line_axis];
  16   if (extent.empty_b())
  17     return;
  18
  19   Real stick_out = b[other_axis (line_axis)][d];
  20
  21   for (int i = line->size(); i--;)
  22     {
  23       Interval w = line->elem(i).width_;
  24       if (extent[LEFT] > w[RIGHT])
  25         break;
  26
  27       w.intersect (extent);
  28       Real my_height = line->elem(i).height_;
  29
  30       if (!w.empty_b () && d* (my_height - stick_out) < 0)
  31         {
  32           Interval e1 (line->elem(i).width_[LEFT], extent[LEFT]);
  33           Interval e3 (extent[RIGHT], line->elem(i).width_[RIGHT]);
  34
  35           if (!e3.empty_b ())
  36             line->insert (Skyline_entry (e3, my_height), i+1);
  37
  38           line->elem_ref(i).height_ = stick_out;
  39           line->elem_ref(i).width_ = w;
  40           if (!e1.empty_b ())
  41             line->insert (Skyline_entry (e1, my_height), i );
  42         }
  43
  44
  45     }
  46 }
  47
  48 Array<Skyline_entry>
  49 extents_to_skyline (Array<Box> extents, Axis a, Direction d)
  50 {
  51   Array<Skyline_entry> skyline;
  52
  53   Interval i;
  54   i.set_empty();
  55   i.swap();
  56   Skyline_entry e;
  57   e.width_ = i;
  58   e.height_ = -d * infinity_f;
  59   skyline.push (e);
  60
  61   /*
  62     This makes a quadratic algorithm -- we could do better (n log (n) ) but that
  63     seems overkill for now.
  64    */
  65   for (int j = extents.size(); j--; )
  66     insert_extent_into_skyline (&skyline, extents[j], a, d);
  67
  68   return skyline;
  69 }
  70
  71
  72 /*
  73   minimum distance that can be achieved between baselines. "Clouds" is
  74   a skyline pointing down.
  75  */
  76 Real
  77 skyline_meshing_distance (Array<Skyline_entry> buildings,
  78                           Array<Skyline_entry> clouds)
  79 {
  80   int i = buildings.size () -1;
  81   int j  = clouds.size() -1;
  82
  83   Real distance = - infinity_f;
  84
  85   while (i > 0 || j > 0)
  86     {
  87       Interval w = buildings[i].width_;
  88       w.intersect(clouds[j].width_);
  89
  90       if (!w.empty_b())
  91         distance = distance >? (buildings[i].height_ - clouds[j].height_);
  92
  93       if (i>0 && buildings[i].width_[LEFT] >=  clouds[j].width_[LEFT])
  94         {
  95           i--;
  96         }
  97       else if (j > 0 && buildings[i].width_[LEFT] <=  clouds[j].width_[LEFT])
  98         {
  99           j--;
 100         }
 101     }
 102
 103   return distance;
 104 }
 105
 106 Skyline_entry::Skyline_entry()
 107 {
 108   height_ = 0.0;
 109 }
 110
 111 Skyline_entry::Skyline_entry (Interval i, Real r)
 112 {
 113   width_ = i;
 114   height_ = r;
 115
 116 }