2 skyline.cc -- implement Skyline_entry and funcs.
4 source file of the GNU LilyPond music typesetter
6 (c) 2002--2005 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
38 const Real EPS = 1e-12;
41 TODO: avoid unnecessary fragmentation.
43 This is O (n^2), searching and insertion. Could be O (n log n) with
47 insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
50 Interval extent = b[line_axis];
51 if (extent.is_empty ())
54 Real stick_out = b[other_axis (line_axis)][d];
57 Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
59 for (int i = line->size (); i--;)
61 Interval w = line->elem (i).width_;
64 if (extent[LEFT] >= w[RIGHT])
67 Real my_height = line->elem (i).height_;
71 && d * (my_height - stick_out) < 0)
73 Interval e1 (line->elem (i).width_[LEFT], extent[LEFT]);
74 Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]);
76 if (!e3.is_empty () && e3.length () > EPS)
77 line->insert (Skyline_entry (e3, my_height), i + 1);
79 line->elem_ref (i).height_ = stick_out;
80 line->elem_ref (i).width_ = w;
81 if (!e1.is_empty () && e1.length () > EPS)
82 line->insert (Skyline_entry (e1, my_height), i);
88 merge_skyline (Array<Skyline_entry> *a1,
89 Array<Skyline_entry> const &a2,
92 for (int i = 0; i < a2.size (); i++)
95 b[X_AXIS] = a2[i].width_;
96 b[Y_AXIS][dir] = a2[i].height_;
97 b[Y_AXIS][-dir] = dir * infinity_f;
99 insert_extent_into_skyline (a1, b, X_AXIS, dir);
104 empty_skyline (Direction d)
106 Array<Skyline_entry> skyline;
113 e.height_ = -d * infinity_f;
119 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
122 Array<Skyline_entry> skyline = empty_skyline (d);
125 This makes a cubic algorithm (array insertion is O (n),
126 searching the array dumbly is O (n), and for n items, we get O (n^3).)
128 We could do a lot better (n log (n), using a balanced tree) but
129 that seems overkill for now.
131 for (int j = extents.size (); j--;)
132 insert_extent_into_skyline (&skyline, extents[j], a, d);
138 minimum distance that can be achieved between baselines. "Clouds" is
139 a skyline pointing down.
141 This is an O (n) algorithm.
144 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
145 Array<Skyline_entry> const &clouds)
147 int i = buildings.size () -1;
148 int j = clouds.size () -1;
150 Real distance = -infinity_f;
152 while (i > 0 || j > 0)
154 Interval w = buildings[i].width_;
155 w.intersect (clouds[j].width_);
158 distance = max (distance, (buildings[i].height_ - clouds[j].height_));
160 if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
164 else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
173 Skyline_entry::Skyline_entry ()
178 Skyline_entry::Skyline_entry (Interval i, Real r)
185 heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
187 for (int i = 0; i < buildings->size (); i++)
188 buildings->elem_ref (i).height_ += ground;