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