*** empty log message ***

[lilypond.git] / lily / skyline.cc

diff --git a/lily/skyline.cc b/lily/skyline.cc
index 33447faeb8f63796a51c9b2647757fa7aaba79ca..f72ea5b2f6d5fcbf8c6cdf229d62077373b90c39 100644 (file)
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -1,44 +1,39 @@
-/*   
+/*

   skyline.cc -- implement Skyline_entry and funcs.
 
   source file of the GNU LilyPond music typesetter
 
   skyline.cc -- implement Skyline_entry and funcs.
 
   source file of the GNU LilyPond music typesetter
 

-  (c) 2002--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>

 */
 
 */
 

-#include "skyline.hh" 
-
+#include "skyline.hh"

 
 /*
   A skyline is a shape of the form:
 
 
 
 /*
   A skyline is a shape of the form:
 
 

-                  ----
-                  |  |
-         ---------|  |
-         |           |
-          |          |
-          |          |______
-  --------|                 |___
-  
-
+  *                  ----
+  *                  |  |
+  *         ---------|  |
+  *         |           |
+  *         |           |
+  *         |          |______
+  * --------|                |___
+  *

 
   This file deals with building such skyline structure, and computing
   the minimum distance between two opposing skylines.
 
   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
   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[0].width_[LEFT] = -inf
-  
- */

 
 

+  skyline.back ().width_[RIGHT] = inf
+  skyline[0].width_[LEFT] = -inf
+*/

 
 

-const Real EPS = 1e-12;  
+const Real EPS = 1e-12;

 
 /*
   TODO: avoid unnecessary fragmentation.
 
 /*
   TODO: avoid unnecessary fragmentation.


@@ -47,85 +42,82 @@ const Real EPS = 1e-12;
   binsearch.
 */
 void
   binsearch.
 */
 void

-insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
+insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,

                            Direction d)
 {
   Interval extent = b[line_axis];
   if (extent.is_empty ())
     return;
                            Direction d)
 {
   Interval extent = b[line_axis];
   if (extent.is_empty ())
     return;

-  
+

   Real stick_out = b[other_axis (line_axis)][d];
 
   /*
   Real stick_out = b[other_axis (line_axis)][d];
 
   /*

-    Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments. 
-   */
-  for (int i = line->size (); i--;)
+    Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
+  */
+  for (vsize i = line->size (); i--;)

     {
     {

-      Interval w = line->elem (i).width_;
+      Interval w = line->at (i).width_;

       w.intersect (extent);
 
       if (extent[LEFT] >= w[RIGHT])
        break;
       w.intersect (extent);
 
       if (extent[LEFT] >= w[RIGHT])
        break;

-      
-      Real my_height = line->elem (i).height_;

 
 

-      if (!w.is_empty () &&
-         w.length () > EPS
-         && d* (my_height - stick_out) < 0)
+      Real my_height = line->at (i).height_;
+
+      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->at (i).width_[LEFT], extent[LEFT]);
+         Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);

 
          if (!e3.is_empty () && e3.length () > EPS)
 
          if (!e3.is_empty () && e3.length () > EPS)

-           line->insert (Skyline_entry (e3, my_height), i+1);
+           line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height));

 
 

-         line->elem_ref (i).height_ = stick_out;
-         line->elem_ref (i).width_ = w;
+         line->at (i).height_ = stick_out;
+         line->at (i).width_ = w;

          if (!e1.is_empty () && e1.length () > EPS)
          if (!e1.is_empty () && e1.length () > EPS)

-           line->insert (Skyline_entry (e1, my_height), i );
+           line->insert (line->begin () + i, Skyline_entry (e1, my_height));

        }
        }

-
-

     }
 }
 
 void
     }
 }
 
 void

-merge_skyline (Array<Skyline_entry> * a1,
-              Array<Skyline_entry> const  & a2,
+merge_skyline (vector<Skyline_entry> *a1,
+              vector<Skyline_entry> const &a2,

               Direction dir)
 {
               Direction dir)
 {

-  for (int i = 0; i < a2.size (); i++)
+  for (vsize i = 0; i < a2.size (); i++)

     {
       Box b;
       b[X_AXIS] = a2[i].width_;
       b[Y_AXIS][dir] = a2[i].height_;
     {
       Box b;
       b[X_AXIS] = a2[i].width_;
       b[Y_AXIS][dir] = a2[i].height_;

-      b[Y_AXIS][-dir] = dir * infinity_f ;
+      b[Y_AXIS][-dir] = dir * infinity_f;

 
       insert_extent_into_skyline (a1, b, X_AXIS, dir);
     }
 }
 
 
       insert_extent_into_skyline (a1, b, X_AXIS, dir);
     }
 }
 

