Small fix from mailist.

[lilypond.git] / lily / skyline.cc

diff --git a/lily/skyline.cc b/lily/skyline.cc
index b3b6349461a25369fffab2aaf0f954a05f359c71..f72ea5b2f6d5fcbf8c6cdf229d62077373b90c39 100644 (file)
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -3,7 +3,7 @@
 
   source file of the GNU LilyPond music typesetter
 
 
   source file of the GNU LilyPond music typesetter
 

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

 */
 
 #include "skyline.hh"
 */
 
 #include "skyline.hh"


@@ -12,26 +12,24 @@
   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.back ().width_[RIGHT] = inf

   skyline[0].width_[LEFT] = -inf
 */
 
   skyline[0].width_[LEFT] = -inf
 */
 


@@ -44,7 +42,7 @@ 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];
                            Direction d)
 {
   Interval extent = b[line_axis];


@@ -56,40 +54,40 @@ insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
   /*
     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
   */
   /*
     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
   */

-  for (int i = line->size (); i--;)
+  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_;
+      Real my_height = line->at (i).height_;

 
       if (!w.is_empty ()
          && w.length () > EPS
          && 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->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_;
     {
       Box b;
       b[X_AXIS] = a2[i].width_;


@@ -100,10 +98,10 @@ merge_skyline (Array<Skyline_entry> *a1,
     }
 }
 
     }
 }
 

-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 ();
 
   Interval i;
   i.set_empty ();


@@ -111,15 +109,15 @@ empty_skyline (Direction d)
   Skyline_entry e;
   e.width_ = i;
   e.height_ = -d * infinity_f;
   Skyline_entry e;
   e.width_ = i;
   e.height_ = -d * infinity_f;

-  skyline.push (e);
+  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),


@@ -128,7 +126,7 @@ 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;


@@ -141,8 +139,8 @@ extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
   This is an O (n) algorithm.
 */
 Real
   This is an O (n) algorithm.
 */
 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 j = clouds.size () -1;
 {
   int i = buildings.size () -1;
   int j = clouds.size () -1;


@@ -155,16 +153,12 @@ skyline_meshing_distance (Array<Skyline_entry> const &buildings,
       w.intersect (clouds[j].width_);
 
       if (!w.is_empty ())
       w.intersect (clouds[j].width_);
 
       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])
 
       if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])

-       {
-         i--;
-       }
+       i--;

       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])

-       {
-         j--;
-       }
+       j--;

     }
 
   return distance;
     }
 
   return distance;


@@ -182,8 +176,27 @@ Skyline_entry::Skyline_entry (Interval i, Real 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;
+}
+