2 skyline.cc -- implement Skyline_entry and funcs.
4 source file of the GNU LilyPond music typesetter
6 (c) 2002 Han-Wen Nienhuys <hanwen@cs.uu.nl>
13 A skyline is a shape of the form:
26 This file deals with building such skyline structure, and computing
27 the minimum distance between two opposing skylines.
30 Invariants for a skyline:
32 skyline[...].width_ forms a partition of the real interval, where
33 the segments are adjacent, and ascending. Hence we have
35 skyline.top().width_[RIGHT] = inf
36 skyline[0].width_[LEFT] = -inf
42 TODO: avoid unnecessary fragmentation.
44 This is O(n^2), searching and insertion. Could be O(n log n) with
48 insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
51 Interval extent = b[line_axis];
55 Real stick_out = b[other_axis (line_axis)][d];
57 for (int i = line->size(); i--;)
59 Interval w = line->elem(i).width_;
60 if (extent[LEFT] > w[RIGHT])
64 Real my_height = line->elem(i).height_;
66 if (!w.empty_b () && d* (my_height - stick_out) < 0)
68 Interval e1 (line->elem(i).width_[LEFT], extent[LEFT]);
69 Interval e3 (extent[RIGHT], line->elem(i).width_[RIGHT]);
72 line->insert (Skyline_entry (e3, my_height), i+1);
74 line->elem_ref(i).height_ = stick_out;
75 line->elem_ref(i).width_ = w;
77 line->insert (Skyline_entry (e1, my_height), i );
86 empty_skyline (Direction d)
88 Array<Skyline_entry> skyline;
95 e.height_ = -d * infinity_f;
101 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
104 Array<Skyline_entry> skyline = empty_skyline(d);
107 This makes a cubic algorithm (array insertion is O(n),
108 searching the array dumbly is O(n), and for n items, we get O(n^3).)
110 We could do a lot better (n log (n), using a balanced tree) but
111 that seems overkill for now.
113 for (int j = extents.size(); j--; )
114 insert_extent_into_skyline (&skyline, extents[j], a, d);
121 minimum distance that can be achieved between baselines. "Clouds" is
122 a skyline pointing down.
124 This is an O(n) algorithm.
127 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
128 Array<Skyline_entry> const &clouds)
130 int i = buildings.size () -1;
131 int j = clouds.size() -1;
133 Real distance = - infinity_f;
135 while (i > 0 || j > 0)
137 Interval w = buildings[i].width_;
138 w.intersect(clouds[j].width_);
141 distance = distance >? (buildings[i].height_ - clouds[j].height_);
143 if (i>0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
147 else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
156 Skyline_entry::Skyline_entry()
161 Skyline_entry::Skyline_entry (Interval i, Real r)