X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=f72ea5b2f6d5fcbf8c6cdf229d62077373b90c39;hb=2f7343c6c81e75989d087cab3557d6a8527609af;hp=33447faeb8f63796a51c9b2647757fa7aaba79ca;hpb=304b5f3aa7eee7b0ff8d4ba7526a1410735f6e74;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 33447faeb8..f72ea5b2f6 100644 --- 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 - (c) 2002--2004 Han-Wen Nienhuys + (c) 2002--2006 Han-Wen Nienhuys */ -#include "skyline.hh" - +#include "skyline.hh" /* 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[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. @@ -47,85 +42,82 @@ 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]; if (extent.is_empty ()) return; - + 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; - - 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) - 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_; 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); } } - -Array +vector empty_skyline (Direction d) { - Array skyline; + vector skyline; 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; } -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), @@ -133,46 +125,40 @@ 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; } - - /* minimum distance that can be achieved between baselines. "Clouds" is a skyline pointing down. 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; + 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_); - + 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; @@ -187,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 (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 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; +} +