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--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "skyline.hh"
  10
  11 /*
  12   A skyline is a shape of the form:
  13
  14
  15                    ----
  16                    |  |
  17           ---------|  |
  18           |           |
  19           |           |
  20           |           |______
  21   --------|                  |___
  22
  23
  24
  25   This file deals with building such skyline structure, and computing
  26   the minimum distance between two opposing skylines.
  27
  28
  29   Invariants for a skyline:
  30
  31   skyline[...].width_ forms a partition of the real interval, where
  32   the segments are adjacent, and ascending. Hence we have
  33
  34   skyline.top ().width_[RIGHT] = inf
  35   skyline[0].width_[LEFT] = -inf
  36
  37  */
  38
  39
  40 const Real EPS = 1e-12;
  41
  42 /*
  43   TODO: avoid unnecessary fragmentation.
  44
  45   This is O (n^2), searching and insertion.  Could be O (n log n) with
  46   binsearch.
  47 */
  48 void
  49 insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
  50                             Direction d)
  51 {
  52   Interval extent = b[line_axis];
  53   if (extent.is_empty ())
  54     return;
  55
  56   Real stick_out = b[other_axis (line_axis)][d];
  57
  58   /*
  59     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
  60    */
  61   for (int i = line->size (); i--;)
  62     {
  63       Interval w = line->elem (i).width_;
  64       w.intersect (extent);
  65
  66       if (extent[LEFT] >= w[RIGHT])
  67         break;
  68
  69       Real my_height = line->elem (i).height_;
  70
  71       if (!w.is_empty () &&
  72           w.length () > EPS
  73           && d* (my_height - stick_out) < 0)
  74         {
  75           Interval e1 (line->elem (i).width_[LEFT], extent[LEFT]);
  76           Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]);
  77
  78           if (!e3.is_empty () && e3.length () > EPS)
  79             line->insert (Skyline_entry (e3, my_height), i+1);
  80
  81           line->elem_ref (i).height_ = stick_out;
  82           line->elem_ref (i).width_ = w;
  83           if (!e1.is_empty () && e1.length () > EPS)
  84             line->insert (Skyline_entry (e1, my_height), i );
  85         }
  86
  87
  88     }
  89 }
  90
  91 void
  92 merge_skyline (Array<Skyline_entry> * a1,
  93                Array<Skyline_entry> const  & a2,
  94                Direction dir)
  95 {
  96   for (int i = 0; i < a2.size (); i++)
  97     {
  98       Box b;
  99       b[X_AXIS] = a2[i].width_;
 100       b[Y_AXIS][dir] = a2[i].height_;
 101       b[Y_AXIS][-dir] = dir * infinity_f ;
 102
 103       insert_extent_into_skyline (a1, b, X_AXIS, dir);
 104     }
 105 }
 106
 107
 108 Array<Skyline_entry>
 109 empty_skyline (Direction d)
 110 {
 111   Array<Skyline_entry> skyline;
 112
 113   Interval i;
 114   i.set_empty ();
 115   i.swap ();
 116   Skyline_entry e;
 117   e.width_ = i;
 118   e.height_ = -d * infinity_f;
 119   skyline.push (e);
 120   return skyline;
 121 }
 122
 123 Array<Skyline_entry>
 124 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
 125 {
 126
 127   Array<Skyline_entry> skyline = empty_skyline (d);
 128
 129   /*
 130     This makes a cubic algorithm (array  insertion is O (n),
 131     searching the array dumbly is O (n), and for n items, we get O (n^3).)
 132
 133     We could do a lot better (n log (n), using a balanced tree) but
 134     that seems overkill for now.
 135    */
 136   for (int j = extents.size (); j--; )
 137     insert_extent_into_skyline (&skyline, extents[j], a, d);
 138
 139   return skyline;
 140 }
 141
 142
 143
 144 /*
 145   minimum distance that can be achieved between baselines. "Clouds" is
 146   a skyline pointing down.
 147
 148   This is an O (n) algorithm.
 149  */
 150 Real
 151 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
 152                           Array<Skyline_entry> const &clouds)
 153 {
 154   int i = buildings.size () -1;
 155   int j  = clouds.size () -1;
 156
 157   Real distance = - infinity_f;
 158
 159   while (i > 0 || j > 0)
 160     {
 161       Interval w = buildings[i].width_;
 162       w.intersect (clouds[j].width_);
 163
 164       if (!w.is_empty ())
 165         distance = distance >? (buildings[i].height_ - clouds[j].height_);
 166
 167       if (i>0 && buildings[i].width_[LEFT] >=  clouds[j].width_[LEFT])
 168         {
 169           i--;
 170         }
 171       else if (j > 0 && buildings[i].width_[LEFT] <=  clouds[j].width_[LEFT])
 172         {
 173           j--;
 174         }
 175     }
 176
 177   return distance;
 178 }
 179
 180 Skyline_entry::Skyline_entry ()
 181 {
 182   height_ = 0.0;
 183 }
 184
 185 Skyline_entry::Skyline_entry (Interval i, Real r)
 186 {
 187   width_ = i;
 188   height_ = r;
 189
 190 }
 191
 192 void
 193 heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
 194 {
 195   for (int i = 0; i < buildings->size (); i++)
 196     buildings->elem_ref (i).height_ += ground;
 197 }