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