-
-Array<Skyline_entry>
+vector<Skyline_entry>

 empty_skyline (Direction d)
 {
 empty_skyline (Direction d)
 {

-  Array<Skyline_entry> skyline;
+  vector<Skyline_entry> skyline;

 
   Interval i;
   i.set_empty ();
   i.swap ();
   Skyline_entry e;
   e.width_ = i;
 
   Interval i;
   i.set_empty ();
   i.swap ();
   Skyline_entry e;
   e.width_ = i;

-  e.height_ = -d * infinity_f; 
-  skyline.push (e);
+  e.height_ = -d * infinity_f;
+  skyline.push_back (e);

   return skyline;
 }
 
   return skyline;
 }
 

-Array<Skyline_entry>
-extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
+vector<Skyline_entry>
+extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)

 {
 
 {
 

-  Array<Skyline_entry> skyline = empty_skyline (d);
+  vector<Skyline_entry> skyline = empty_skyline (d);

 
   /*
     This makes a cubic algorithm (array  insertion is O (n),
 
   /*
     This makes a cubic algorithm (array  insertion is O (n),


@@ -133,46 +125,40 @@ extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
 
     We could do a lot better (n log (n), using a balanced tree) but
     that seems overkill for now.
 
     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 (vsize j = extents.size (); j--;)

     insert_extent_into_skyline (&skyline, extents[j], a, d);
 
   return skyline;
 }
 
     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.
 /*
   minimum distance that can be achieved between baselines. "Clouds" is
   a skyline pointing down.
 
   This is an O (n) algorithm.

- */
+*/

 Real
 Real

-skyline_meshing_distance (Array<Skyline_entry> const &buildings,
-                         Array<Skyline_entry> const &clouds)
+skyline_meshing_distance (vector<Skyline_entry> const &buildings,
+                         vector<Skyline_entry> const &clouds)

 {
   int i = buildings.size () -1;
 {
   int i = buildings.size () -1;

-  int j  = clouds.size () -1;
+  int j = clouds.size () -1;
+
+  Real distance = -infinity_f;

 
 

-  Real distance = - infinity_f;
-  

   while (i > 0 || j > 0)
     {
       Interval w = buildings[i].width_;
       w.intersect (clouds[j].width_);
   while (i > 0 || j > 0)
     {
       Interval w = buildings[i].width_;
       w.intersect (clouds[j].width_);

-      
+

       if (!w.is_empty ())
       if (!w.is_empty ())

-       distance = distance >? (buildings[i].height_ - clouds[j].height_);
+       distance = max (distance, (buildings[i].height_ - clouds[j].height_));

 
 

-      if (i>0 && buildings[i].width_[LEFT] >=  clouds[j].width_[LEFT])
-       {
-         i--;
-       }
-      else if (j > 0 && buildings[i].width_[LEFT] <=  clouds[j].width_[LEFT])
-       {
-         j--;
-       }       
+      if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
+       i--;
+      else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
+       j--;

     }
 
   return distance;
     }
 
   return distance;


@@ -187,12 +173,30 @@ Skyline_entry::Skyline_entry (Interval i, Real r)
 {
   width_ = i;
   height_ = r;
 {
   width_ = i;
   height_ = r;

-  

 }
 
 void
 }
 
 void

-heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
+heighten_skyline (vector<Skyline_entry> *buildings, Real ground)

 {
 {

-  for (int i = 0; i < buildings->size (); i++)
-    buildings->elem_ref (i).height_ += ground; 
+  for (vsize i = 0; i < buildings->size (); i++)
+    buildings->at (i).height_ += ground;

 }
 }

+
+Real
+skyline_height (vector<Skyline_entry> const &buildings,
+               Real airplane,
+               Direction sky_dir)
+{
+  Real h = - sky_dir * infinity_f;
+
+  /*
+    Ugh! linear, should be O(log n).
+   */
+  for (vsize i = 0; i < buildings.size (); i++)
+    if (buildings[i].width_.contains (airplane))
+      h = sky_dir * max (sky_dir * h,
+                        sky_dir * buildings[i].height_);
+  
+  return h;
+}
+