]> git.donarmstrong.com Git - lilypond.git/blob - lily/skyline.cc
Basic-notation reorg and misc small fixes.
[lilypond.git] / lily / skyline.cc
1 /*
2   skyline.cc -- implement Skyline_entry and funcs.
3
4   source file of the GNU LilyPond music typesetter
5
6   (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
7 */
8
9 #include "skyline.hh"
10
11 /*
12   A skyline is a shape of the form:
13
14
15   *                  ----
16   *                  |  |
17   *         ---------|  |
18   *         |           |
19   *         |           |
20   *         |           |______
21   * --------|                 |___
22   *
23
24   This file deals with building such skyline structure, and computing
25   the minimum distance between two opposing skylines.
26
27   Invariants for a skyline:
28
29   skyline[...].width_ forms a partition of the real interval, where
30   the segments are adjacent, and ascending. Hence we have
31
32   skyline.back ().width_[RIGHT] = inf
33   skyline[0].width_[LEFT] = -inf
34 */
35
36 const Real EPS = 1e-12;
37
38 /*
39   TODO: avoid unnecessary fragmentation.
40
41   This is O (n^2), searching and insertion.  Could be O (n log n) with
42   binsearch.
43 */
44 void
45 insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
46                             Direction d)
47 {
48   Interval extent = b[line_axis];
49   if (extent.is_empty ())
50     return;
51
52   Real stick_out = b[other_axis (line_axis)][d];
53
54   /*
55     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
56   */
57   for (vsize i = line->size (); i--;)
58     {
59       Interval w = line->at (i).width_;
60       w.intersect (extent);
61
62       if (extent[LEFT] >= w[RIGHT])
63         break;
64
65       Real my_height = line->at (i).height_;
66
67       if (!w.is_empty ()
68           && w.length () > EPS
69           && d * (my_height - stick_out) < 0)
70         {
71           Interval e1 (line->at (i).width_[LEFT], extent[LEFT]);
72           Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);
73
74           if (!e3.is_empty () && e3.length () > EPS)
75             line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height));
76
77           line->at (i).height_ = stick_out;
78           line->at (i).width_ = w;
79           if (!e1.is_empty () && e1.length () > EPS)
80             line->insert (line->begin () + i, Skyline_entry (e1, my_height));
81         }
82     }
83 }
84
85 void
86 merge_skyline (vector<Skyline_entry> *a1,
87                vector<Skyline_entry> const &a2,
88                Direction dir)
89 {
90   for (vsize i = 0; i < a2.size (); i++)
91     {
92       Box b;
93       b[X_AXIS] = a2[i].width_;
94       b[Y_AXIS][dir] = a2[i].height_;
95       b[Y_AXIS][-dir] = dir * infinity_f;
96
97       insert_extent_into_skyline (a1, b, X_AXIS, dir);
98     }
99 }
100
101 vector<Skyline_entry>
102 empty_skyline (Direction d)
103 {
104   vector<Skyline_entry> skyline;
105
106   Interval i;
107   i.set_empty ();
108   i.swap ();
109   Skyline_entry e;
110   e.width_ = i;
111   e.height_ = -d * infinity_f;
112   skyline.push_back (e);
113   return skyline;
114 }
115
116 vector<Skyline_entry>
117 extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)
118 {
119
120   vector<Skyline_entry> skyline = empty_skyline (d);
121
122   /*
123     This makes a cubic algorithm (array  insertion is O (n),
124     searching the array dumbly is O (n), and for n items, we get O (n^3).)
125
126     We could do a lot better (n log (n), using a balanced tree) but
127     that seems overkill for now.
128   */
129   for (vsize j = extents.size (); j--;)
130     insert_extent_into_skyline (&skyline, extents[j], a, d);
131
132   return skyline;
133 }
134
135 /*
136   minimum distance that can be achieved between baselines. "Clouds" is
137   a skyline pointing down.
138
139   This is an O (n) algorithm.
140 */
141 Real
142 skyline_meshing_distance (vector<Skyline_entry> const &buildings,
143                           vector<Skyline_entry> const &clouds)
144 {
145   int i = buildings.size () -1;
146   int j = clouds.size () -1;
147
148   Real distance = -infinity_f;
149
150   while (i > 0 || j > 0)
151     {
152       Interval w = buildings[i].width_;
153       w.intersect (clouds[j].width_);
154
155       if (!w.is_empty ())
156         distance = max (distance, (buildings[i].height_ - clouds[j].height_));
157
158       if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
159         i--;
160       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
161         j--;
162     }
163
164   return distance;
165 }
166
167 Skyline_entry::Skyline_entry ()
168 {
169   height_ = 0.0;
170 }
171
172 Skyline_entry::Skyline_entry (Interval i, Real r)
173 {
174   width_ = i;
175   height_ = r;
176 }
177
178 void
179 heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
180 {
181   for (vsize i = 0; i < buildings->size (); i++)
182     buildings->at (i).height_ += ground;
183 }
184
185 Real
186 skyline_height (vector<Skyline_entry> const &buildings,
187                 Real airplane,
188                 Direction sky_dir)
189 {
190   Real h = - sky_dir * infinity_f;
191
192   /*
193     Ugh! linear, should be O(log n).
194    */
195   for (vsize i = 0; i < buildings.size (); i++)
196     if (buildings[i].width_.contains (airplane))
197       h = sky_dir * max (sky_dir * h,
198                          sky_dir * buildings[i].height_);
199   
200   return h;
201 }
202