Left: | ||
Right: |
OLD | NEW |
---|---|
1 /* | 1 /* |
2 This file is part of LilyPond, the GNU music typesetter. | 2 This file is part of LilyPond, the GNU music typesetter. |
3 | 3 |
4 Copyright (C) 2006--2014 Joe Neeman <joeneeman@gmail.com> | 4 Copyright (C) 2006--2014 Joe Neeman <joeneeman@gmail.com> |
5 | 5 |
6 LilyPond is free software: you can redistribute it and/or modify | 6 LilyPond is free software: you can redistribute it and/or modify |
7 it under the terms of the GNU General Public License as published by | 7 it under the terms of the GNU General Public License as published by |
8 the Free Software Foundation, either version 3 of the License, or | 8 the Free Software Foundation, either version 3 of the License, or |
9 (at your option) any later version. | 9 (at your option) any later version. |
10 | 10 |
11 LilyPond is distributed in the hope that it will be useful, | 11 LilyPond is distributed in the hope that it will be useful, |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | 12 but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 GNU General Public License for more details. | 14 GNU General Public License for more details. |
15 | 15 |
16 You should have received a copy of the GNU General Public License | 16 You should have received a copy of the GNU General Public License |
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. | 17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. |
18 */ | 18 */ |
19 | 19 |
20 #include "skyline.hh" | 20 #include "skyline.hh" |
21 #include "skyline-pair.hh" | 21 #include "skyline-pair.hh" |
22 #include <deque> | 22 #include <deque> |
23 #include <cstdio> | 23 #include <cstdio> |
24 | 24 |
25 | |
26 /* A skyline is a sequence of non-overlapping buildings: something like | 25 /* A skyline is a sequence of non-overlapping buildings: something like |
27 this: | 26 this: |
28 _______ | 27 _______ |
29 | \ ________ | 28 | \ ________ |
30 | \ ________/ \ | 29 | \ ________/ \ |
31 /\ | \ / \ | 30 /\ | \ / \ |
32 / -------- \ / \ | 31 / -------- \ / \ |
33 / \ / \ | 32 / \ / \ |
34 / ------------/ ---- | 33 / ------------/ ---- |
35 -- | 34 -- |
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
117 if (start_height != end_height) | 116 if (start_height != end_height) |
118 slope_ = (end_height - start_height) / (end - start); | 117 slope_ = (end_height - start_height) / (end - start); |
119 | 118 |
120 assert (!isinf (slope_) && !isnan (slope_)); | 119 assert (!isinf (slope_) && !isnan (slope_)); |
121 | 120 |
122 if (isinf (start)) | 121 if (isinf (start)) |
123 { | 122 { |
124 assert (start_height == end_height); | 123 assert (start_height == end_height); |
125 y_intercept_ = start_height; | 124 y_intercept_ = start_height; |
126 } | 125 } |
127 else if (fabs(slope_) > 1e6) | 126 else if (fabs (slope_) > 1e6) |
128 // too steep to be stored in slope-intercept form, given round-off error | 127 // too steep to be stored in slope-intercept form, given round-off error |
129 { | 128 { |
130 slope_ = 0.0; | 129 slope_ = 0.0; |
131 y_intercept_ = max(start_height, end_height); | 130 y_intercept_ = max (start_height, end_height); |
132 } | 131 } |
133 else | 132 else |
134 y_intercept_ = start_height - slope_ * start; | 133 y_intercept_ = start_height - slope_ * start; |
135 } | 134 } |
136 | 135 |
137 inline Real | 136 inline Real |
138 Building::height (Real x) const | 137 Building::height (Real x) const |
139 { | 138 { |
140 return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; | 139 return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; |
141 } | 140 } |
(...skipping 26 matching lines...) Expand all Loading... | |
168 // Solve for s: y = (x + s)*m + b | 167 // Solve for s: y = (x + s)*m + b |
169 Real ret = (y - y_intercept_ - slope_ * x) / slope_; | 168 Real ret = (y - y_intercept_ - slope_ * x) / slope_; |
170 | 169 |
171 if (ret >= start_ && ret <= end_ && !isinf (ret)) | 170 if (ret >= start_ && ret <= end_ && !isinf (ret)) |
172 return ret; | 171 return ret; |
173 return infinity_f; | 172 return infinity_f; |
174 } | 173 } |
175 | 174 |
176 static Real | 175 static Real |
177 first_intersection (Building const &b, list<Building> *s, Real start_x) | 176 first_intersection (Building const &b, list<Building> *s, Real start_x) |
178 /* Return the first x >= start_x where skyline s above Building b. | 177 /* Return the first x (start_x <= x <= b.end) |
179 * Removes buildings from s that are concealed by b. */ | 178 * where skyline s is clear of Building b. |
179 * Removes buildings from s that are fully concealed by b. */ | |
180 { | 180 { |
181 while (!s->empty () && start_x < b.end_) | 181 for ( ; !s->empty (); s->pop_front ()) |
182 { | 182 { |
183 Building c = s->front (); | 183 Building c = s->front (); |
184 | 184 |
185 // conceals and intersection_x involve multiplication and | 185 start_x = max (start_x, c.start_); |
186 if (start_x >= b.end_) | |
187 return b.end_; | |
188 | |
189 // height and intersection_x involve multiplication and | |
186 // division. Avoid that, if we can. | 190 // division. Avoid that, if we can. |
187 if (c.y_intercept_ == -infinity_f) | 191 if (c.y_intercept_ != -infinity_f) |
188 { | 192 { |
189 if (c.end_ > b.end_) | 193 if (c.height (start_x) > b.height (start_x)) |
190 return b.end_; | 194 return start_x; |
191 start_x = c.end_; | 195 |
192 s->pop_front (); | 196 if (c.height (b.end_) > b.height (b.end_)) |
193 continue; | 197 { |
198 Real i = b.intersection_x (c); | |
199 if (i <= b.end_ && i <= c.end_) | |
200 return max (start_x, i); | |
201 } | |
194 } | 202 } |
195 | 203 if (c.end_ >= b.end_) |
196 if (c.conceals (b, start_x)) | 204 return b.end_; // leave this c on the list s |
197 return start_x; | |
198 | |
199 Real i = b.intersection_x (c); | |
200 if (i > start_x && i <= b.end_ && i <= c.end_) | |
201 return i; | |
202 | |
203 start_x = c.end_; | |
204 if (b.end_ > c.end_) | |
205 s->pop_front (); | |
206 } | 205 } |
207 return b.end_; | 206 return b.end_; |
208 } | 207 } |
209 | 208 |
210 bool | |
211 Building::conceals (Building const &other, Real x) const | |
212 { | |
213 if (slope_ == other.slope_) | |
214 return y_intercept_ > other.y_intercept_; | |
215 | |
216 /* their slopes were not equal, so there is an intersection point */ | |
217 Real i = intersection_x (other); | |
218 return (i <= x && slope_ > other.slope_) | |
219 || (i > x && slope_ < other.slope_); | |
220 } | |
221 | |
222 // Remove redundant empty buildings from the skyline. | 209 // Remove redundant empty buildings from the skyline. |
223 // If there are two adjacent empty buildings, they can be | 210 // If there are two adjacent empty buildings, they can be |
224 // turned into one. | 211 // turned into one. |
225 void | 212 void |
226 Skyline::normalize () | 213 Skyline::normalize () |
227 { | 214 { |
228 bool last_empty = false; | 215 bool last_empty = false; |
229 list<Building>::iterator i; | 216 list<Building>::iterator i; |
230 | 217 |
231 for (i = buildings_.begin (); i != buildings_.end (); i++) | 218 for (i = buildings_.begin (); i != buildings_.end (); i++) |
(...skipping 20 matching lines...) Expand all Loading... | |
252 // assume that there are never two adjacent empty buildings. | 239 // assume that there are never two adjacent empty buildings. |
253 // That is, if center is empty then left and right are not. | 240 // That is, if center is empty then left and right are not. |
254 list<Building>::iterator left = buildings_.begin (); | 241 list<Building>::iterator left = buildings_.begin (); |
255 list<Building>::iterator center = buildings_.begin (); | 242 list<Building>::iterator center = buildings_.begin (); |
256 list<Building>::iterator right; | 243 list<Building>::iterator right; |
257 | 244 |
258 for (right = buildings_.begin (); right != buildings_.end (); right++) | 245 for (right = buildings_.begin (); right != buildings_.end (); right++) |
259 { | 246 { |
260 if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) | 247 if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) |
261 { | 248 { |
249 printf ("We are here"); | |
lemzwerg
2014/12/22 04:25:43
Debugging remnants?
Keith
2014/12/22 04:58:08
Proving that code is dead before I remove it.
| |
250 exit (17); // not-reached | |
262 Real p1 = left->height (left->end_); | 251 Real p1 = left->height (left->end_); |
263 Real p2 = right->height (right->start_); | 252 Real p2 = right->height (right->start_); |
264 *center = Building (center->start_, p1, p2, center->end_); | 253 *center = Building (center->start_, p1, p2, center->end_); |
265 | 254 |
266 left = center; | 255 left = center; |
267 center = right; | 256 center = right; |
268 } | 257 } |
269 } | 258 } |
270 } | 259 } |
271 | 260 |
272 void | 261 void |
273 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, | 262 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, |
274 list<Building> *const result) const | 263 list<Building> *const result) const |
275 { | 264 { |
276 if (s1->empty () || s2->empty ()) | 265 if (s1->empty () && s2->empty ()) |
266 programming_error ("tried to merge two empty skylines"); | |
267 | |
268 bool s2_pending = false; | |
269 Real last_end = -infinity_f; | |
270 while (!s1->empty () && !s2->empty ()) | |
277 { | 271 { |
278 programming_error ("tried to merge an empty skyline"); | |
279 return; | |
280 } | |
281 | |
282 Real x = -infinity_f; | |
283 Real last_end = -infinity_f; | |
284 while (!s1->empty ()) | |
285 { | |
286 if (s2->front ().conceals (s1->front (), x)) | |
287 swap (s1, s2); | |
288 | |
289 Building b = s1->front (); | 272 Building b = s1->front (); |
290 Building c = s2->front (); | 273 Building c = s2->front (); |
274 if (s2_pending // the head of s2 starts before the head of s1 | |
275 || c.height (last_end) > b.height (last_end)) | |
276 { | |
277 swap (s1, s2); | |
278 swap (b, c); | |
279 } | |
280 // Now b, the head of s1, starts earlier or lies above s2. | |
291 | 281 |
292 // Optimization: if the other skyline is empty at this point, | 282 // Optimization: if the other skyline is empty at this point, |
293 // we can avoid testing some intersections. Just grab as many | 283 // we can avoid testing some intersections. Just grab as many |
294 // buildings from s1 as we can, and shove them onto the output. | 284 // buildings from s1 as we can, and shove them onto the output. |
295 if (c.y_intercept_ == -infinity_f | 285 if (c.y_intercept_ == -infinity_f |
296 && c.end_ >= b.end_) | 286 && c.end_ >= b.end_) |
297 { | 287 { |
298 list<Building>::iterator i = s1->begin (); | 288 list<Building>::iterator i = s1->begin (); |
299 i++; | 289 i++; |
300 while (i != s1->end () && i->end_ <= c.end_) | 290 while (i != s1->end () && i->end_ <= c.end_) |
301 i++; | 291 i++; |
302 | 292 |
303 s1->front ().start_ = x; | 293 s1->front ().start_ = last_end; |
304 result->splice (result->end (), *s1, s1->begin (), i); | 294 result->splice (result->end (), *s1, s1->begin (), i); |
305 x = result->back ().end_; | 295 last_end = result->back ().end_; |
306 last_end = x; | |
307 continue; | 296 continue; |
308 } | 297 } |
309 // first_intersection() removes buildings from s2 if b hides them | 298 // first_intersection() removes buildings from s2 if b hides them |
310 Real end = first_intersection (b, s2, x); | 299 Real x = first_intersection (b, s2, last_end); |
311 if (s2->empty ()) | 300 if (s2->empty ()) |
301 break; | |
302 | |
303 if (x > last_end) | |
312 { | 304 { |
313 b.start_ = last_end; | 305 b.leading_part (x); // chops b, leaving the part up to x |
314 result->push_back (b); | |
315 break; | |
316 } | |
317 | |
318 // Should be (end > x), during ver2.19. end == x happens fairly often, | |
319 // and we do not need to keep vertical segments within a skyline. | |
320 if (end >= x) | |
321 { | |
322 b.leading_part (end); | |
323 b.start_ = last_end; | 306 b.start_ = last_end; |
324 last_end = b.end_; | 307 last_end = b.end_; |
325 result->push_back (b); | 308 result->push_back (b); |
326 } | 309 } |
327 | 310 |
328 if (end >= s1->front ().end_) | 311 b = s1->front (); |
329 s1->pop_front (); | 312 c = s2->front (); |
330 // Should add during ver2.19 (to avoid an endless loop | 313 if (b.end_ <= c.end_) |
331 // when merging identical skylines with a vertical segment) | 314 { |
332 // if (end >= s2->front().end_) s2->pop_front(); | 315 // Any trailing part of b is concealed by c |
333 | 316 s1->pop_front (); |
334 x = end; | 317 // Consider c next for inclusion in the merged skyline |
318 s2_pending = true; | |
319 } | |
320 else | |
321 { | |
322 // the trailing part of c is fully exposed, goes directly to merged | |
323 s2->pop_front (); | |
324 c.start_ = last_end; | |
325 last_end = c.end_; | |
326 result->push_back (c); | |
327 } | |
328 } | |
329 if (last_end < infinity_f) | |
330 { | |
331 if (!s1->empty ()) | |
332 { | |
333 s1->front ().start_ = last_end; | |
334 result->splice (result->end (), *s1); | |
335 } | |
336 else if (!s2->empty ()) | |
337 { | |
338 s2->front ().start_ = last_end; | |
339 result->splice (result->end (), *s2); | |
340 } | |
335 } | 341 } |
336 } | 342 } |
337 | 343 |
338 static void | 344 static void |
339 empty_skyline (list<Building> *const ret) | 345 empty_skyline (list<Building> *const ret) |
340 { | 346 { |
341 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)) ; | 347 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)) ; |
342 } | 348 } |
343 | 349 |
344 /* | 350 /* |
(...skipping 577 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
922 } | 928 } |
923 | 929 |
924 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", | 930 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", |
925 1, 0, 0, (SCM sky), | 931 1, 0, 0, (SCM sky), |
926 "Return whether @var{sky} is empty.") | 932 "Return whether @var{sky} is empty.") |
927 { | 933 { |
928 Skyline *s = Skyline::unsmob (sky); | 934 Skyline *s = Skyline::unsmob (sky); |
929 LY_ASSERT_SMOB (Skyline, sky, 1); | 935 LY_ASSERT_SMOB (Skyline, sky, 1); |
930 return scm_from_bool (s->is_empty ()); | 936 return scm_from_bool (s->is_empty ()); |
931 } | 937 } |
OLD | NEW |