2 skyline.cc -- implement Skyline_entry and funcs.
4 source file of the GNU LilyPond music typesetter
6 (c) 2002--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
12 A skyline is a shape of the form:
25 This file deals with building such skyline structure, and computing
26 the minimum distance between two opposing skylines.
29 Invariants for a skyline:
31 skyline[...].width_ forms a partition of the real interval, where
32 the segments are adjacent, and ascending. Hence we have
34 skyline.top ().width_[RIGHT] = inf
35 skyline[0].width_[LEFT] = -inf
40 const Real EPS = 1e-12;
43 TODO: avoid unnecessary fragmentation.
45 This is O (n^2), searching and insertion. Could be O (n log n) with
49 insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
52 Interval extent = b[line_axis];
53 if (extent.is_empty ())
56 Real stick_out = b[other_axis (line_axis)][d];
59 Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
61 for (int i = line->size (); i--;)
63 Interval w = line->elem (i).width_;
66 if (extent[LEFT] >= w[RIGHT])
69 Real my_height = line->elem (i).height_;
73 && d* (my_height - stick_out) < 0)
75 Interval e1 (line->elem (i).width_[LEFT], extent[LEFT]);
76 Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]);
78 if (!e3.is_empty () && e3.length () > EPS)
79 line->insert (Skyline_entry (e3, my_height), i+1);
81 line->elem_ref (i).height_ = stick_out;
82 line->elem_ref (i).width_ = w;
83 if (!e1.is_empty () && e1.length () > EPS)
84 line->insert (Skyline_entry (e1, my_height), i );
92 merge_skyline (Array<Skyline_entry> * a1,
93 Array<Skyline_entry> const & a2,
96 for (int i = 0; i < a2.size (); i++)
99 b[X_AXIS] = a2[i].width_;
100 b[Y_AXIS][dir] = a2[i].height_;
101 b[Y_AXIS][-dir] = dir * infinity_f ;
103 insert_extent_into_skyline (a1, b, X_AXIS, dir);
109 empty_skyline (Direction d)
111 Array<Skyline_entry> skyline;
118 e.height_ = -d * infinity_f;
124 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
127 Array<Skyline_entry> skyline = empty_skyline (d);
130 This makes a cubic algorithm (array insertion is O (n),
131 searching the array dumbly is O (n), and for n items, we get O (n^3).)
133 We could do a lot better (n log (n), using a balanced tree) but
134 that seems overkill for now.
136 for (int j = extents.size (); j--; )
137 insert_extent_into_skyline (&skyline, extents[j], a, d);
145 minimum distance that can be achieved between baselines. "Clouds" is
146 a skyline pointing down.
148 This is an O (n) algorithm.
151 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
152 Array<Skyline_entry> const &clouds)
154 int i = buildings.size () -1;
155 int j = clouds.size () -1;
157 Real distance = - infinity_f;
159 while (i > 0 || j > 0)
161 Interval w = buildings[i].width_;
162 w.intersect (clouds[j].width_);
165 distance = distance >? (buildings[i].height_ - clouds[j].height_);
167 if (i>0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
171 else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
180 Skyline_entry::Skyline_entry ()
185 Skyline_entry::Skyline_entry (Interval i, Real r)
193 heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
195 for (int i = 0; i < buildings->size (); i++)
196 buildings->elem_ref (i).height_ += ground;