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