X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=455ebb2b9b5c9897c93f8effeb5a5968d3dd3328;hb=9879bd7a67e4f72c6fa7f30eb355f2dc56f9a4bc;hp=45938efe0f1f1e6ab7e2a37e83a44e48b381bb8d;hpb=366ac5a9c6dfb5a32111c8dd6ba40e49334402c3;p=lilypond.git diff --git a/lily/skyline.cc b/lily/skyline.cc index 45938efe0f..455ebb2b9b 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -1,49 +1,46 @@ -/* +/* skyline.cc -- implement Skyline_entry and funcs. source file of the GNU LilyPond music typesetter - (c) 2002--2003 Han-Wen Nienhuys + (c) 2002--2005 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.top ().width_[RIGHT] = inf + skyline[0].width_[LEFT] = -inf +*/ -const Real EPS = 1e-12; +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 @@ -53,70 +50,67 @@ insert_extent_into_skyline (Array *line, Box b, Axis line_axis, 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 (int i = line->size (); i--;) { - Interval w = line->elem(i).width_; + Interval w = line->elem (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->elem (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->elem (i).width_[LEFT], extent[LEFT]); + Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]); - if (!e3.is_empty () && e3.length() > EPS) - line->insert (Skyline_entry (e3, my_height), i+1); + 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.is_empty () && e1.length() > EPS) - line->insert (Skyline_entry (e1, my_height), i ); + 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); } - - } } void -merge_skyline (Array * a1, - Array const & a2, +merge_skyline (Array *a1, + Array const &a2, Direction dir) { - for (int i = 0; i < a2.size(); i++) + 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 ; + b[Y_AXIS][-dir] = dir * infinity_f; insert_extent_into_skyline (a1, b, X_AXIS, dir); } } - Array empty_skyline (Direction d) { Array skyline; Interval i; - i.set_empty(); - i.swap(); + i.set_empty (); + i.swap (); Skyline_entry e; e.width_ = i; - e.height_ = -d * infinity_f; + e.height_ = -d * infinity_f; skyline.push (e); return skyline; } @@ -125,60 +119,58 @@ Array extents_to_skyline (Array const &extents, Axis a, Direction d) { - Array skyline = empty_skyline(d); + Array 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 const &buildings, Array 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_); - + 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--; } - 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--; - } + } } return distance; } -Skyline_entry::Skyline_entry() +Skyline_entry::Skyline_entry () { height_ = 0.0; } @@ -187,12 +179,11 @@ Skyline_entry::Skyline_entry (Interval i, Real r) { width_ = i; height_ = r; - } void heighten_skyline (Array *buildings, Real ground) { for (int i = 0; i < buildings->size (); i++) - buildings->elem_ref (i).height_ += ground; + buildings->elem_ref (i).height_ += ground; }