X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=1d7782008dae7df5f0ccbd28184cafa569ff323b;hb=c7be17948fb3aec4e57e21027a0eb98f05be43bb;hp=cc47448ee9d07143d774ea586719a9cd9e3b0d24;hpb=667d9bdb6227dd10819599c6d069a5eeb67eedd7;p=lilypond.git

diff --git a/lily/skyline.cc b/lily/skyline.cc
index cc47448ee9..1d7782008d 100644
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -3,12 +3,11 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c) 2002--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 
 #include "skyline.hh" 
 
-
 /*
   A skyline is a shape of the form:
 
@@ -26,22 +25,24 @@
   This file deals with building such skyline structure, and computing
   the minimum distance between two opposing skylines.
   
-  
+   
   Invariants for a skyline:
 
   skyline[...].width_ forms a partition of the real interval, where
   the segments are adjacent, and ascending. Hence we have
   
-  skyline.top().width_[RIGHT] = inf
+  skyline.top ().width_[RIGHT] = inf
   skyline[0].width_[LEFT] = -inf
   
  */
 
 
+const Real EPS = 1e-12;  
+
 /*
   TODO: avoid unnecessary fragmentation.
 
-  This is O(n^2), searching and insertion.  Could be O(n log n) with
+  This is O (n^2), searching and insertion.  Could be O (n log n) with
   binsearch.
 */
 void
@@ -49,31 +50,37 @@ insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
 			    Direction d)
 {
   Interval extent = b[line_axis];
-  if (extent.empty_b())
+  if (extent.is_empty ())
     return;
   
   Real stick_out = b[other_axis (line_axis)][d];
-  
-  for (int i = line->size(); i--;)
+
+  /*
+    Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments. 
+   */
+  for (int i = line->size (); i--;)
     {
-      Interval w = line->elem(i).width_;
-      if (extent[LEFT] > w[RIGHT])
+      Interval w = line->elem (i).width_;
+      w.intersect (extent);
+
+      if (extent[LEFT] >= w[RIGHT])
 	break;
       
-      w.intersect (extent);
-      Real my_height = line->elem(i).height_;
+      Real my_height = line->elem (i).height_;
 
-      if (!w.empty_b () && d* (my_height - stick_out) < 0)
+      if (!w.is_empty () &&
+	  w.length () > EPS
+	  && d* (my_height - stick_out) < 0)
 	{
-	  Interval e1 (line->elem(i).width_[LEFT], extent[LEFT]);
-	  Interval e3 (extent[RIGHT], line->elem(i).width_[RIGHT]);
+	  Interval e1 (line->elem (i).width_[LEFT], extent[LEFT]);
+	  Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]);
 
-	  if (!e3.empty_b ())
+	  if (!e3.is_empty () && e3.length () > EPS)
 	    line->insert (Skyline_entry (e3, my_height), i+1);
 
-	  line->elem_ref(i).height_ = stick_out;
-	  line->elem_ref(i).width_ = w;
-	  if (!e1.empty_b ())
+	  line->elem_ref (i).height_ = stick_out;
+	  line->elem_ref (i).width_ = w;
+	  if (!e1.is_empty () && e1.length () > EPS)
 	    line->insert (Skyline_entry (e1, my_height), i );
 	}
 
@@ -81,6 +88,22 @@ insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
     }
 }
 
+void
+merge_skyline (Array<Skyline_entry> * a1,
+	       Array<Skyline_entry> const  & a2,
+	       Direction dir)
+{
+  for (int i = 0; i < a2.size (); i++)
+    {
+      Box b;
+      b[X_AXIS] = a2[i].width_;
+      b[Y_AXIS][dir] = a2[i].height_;
+      b[Y_AXIS][-dir] = dir * infinity_f ;
+
+      insert_extent_into_skyline (a1, b, X_AXIS, dir);
+    }
+}
+
 
 Array<Skyline_entry>
 empty_skyline (Direction d)
@@ -88,8 +111,8 @@ empty_skyline (Direction d)
   Array<Skyline_entry> skyline;
 
   Interval i;
-  i.set_empty();
-  i.swap();
+  i.set_empty ();
+  i.swap ();
   Skyline_entry e;
   e.width_ = i;
   e.height_ = -d * infinity_f; 
@@ -101,43 +124,44 @@ Array<Skyline_entry>
 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
 {
 
-  Array<Skyline_entry> skyline = empty_skyline(d);
+  Array<Skyline_entry> skyline = empty_skyline (d);
 
   /*
-    This makes a cubic algorithm (array  insertion is O(n),
-    searching the array dumbly is O(n), and for n items, we get O(n^3).)
+    This makes a cubic algorithm (array  insertion is O (n),
+    searching the array dumbly is O (n), and for n items, we get O (n^3).)
 
     We could do a lot better (n log (n), using a balanced tree) but
     that seems overkill for now.
    */
-  for (int j = extents.size(); j--; )
+  for (int j = extents.size (); j--; )
     insert_extent_into_skyline (&skyline, extents[j], a, d);
 
   return skyline;
 }
 
 
+
 /*
   minimum distance that can be achieved between baselines. "Clouds" is
   a skyline pointing down.
 
-  This is an O(n) algorithm.
+  This is an O (n) algorithm.
  */
 Real
 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
 			  Array<Skyline_entry> const &clouds)
 {
   int i = buildings.size () -1;
-  int j  = clouds.size() -1;
+  int j  = clouds.size () -1;
 
   Real distance = - infinity_f;
   
   while (i > 0 || j > 0)
     {
       Interval w = buildings[i].width_;
-      w.intersect(clouds[j].width_);
+      w.intersect (clouds[j].width_);
       
-      if (!w.empty_b())
+      if (!w.is_empty ())
 	distance = distance >? (buildings[i].height_ - clouds[j].height_);
 
       if (i>0 && buildings[i].width_[LEFT] >=  clouds[j].width_[LEFT])
@@ -153,7 +177,7 @@ skyline_meshing_distance (Array<Skyline_entry> const &buildings,
   return distance;
 }
 
-Skyline_entry::Skyline_entry()
+Skyline_entry::Skyline_entry ()
 {
   height_ = 0.0;
 }
@@ -164,3 +188,10 @@ Skyline_entry::Skyline_entry (Interval i, Real r)
   height_ = r;
   
 }
+
+void
+heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
+{
+  for (int i = 0; i < buildings->size (); i++)
+    buildings->elem_ref (i).height_ += ground; 
+}