X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=f72ea5b2f6d5fcbf8c6cdf229d62077373b90c39;hb=60e6486425fd08ee69e3e383ca5183d058bca037;hp=bbbf7f55808b15939c796546ee6d341a166cbbd2;hpb=58bcc84c9480dae1b21bc24d8396b91fe19e0131;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index bbbf7f5580..f72ea5b2f6 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -3,7 +3,7 @@ source file of the GNU LilyPond music typesetter - (c) 2002--2005 Han-Wen Nienhuys + (c) 2002--2006 Han-Wen Nienhuys */ #include "skyline.hh" @@ -12,26 +12,24 @@ 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. - 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 */ @@ -44,7 +42,7 @@ const Real EPS = 1e-12; binsearch. */ void -insert_extent_into_skyline (Array *line, Box b, Axis line_axis, +insert_extent_into_skyline (vector *line, Box b, Axis line_axis, Direction d) { Interval extent = b[line_axis]; @@ -56,41 +54,40 @@ insert_extent_into_skyline (Array *line, Box b, Axis line_axis, /* 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; - 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) + && 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) - 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) - line->insert (Skyline_entry (e1, my_height), i); + line->insert (line->begin () + i, Skyline_entry (e1, my_height)); } - } } void -merge_skyline (Array * a1, - Array const &a2, +merge_skyline (vector *a1, + vector const &a2, 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_; @@ -101,10 +98,10 @@ merge_skyline (Array * a1, } } -Array +vector empty_skyline (Direction d) { - Array skyline; + vector skyline; Interval i; i.set_empty (); @@ -112,15 +109,15 @@ empty_skyline (Direction d) Skyline_entry e; e.width_ = i; e.height_ = -d * infinity_f; - skyline.push (e); + skyline.push_back (e); return skyline; } -Array -extents_to_skyline (Array const &extents, Axis a, Direction d) +vector +extents_to_skyline (vector const &extents, Axis a, Direction d) { - Array skyline = empty_skyline (d); + vector skyline = empty_skyline (d); /* This makes a cubic algorithm (array insertion is O (n), @@ -129,7 +126,7 @@ extents_to_skyline (Array 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. */ - for (int j = extents.size (); j--;) + for (vsize j = extents.size (); j--;) insert_extent_into_skyline (&skyline, extents[j], a, d); return skyline; @@ -142,8 +139,8 @@ extents_to_skyline (Array const &extents, Axis a, Direction d) This is an O (n) algorithm. */ Real -skyline_meshing_distance (Array const &buildings, - Array const &clouds) +skyline_meshing_distance (vector const &buildings, + vector const &clouds) { int i = buildings.size () -1; int j = clouds.size () -1; @@ -156,16 +153,12 @@ skyline_meshing_distance (Array const &buildings, 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]) - { - i--; - } + i--; else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT]) - { - j--; - } + j--; } return distance; @@ -180,12 +173,30 @@ Skyline_entry::Skyline_entry (Interval i, Real r) { width_ = i; height_ = r; - } void -heighten_skyline (Array *buildings, Real ground) +heighten_skyline (vector *buildings, Real ground) +{ + for (vsize i = 0; i < buildings->size (); i++) + buildings->at (i).height_ += ground; +} + +Real +skyline_height (vector const &buildings, + Real airplane, + Direction sky_dir) { - for (int i = 0; i < buildings->size (); i++) - buildings->elem_ref (i).height_ += ground; + 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; } +