]> git.donarmstrong.com Git - lilypond.git/blob - lily/skyline.cc
* lily/accidental-placement.cc (position_accidentals): document
[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 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.empty_b())
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.empty_b () &&
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.empty_b () && 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.empty_b () && e1.length() > EPS)
85             line->insert (Skyline_entry (e1, my_height), i );
86         }
87
88
89     }
90 }
91
92
93 Array<Skyline_entry>
94 empty_skyline (Direction d)
95 {
96   Array<Skyline_entry> skyline;
97
98   Interval i;
99   i.set_empty();
100   i.swap();
101   Skyline_entry e;
102   e.width_ = i;
103   e.height_ = -d * infinity_f; 
104   skyline.push (e);
105   return skyline;
106 }
107
108 Array<Skyline_entry>
109 extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
110 {
111
112   Array<Skyline_entry> skyline = empty_skyline(d);
113
114   /*
115     This makes a cubic algorithm (array  insertion is O(n),
116     searching the array dumbly is O(n), and for n items, we get O(n^3).)
117
118     We could do a lot better (n log (n), using a balanced tree) but
119     that seems overkill for now.
120    */
121   for (int j = extents.size(); j--; )
122     insert_extent_into_skyline (&skyline, extents[j], a, d);
123
124   return skyline;
125 }
126
127
128 /*
129   minimum distance that can be achieved between baselines. "Clouds" is
130   a skyline pointing down.
131
132   This is an O(n) algorithm.
133  */
134 Real
135 skyline_meshing_distance (Array<Skyline_entry> const &buildings,
136                           Array<Skyline_entry> const &clouds)
137 {
138   int i = buildings.size () -1;
139   int j  = clouds.size() -1;
140
141   Real distance = - infinity_f;
142   
143   while (i > 0 || j > 0)
144     {
145       Interval w = buildings[i].width_;
146       w.intersect(clouds[j].width_);
147       
148       if (!w.empty_b())
149         distance = distance >? (buildings[i].height_ - clouds[j].height_);
150
151       if (i>0 && buildings[i].width_[LEFT] >=  clouds[j].width_[LEFT])
152         {
153           i--;
154         }
155       else if (j > 0 && buildings[i].width_[LEFT] <=  clouds[j].width_[LEFT])
156         {
157           j--;
158         }       
159     }
160
161   return distance;
162 }
163
164 Skyline_entry::Skyline_entry()
165 {
166   height_ = 0.0;
167 }
168
169 Skyline_entry::Skyline_entry (Interval i, Real r)
170 {
171   width_ = i;
172   height_ = r;
173   
174 }