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