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