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 void
  88 merge_skyline (Array<Skyline_entry> *a1,
  89                Array<Skyline_entry> const &a2,
  90                Direction dir)
  91 {
  92   for (int i = 0; i < a2.size (); i++)
  93     {
  94       Box b;
  95       b[X_AXIS] = a2[i].width_;
  96       b[Y_AXIS][dir] = a2[i].height_;
  97       b[Y_AXIS][-dir] = dir * infinity_f;
  98
  99       insert_extent_into_skyline (a1, b, X_AXIS, dir);
 100     }
 101 }
 102
 103 Array<Skyline_entry>
 104 empty_skyline (Direction d)
 105 {
 106   Array<Skyline_entry> skyline;
 107
 108   Interval i;
 109   i.set_empty ();
 110   i.swap ();
 111   Skyline_entry e;
 112   e.width_ = i;
 113   e.height_ = -d * infinity_f;
 114   skyline.push (e);
 115   return skyline;
 116 }
 117
 118 Array<Skyline_entry>
 119 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
 120 {
 121
 122   Array<Skyline_entry> skyline = empty_skyline (d);
 123
 124   /*
 125     This makes a cubic algorithm (array  insertion is O (n),
 126     searching the array dumbly is O (n), and for n items, we get O (n^3).)
 127
 128     We could do a lot better (n log (n), using a balanced tree) but
 129     that seems overkill for now.
 130   */
 131   for (int j = extents.size (); j--;)
 132     insert_extent_into_skyline (&skyline, extents[j], a, d);
 133
 134   return skyline;
 135 }
 136
 137 /*
 138   minimum distance that can be achieved between baselines. "Clouds" is
 139   a skyline pointing down.
 140
 141   This is an O (n) algorithm.
 142 */
 143 Real
 144 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
 145                           Array<Skyline_entry> const &clouds)
 146 {
 147   int i = buildings.size () -1;
 148   int j = clouds.size () -1;
 149
 150   Real distance = -infinity_f;
 151
 152   while (i > 0 || j > 0)
 153     {
 154       Interval w = buildings[i].width_;
 155       w.intersect (clouds[j].width_);
 156
 157       if (!w.is_empty ())
 158         distance = max (distance, (buildings[i].height_ - clouds[j].height_));
 159
 160       if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
 161         i--;
 162       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
 163         j--;
 164     }
 165
 166   return distance;
 167 }
 168
 169 Skyline_entry::Skyline_entry ()
 170 {
 171   height_ = 0.0;
 172 }
 173
 174 Skyline_entry::Skyline_entry (Interval i, Real r)
 175 {
 176   width_ = i;
 177   height_ = r;
 178 }
 179
 180 void
 181 heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
 182 {
 183   for (int i = 0; i < buildings->size (); i++)
 184     buildings->elem_ref (i).height_ += ground;
 185 }