LEFT | RIGHT |
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--2020 Joe Neeman <joeneeman@gmail.com> | 4 Copyright (C) 2006--2020 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 using std::deque; | 25 using std::deque; |
26 using std::list; | |
27 using std::vector; | 26 using std::vector; |
28 | 27 |
29 /* A skyline is a sequence of non-overlapping buildings: something like | 28 /* A skyline is a sequence of non-overlapping buildings: something like |
30 this: | 29 this: |
31 _______ | 30 _______ |
32 | \ ________ | 31 | \ ________ |
33 | \ ________/ \ | 32 | \ ________/ \ |
34 /\ | \ / \ | 33 /\ | \ / \ |
35 / -------- \ / \ | 34 / -------- \ / \ |
36 / \ / \ | 35 / \ / \ |
(...skipping 26 matching lines...) Expand all Loading... |
63 Also, some target machines use the x87 floating point unit, which provides | 62 Also, some target machines use the x87 floating point unit, which provides |
64 extended precision for intermediate results held in registers. On this type | 63 extended precision for intermediate results held in registers. On this type |
65 of hardware comparisons such as | 64 of hardware comparisons such as |
66 double c = 1.0/3.0; boolean compare = (c == 1.0/3.0) | 65 double c = 1.0/3.0; boolean compare = (c == 1.0/3.0) |
67 could go either way because the 1.0/3.0 is allowed to be kept | 66 could go either way because the 1.0/3.0 is allowed to be kept |
68 higher precision than the variable 'c'. | 67 higher precision than the variable 'c'. |
69 Alert to these considerations, we now accept buildings of zero-width. | 68 Alert to these considerations, we now accept buildings of zero-width. |
70 */ | 69 */ |
71 | 70 |
72 static void | 71 static void |
73 print_buildings (list<Building> const &b) | 72 print_buildings (vector<Building> const &b) |
74 { | 73 { |
75 for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++) | 74 for (auto i : b) |
76 i->print (); | 75 i.print (); |
77 } | 76 } |
78 | 77 |
79 void | 78 void |
80 Skyline::print () const | 79 Skyline::print () const |
81 { | 80 { |
82 print_buildings (buildings_); | 81 print_buildings (buildings_); |
83 } | 82 } |
84 | 83 |
85 void | 84 void |
86 Skyline::print_points () const | 85 Skyline::print_points () const |
87 { | 86 { |
88 vector<Offset> ps (to_points (X_AXIS)); | 87 vector<Offset> ps (to_points (X_AXIS)); |
89 | 88 |
90 for (vsize i = 0; i < ps.size (); i++) | 89 int i = 0; |
91 printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS], | 90 for (Offset p : ps) |
92 (i % 2) == 1 ? "\n" : " "); | 91 printf ("(%f,%f)%s", p[X_AXIS], p[Y_AXIS], (i++ % 2) == 1 ? "\n" : " "); |
93 } | 92 } |
94 | 93 |
95 Building::Building (Real start, Real start_height, Real end_height, Real end) | 94 Building::Building (Real start, Real start_height, Real end_height, Real end) |
96 : x_ (start, end) | 95 : x_ (start, end) |
97 { | 96 { |
98 if (std::isinf (start) || std::isinf (end)) | 97 if (std::isinf (start) || std::isinf (end)) |
99 assert (start_height == end_height); | 98 assert (start_height == end_height); |
100 | 99 |
101 precompute (start_height, end_height); | 100 precompute (start_height, end_height); |
102 } | 101 } |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
167 } | 166 } |
168 | 167 |
169 bool | 168 bool |
170 Building::above (Building const &other, Real x) const | 169 Building::above (Building const &other, Real x) const |
171 { | 170 { |
172 return (std::isinf (y_intercept_) || std::isinf (other.y_intercept_) || std::i
sinf (x)) | 171 return (std::isinf (y_intercept_) || std::isinf (other.y_intercept_) || std::i
sinf (x)) |
173 ? y_intercept_ > other.y_intercept_ | 172 ? y_intercept_ > other.y_intercept_ |
174 : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_; | 173 : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_; |
175 } | 174 } |
176 | 175 |
177 // Remove redundant empty buildings from the skyline. | 176 void |
178 // If there are two adjacent empty buildings, they can be | 177 Skyline::internal_merge_skyline (vector<Building> const *sbp, |
179 // turned into one. | 178 vector<Building> const *scp, |
180 void | 179 vector<Building> *result) const |
181 Skyline::normalize () | 180 { |
182 { | 181 if (sbp->empty () || scp->empty ()) |
183 bool last_empty = false; | |
184 list<Building>::iterator i; | |
185 | |
186 for (i = buildings_.begin (); i != buildings_.end (); i++) | |
187 { | |
188 if (last_empty && i->y_intercept_ == -infinity_f) | |
189 { | |
190 list<Building>::iterator last = i; | |
191 last--; | |
192 last->x_[RIGHT] = i->x_[RIGHT]; | |
193 buildings_.erase (i); | |
194 i = last; | |
195 } | |
196 last_empty = (i->y_intercept_ == -infinity_f); | |
197 } | |
198 | |
199 assert (buildings_.front ().x_[LEFT] == -infinity_f); | |
200 assert (buildings_.back ().x_[RIGHT] == infinity_f); | |
201 } | |
202 | |
203 void | |
204 Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc, | |
205 list<Building> *const result) const | |
206 { | |
207 if (sb->empty () || sc->empty ()) | |
208 { | 182 { |
209 programming_error ("tried to merge an empty skyline"); | 183 programming_error ("tried to merge an empty skyline"); |
210 return; | 184 return; |
211 } | 185 } |
212 | 186 result->reserve (std::max (sbp->size (), scp->size ())); |
213 Building b = sb->front (); | 187 auto bit = sbp->begin (); |
214 for (; !sc->empty (); sc->pop_front ()) | 188 auto cit = scp->begin (); |
| 189 |
| 190 Building b = *bit; |
| 191 for (; cit != scp->end (); ++cit) |
215 { | 192 { |
216 /* Building b is continuing from the previous pass through the loop. | 193 /* Building b is continuing from the previous pass through the loop. |
217 Building c is newly-considered, and starts no earlier than b started. | 194 Building c is newly-considered, and starts no earlier than b started. |
218 The comments draw b as if its roof had zero slope ----. | 195 The comments draw b as if its roof had zero slope ----. |
219 with dashes where b lies above c. | 196 with dashes where b lies above c. |
220 The roof of c could rise / or fall \ through the roof of b, | 197 The roof of c could rise / or fall \ through the roof of b, |
221 or the vertical sides | of c could intersect the roof of b. */ | 198 or the vertical sides | of c could intersect the roof of b. */ |
222 Building c = sc->front (); | 199 Building c = *cit; |
223 if (b.x_[RIGHT] < c.x_[RIGHT]) /* finish with b */ | 200 if (b.x_[RIGHT] < c.x_[RIGHT]) /* finish with b */ |
224 { | 201 { |
225 if (b.x_[RIGHT] <= b.x_[LEFT]) /* we are already finished with b */ | 202 if (b.x_[RIGHT] <= b.x_[LEFT]) /* we are already finished with b */ |
226 ; | 203 ; |
227 else if (c.above (b, c.x_[LEFT])) /* -| . | */ | 204 else if (c.above (b, c.x_[LEFT])) /* -| . | */ |
228 { | 205 { |
229 Building m (b); | 206 Building m (b); |
230 m.x_[RIGHT] = c.x_[LEFT]; | 207 m.x_[RIGHT] = c.x_[LEFT]; |
231 if (m.x_[RIGHT] > m.x_[LEFT]) | 208 if (m.x_[RIGHT] > m.x_[LEFT]) |
232 result->push_back (m); | 209 result->push_back (m); |
233 if (b.above (c, b.x_[RIGHT])) /* -|\--. */ | 210 if (b.above (c, b.x_[RIGHT])) /* -|\--. */ |
234 { | 211 { |
235 Building n (c); | 212 Building n (c); |
236 n.x_[RIGHT] = b.x_[LEFT] = b.intersection_x (c); | 213 n.x_[RIGHT] = b.x_[LEFT] = b.intersection_x (c); |
237 result->push_back (n); | 214 result->push_back (n); |
238 result->push_back (b); | 215 result->push_back (b); |
239 } | 216 } |
240 } | 217 } |
241 else | 218 else |
242 { | 219 { |
243 if (c.above (b, b.x_[RIGHT])) /* ---/ . | */ | 220 if (c.above (b, b.x_[RIGHT])) /* ---/ . | */ |
244 b.x_[RIGHT] = b.intersection_x (c); | 221 b.x_[RIGHT] = b.intersection_x (c); |
245 else /* -----. */ | 222 else /* -----. */ |
246 c.x_[LEFT] = b.x_[RIGHT]; | 223 c.x_[LEFT] = b.x_[RIGHT]; |
247 result->push_back (b); | 224 result->push_back (b); |
248 } | 225 } |
249 /* 'c' continues further, so move it into 'b' for the next pass. */ | 226 /* 'c' continues further, so move it into 'b' for the next pass. */ |
250 b = c; | 227 b = c; |
251 std::swap (sb, sc); | 228 std::swap (bit, cit); |
| 229 std::swap (sbp, scp); |
252 } | 230 } |
253 else /* b.x_[RIGHT] > c.x_[RIGHT] so finish with c */ | 231 else /* b.x_[RIGHT] > c.x_[RIGHT] so finish with c */ |
254 { | 232 { |
255 if (c.above (b, c.x_[LEFT])) /* -| |---. */ | 233 if (c.above (b, c.x_[LEFT])) /* -| |---. */ |
256 { | 234 { |
257 Building m (b); | 235 Building m (b); |
258 m.x_[RIGHT] = c.x_[LEFT]; | 236 m.x_[RIGHT] = c.x_[LEFT]; |
259 if (m.x_[RIGHT] > m.x_[LEFT]) | 237 if (m.x_[RIGHT] > m.x_[LEFT]) |
260 result->push_back (m); | 238 result->push_back (m); |
261 if (b.above (c, c.x_[RIGHT])) /* -| \---. */ | 239 if (b.above (c, c.x_[RIGHT])) /* -| \---. */ |
262 c.x_[RIGHT] = b.intersection_x (c); | 240 c.x_[RIGHT] = b.intersection_x (c); |
263 } | 241 } |
264 else if (c.above (b, c.x_[RIGHT])) /* ---/|--. */ | 242 else if (c.above (b, c.x_[RIGHT])) /* ---/|--. */ |
265 { | 243 { |
266 Building m (b); | 244 Building m (b); |
267 c.x_[LEFT] = m.x_[RIGHT] = b.intersection_x (c); | 245 c.x_[LEFT] = m.x_[RIGHT] = b.intersection_x (c); |
268 result->push_back (m); | 246 result->push_back (m); |
269 } | 247 } |
270 else /* c is completely hidden by b */ | 248 else /* c is completely hidden by b */ |
271 continue; | 249 continue; |
272 result->push_back (c); | 250 result->push_back (c); |
273 b.x_[LEFT] = c.x_[RIGHT]; | 251 b.x_[LEFT] = c.x_[RIGHT]; |
274 } | 252 } |
275 } | 253 } |
276 if (b.x_[RIGHT] > b.x_[LEFT]) | 254 if (b.x_[RIGHT] > b.x_[LEFT]) |
277 result->push_back (b); | 255 result->push_back (b); |
278 } | 256 } |
279 | 257 |
280 static void | 258 static void |
281 empty_skyline (list<Building> *const ret) | 259 empty_skyline (vector<Building> *const ret) |
282 { | 260 { |
283 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f))
; | 261 assert (ret->empty ()); |
| 262 ret->push_back (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)); |
284 } | 263 } |
285 | 264 |
286 /* | 265 /* |
287 Given Building 'b', build a skyline containing only that building. | 266 Given Building 'b', build a skyline containing only that building. |
288 */ | 267 */ |
289 static void | 268 static void |
290 single_skyline (Building b, list<Building> *const ret) | 269 single_skyline (Building b, vector<Building> *const ret) |
291 { | 270 { |
292 assert (b.x_[RIGHT] >= b.x_[LEFT]); | 271 assert (b.x_[RIGHT] >= b.x_[LEFT]); |
293 | 272 |
294 if (b.x_[LEFT] != -infinity_f) | 273 if (b.x_[LEFT] != -infinity_f) |
295 ret->push_back ( | 274 ret->push_back ( |
296 Building (-infinity_f, -infinity_f, -infinity_f, b.x_[LEFT])); | 275 Building (-infinity_f, -infinity_f, -infinity_f, b.x_[LEFT])); |
297 ret->push_back (b); | 276 ret->push_back (b); |
298 if (b.x_[RIGHT] != infinity_f) | 277 if (b.x_[RIGHT] != infinity_f) |
299 ret->push_back ( | 278 ret->push_back ( |
300 Building (b.x_[RIGHT], -infinity_f, -infinity_f, infinity_f)); | 279 Building (b.x_[RIGHT], -infinity_f, -infinity_f, infinity_f)); |
301 } | 280 } |
302 | 281 |
303 /* remove a non-overlapping set of boxes from BOXES and build a skyline | 282 /* Partition BUILDINGS into a non-overlapping set of boxes and the rest */ |
304 out of them */ | 283 static void |
305 static list<Building> | 284 non_overlapping_skyline (vector<Building> const &buildings, |
306 non_overlapping_skyline (list<Building> *const buildings) | 285 vector<Building> *trimmed, vector<Building> *result) |
307 { | 286 { |
308 list<Building> result; | 287 trimmed->reserve (buildings.size () / 2); |
| 288 result->reserve (buildings.size () / 2); |
309 Real last_end = -infinity_f; | 289 Real last_end = -infinity_f; |
310 Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); | 290 Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); |
311 list<Building>::iterator i = buildings->begin (); | 291 for (auto const &b : buildings) |
312 while (i != buildings->end ()) | 292 { |
313 { | 293 Real x1 = b.x_[LEFT]; |
314 Real x1 = i->x_[LEFT]; | 294 Real y1 = b.height (b.x_[LEFT]); |
315 Real y1 = i->height (i->x_[LEFT]); | 295 Real x2 = b.x_[RIGHT]; |
316 Real x2 = i->x_[RIGHT]; | 296 Real y2 = b.height (b.x_[RIGHT]); |
317 Real y2 = i->height (i->x_[RIGHT]); | |
318 | 297 |
319 // Drop buildings that will obviously have no effect. | 298 // Drop buildings that will obviously have no effect. |
320 if (last_building.height (x1) >= y1 && last_building.x_[RIGHT] >= x2 | 299 if (last_building.height (x1) >= y1 && last_building.x_[RIGHT] >= x2 |
321 && last_building.height (x2) >= y2) | 300 && last_building.height (x2) >= y2) |
322 { | 301 { |
323 list<Building>::iterator j = i++; | |
324 buildings->erase (j); | |
325 continue; | 302 continue; |
326 } | 303 } |
327 | 304 |
328 if (x1 < last_end) | 305 if (x1 < last_end) |
329 { | 306 { |
330 i++; | 307 trimmed->push_back (b); |
331 continue; | 308 continue; |
332 } | 309 } |
333 | 310 |
334 // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH) | 311 // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH) |
335 if (x1 > last_end) | 312 if (x1 > last_end) |
336 result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); | 313 result->push_back (Building (last_end, -infinity_f, -infinity_f, x1)); |
337 | 314 |
338 result.push_back (*i); | 315 result->push_back (b); |
339 last_building = *i; | 316 last_building = b; |
340 last_end = i->x_[RIGHT]; | 317 last_end = b.x_[RIGHT]; |
341 | |
342 list<Building>::iterator j = i++; | |
343 buildings->erase (j); | |
344 } | 318 } |
345 | 319 |
346 if (last_end < infinity_f) | 320 if (last_end < infinity_f) |
347 result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f))
; | 321 result->push_back ( |
348 return result; | 322 Building (last_end, -infinity_f, -infinity_f, infinity_f)); |
349 } | 323 } |
350 | 324 |
351 class LessThanBuilding | 325 class LessThanBuilding |
352 { | 326 { |
353 public: | 327 public: |
354 bool operator () (Building const &b1, Building const &b2) | 328 bool operator () (Building const &b1, Building const &b2) |
355 { | 329 { |
356 return b1.x_[LEFT] < b2.x_[LEFT] | 330 return b1.x_[LEFT] < b2.x_[LEFT] |
357 || (b1.x_[LEFT] == b2.x_[LEFT] | 331 || (b1.x_[LEFT] == b2.x_[LEFT] |
358 && b1.height (b1.x_[LEFT]) > b2.height (b1.x_[LEFT])); | 332 && b1.height (b1.x_[LEFT]) > b2.height (b1.x_[LEFT])); |
359 } | 333 } |
360 }; | 334 }; |
361 | 335 |
362 /** | 336 /** |
363 BUILDINGS is a list of buildings, but they could be overlapping | 337 BUILDINGS is a list of buildings, but they could be overlapping |
364 and in any order. The returned list of buildings is ordered and non-overlapp
ing. | 338 and in any order. The returned list of buildings is ordered and non-overlapp
ing. |
365 */ | 339 */ |
366 list<Building> | 340 vector<Building> |
367 Skyline::internal_build_skyline (list<Building> *buildings) const | 341 Skyline::internal_build_skyline (vector<Building> *buildings) const |
368 { | 342 { |
369 vsize size = buildings->size (); | 343 vsize size = buildings->size (); |
370 | 344 |
371 if (size == 0) | 345 if (size == 0) |
372 { | 346 { |
373 list<Building> result; | 347 vector<Building> result; |
374 empty_skyline (&result); | 348 empty_skyline (&result); |
375 return result; | 349 return result; |
376 } | 350 } |
377 else if (size == 1) | 351 else if (size == 1) |
378 { | 352 { |
379 list<Building> result; | 353 vector<Building> result; |
380 single_skyline (buildings->front (), &result); | 354 single_skyline (buildings->front (), &result); |
381 return result; | 355 return result; |
382 } | 356 } |
383 | 357 |
384 deque<list<Building> > partials; | 358 deque<vector<Building>> partials; |
385 buildings->sort (LessThanBuilding ()); | 359 |
| 360 sort (buildings->begin (), buildings->end (), LessThanBuilding ()); |
386 while (!buildings->empty ()) | 361 while (!buildings->empty ()) |
387 partials.push_back (non_overlapping_skyline (buildings)); | 362 { |
| 363 vector<Building> trimmed, partial; |
| 364 non_overlapping_skyline (*buildings, &trimmed, &partial); |
| 365 partials.push_back (partial); |
| 366 std::swap (*buildings, trimmed); |
| 367 } |
388 | 368 |
389 /* we'd like to say while (partials->size () > 1) but that's O (n). | 369 /* we'd like to say while (partials->size () > 1) but that's O (n). |
390 Instead, we exit in the middle of the loop */ | 370 Instead, we exit in the middle of the loop */ |
391 while (!partials.empty ()) | 371 while (!partials.empty ()) |
392 { | 372 { |
393 list<Building> merged; | 373 vector<Building> merged; |
394 list<Building> one = partials.front (); | 374 vector<Building> one = partials.front (); |
395 partials.pop_front (); | 375 partials.pop_front (); |
396 if (partials.empty ()) | 376 if (partials.empty ()) |
397 return one; | 377 return one; |
398 | 378 |
399 list<Building> two = partials.front (); | 379 vector<Building> two = partials.front (); |
400 partials.pop_front (); | 380 partials.pop_front (); |
401 internal_merge_skyline (&one, &two, &merged); | 381 internal_merge_skyline (&one, &two, &merged); |
402 partials.push_back (merged); | 382 partials.push_back (merged); |
403 } | 383 } |
404 assert (0); | 384 assert (0); |
405 return list<Building> (); | 385 return vector<Building> (); |
406 } | 386 } |
407 | 387 |
408 Skyline::Skyline () | 388 Skyline::Skyline () |
409 { | 389 { |
410 sky_ = UP; | 390 sky_ = UP; |
411 empty_skyline (&buildings_); | 391 empty_skyline (&buildings_); |
412 } | 392 } |
413 | 393 |
414 Skyline::Skyline (Direction sky) | 394 Skyline::Skyline (Direction sky) |
415 { | 395 { |
416 sky_ = sky; | 396 sky_ = sky; |
417 empty_skyline (&buildings_); | 397 empty_skyline (&buildings_); |
418 } | 398 } |
419 | 399 |
420 /* | 400 /* |
421 Build skyline from a set of boxes. | 401 Build skyline from a set of boxes. |
422 | 402 |
423 Boxes should be non-empty on both axes. Otherwise, they will be ignored | 403 Boxes should be non-empty on both axes. Otherwise, they will be ignored |
424 */ | 404 */ |
425 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) | 405 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) |
426 { | 406 { |
427 list<Building> buildings; | 407 vector<Building> buildings; |
| 408 buildings.reserve (boxes.size ()); |
428 sky_ = sky; | 409 sky_ = sky; |
429 | 410 |
430 for (vsize i = 0; i < boxes.size (); i++) | 411 for (vsize i = 0; i < boxes.size (); i++) |
431 if (!boxes[i].is_empty (X_AXIS) | 412 if (!boxes[i].is_empty (X_AXIS) |
432 && !boxes[i].is_empty (Y_AXIS)) | 413 && !boxes[i].is_empty (Y_AXIS)) |
433 buildings.push_front (Building (boxes[i], horizon_axis, sky)); | 414 buildings.push_back (Building (boxes[i], horizon_axis, sky)); |
434 | 415 |
435 buildings_ = internal_build_skyline (&buildings); | 416 buildings_ = internal_build_skyline (&buildings); |
436 normalize (); | |
437 } | 417 } |
438 | 418 |
439 /* | 419 /* |
440 build skyline from a set of line segments. | 420 build skyline from a set of line segments. |
441 | 421 |
442 Segments can be articulated from left to right or right to left. | 422 Segments can be articulated from left to right or right to left. |
443 In the case of the latter, they will be stored internally as left to right. | 423 In the case of the latter, they will be stored internally as left to right. |
444 */ | 424 */ |
445 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis
, Direction sky) | 425 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis
, Direction sky) |
446 { | 426 { |
447 list<Building> buildings; | 427 vector<Building> buildings; |
| 428 buildings.reserve (segments.size ()); |
448 sky_ = sky; | 429 sky_ = sky; |
449 | 430 |
450 for (vsize i = 0; i < segments.size (); i++) | 431 for (vsize i = 0; i < segments.size (); i++) |
451 { | 432 { |
452 Drul_array<Offset> const &seg = segments[i]; | 433 Drul_array<Offset> const &seg = segments[i]; |
453 Offset left = seg[LEFT]; | 434 Offset left = seg[LEFT]; |
454 Offset right = seg[RIGHT]; | 435 Offset right = seg[RIGHT]; |
455 if (left[horizon_axis] > right[horizon_axis]) | 436 if (left[horizon_axis] > right[horizon_axis]) |
456 std::swap (left, right); | 437 std::swap (left, right); |
457 | 438 |
458 Real x1 = left[horizon_axis]; | 439 Real x1 = left[horizon_axis]; |
459 Real x2 = right[horizon_axis]; | 440 Real x2 = right[horizon_axis]; |
460 Real y1 = left[other_axis (horizon_axis)] * sky; | 441 Real y1 = left[other_axis (horizon_axis)] * sky; |
461 Real y2 = right[other_axis (horizon_axis)] * sky; | 442 Real y2 = right[other_axis (horizon_axis)] * sky; |
462 | 443 |
463 if (x1 < x2) | 444 if (x1 < x2) |
464 buildings.push_back (Building (x1, y1, y2, x2)); | 445 buildings.push_back (Building (x1, y1, y2, x2)); |
465 } | 446 } |
466 | 447 |
467 buildings_ = internal_build_skyline (&buildings); | 448 buildings_ = internal_build_skyline (&buildings); |
468 normalize (); | |
469 } | 449 } |
470 | 450 |
471 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) | 451 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) |
472 { | 452 { |
473 sky_ = sky; | 453 sky_ = sky; |
474 | 454 |
475 deque<Skyline> partials; | 455 deque<Skyline> partials; |
476 for (vsize i = 0; i < skypairs.size (); i++) | 456 for (vsize i = 0; i < skypairs.size (); i++) |
477 partials.push_back (Skyline ((skypairs[i])[sky])); | 457 partials.push_back (Skyline ((skypairs[i])[sky])); |
478 | 458 |
(...skipping 14 matching lines...) Expand all Loading... |
493 buildings_.clear (); | 473 buildings_.clear (); |
494 } | 474 } |
495 | 475 |
496 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) | 476 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) |
497 { | 477 { |
498 sky_ = sky; | 478 sky_ = sky; |
499 if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS)) | 479 if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS)) |
500 { | 480 { |
501 Building front (b, horizon_axis, sky); | 481 Building front (b, horizon_axis, sky); |
502 single_skyline (front, &buildings_); | 482 single_skyline (front, &buildings_); |
503 normalize (); | |
504 } | 483 } |
505 } | 484 } |
506 | 485 |
507 void | 486 void |
508 Skyline::merge (Skyline const &other) | 487 Skyline::merge (Skyline const &other) |
509 { | 488 { |
510 assert (sky_ == other.sky_); | 489 assert (sky_ == other.sky_); |
511 | 490 |
512 if (other.is_empty ()) | 491 if (other.is_empty ()) |
513 return; | 492 return; |
514 | 493 |
515 if (is_empty ()) | 494 if (is_empty ()) |
516 { | 495 { |
517 buildings_ = other.buildings_; | 496 buildings_ = other.buildings_; |
518 return; | 497 return; |
519 } | 498 } |
520 | 499 |
521 list<Building> other_bld (other.buildings_); | 500 vector<Building> other_bld (other.buildings_); |
522 list<Building> my_bld; | 501 vector<Building> my_bld (buildings_); |
523 my_bld.splice (my_bld.begin (), buildings_); | 502 buildings_.clear (); |
524 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | 503 internal_merge_skyline (&other_bld, &my_bld, &buildings_); |
525 normalize (); | |
526 } | 504 } |
527 | 505 |
528 void | 506 void |
529 Skyline::insert (Box const &b, Axis a) | 507 Skyline::insert (Box const &b, Axis a) |
530 { | 508 { |
531 list<Building> other_bld; | |
532 list<Building> my_bld; | |
533 | |
534 if (std::isnan (b[other_axis (a)][LEFT]) | 509 if (std::isnan (b[other_axis (a)][LEFT]) |
535 || std::isnan (b[other_axis (a)][RIGHT])) | 510 || std::isnan (b[other_axis (a)][RIGHT])) |
536 { | 511 { |
537 programming_error ("insane box for skyline"); | 512 programming_error ("insane box for skyline"); |
538 return; | 513 return; |
539 } | 514 } |
540 | 515 |
541 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ | 516 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ |
542 if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS)) | 517 if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS)) |
543 return; | 518 return; |
544 | 519 |
545 my_bld.splice (my_bld.begin (), buildings_); | 520 vector<Building> my_bld = buildings_; |
| 521 buildings_.clear (); |
| 522 |
| 523 vector<Building> other_bld; |
546 single_skyline (Building (b, a, sky_), &other_bld); | 524 single_skyline (Building (b, a, sky_), &other_bld); |
547 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | 525 internal_merge_skyline (&other_bld, &my_bld, &buildings_); |
548 normalize (); | |
549 } | 526 } |
550 | 527 |
551 void | 528 void |
552 Skyline::raise (Real r) | 529 Skyline::raise (Real r) |
553 { | 530 { |
554 list<Building>::iterator end = buildings_.end (); | 531 for (auto i = buildings_.begin (); i != buildings_.end (); i++) |
555 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | |
556 i->y_intercept_ += sky_ * r; | 532 i->y_intercept_ += sky_ * r; |
557 } | 533 } |
558 | 534 |
559 void | 535 void |
560 Skyline::shift (Real s) | 536 Skyline::shift (Real s) |
561 { | 537 { |
562 list<Building>::iterator end = buildings_.end (); | 538 for (auto i = buildings_.begin (); i != buildings_.end (); i++) |
563 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | |
564 { | 539 { |
565 i->x_[LEFT] += s; | 540 i->x_[LEFT] += s; |
566 i->x_[RIGHT] += s; | 541 i->x_[RIGHT] += s; |
567 i->y_intercept_ -= s * i->slope_; | 542 i->y_intercept_ -= s * i->slope_; |
568 } | 543 } |
569 } | 544 } |
570 | 545 |
571 Real | 546 Real |
572 Skyline::distance (Skyline const &other, Real horizon_padding) const | 547 Skyline::distance (Skyline const &other, Real horizon_padding) const |
573 { | 548 { |
(...skipping 23 matching lines...) Expand all Loading... |
597 | 572 |
598 Skyline | 573 Skyline |
599 Skyline::padded (Real horizon_padding) const | 574 Skyline::padded (Real horizon_padding) const |
600 { | 575 { |
601 if (horizon_padding < 0.0) | 576 if (horizon_padding < 0.0) |
602 warning ("Cannot have negative horizon padding. Junking."); | 577 warning ("Cannot have negative horizon padding. Junking."); |
603 | 578 |
604 if (horizon_padding <= 0.0) | 579 if (horizon_padding <= 0.0) |
605 return *this; | 580 return *this; |
606 | 581 |
607 list<Building> pad_buildings; | 582 vector<Building> pad_buildings; |
608 for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.e
nd (); ++i) | 583 pad_buildings.reserve (buildings_.size ()); |
609 { | 584 for (auto const &b : buildings_) |
610 if (i->x_[LEFT] > -infinity_f) | 585 { |
| 586 if (b.x_[LEFT] > -infinity_f) |
611 { | 587 { |
612 Real height = i->height (i->x_[LEFT]); | 588 Real height = b.height (b.x_[LEFT]); |
613 if (height > -infinity_f) | 589 if (height > -infinity_f) |
614 { | 590 { |
615 // Add the sloped building that pads the left side of the current
building. | 591 // Add the sloped building that pads the left side of the current
building. |
616 Real start = i->x_[LEFT] - 2 * horizon_padding; | 592 Real start = b.x_[LEFT] - 2 * horizon_padding; |
617 Real end = i->x_[LEFT] - horizon_padding; | 593 Real end = b.x_[LEFT] - horizon_padding; |
618 pad_buildings.push_back (Building (start, height - horizon_padding
, height, end)); | 594 pad_buildings.push_back (Building (start, height - horizon_padding
, height, end)); |
619 | 595 |
620 // Add the flat building that pads the left side of the current bu
ilding. | 596 // Add the flat building that pads the left side of the current bu
ilding. |
621 start = i->x_[LEFT] - horizon_padding; | 597 start = b.x_[LEFT] - horizon_padding; |
622 end = i->x_[LEFT]; | 598 end = b.x_[LEFT]; |
623 pad_buildings.push_back (Building (start, height, height, end)); | 599 pad_buildings.push_back (Building (start, height, height, end)); |
624 } | 600 } |
625 } | 601 } |
626 | 602 |
627 if (i->x_[RIGHT] < infinity_f) | 603 if (b.x_[RIGHT] < infinity_f) |
628 { | 604 { |
629 Real height = i->height (i->x_[RIGHT]); | 605 Real height = b.height (b.x_[RIGHT]); |
630 if (height > -infinity_f) | 606 if (height > -infinity_f) |
631 { | 607 { |
632 // Add the flat building that pads the right side of the current b
uilding. | 608 // Add the flat building that pads the right side of the current b
uilding. |
633 Real start = i->x_[RIGHT]; | 609 Real start = b.x_[RIGHT]; |
634 Real end = start + horizon_padding; | 610 Real end = start + horizon_padding; |
635 pad_buildings.push_back (Building (start, height, height, end)); | 611 pad_buildings.push_back (Building (start, height, height, end)); |
636 | 612 |
637 // Add the sloped building that pads the right side of the current
building. | 613 // Add the sloped building that pads the right side of the current
building. |
638 start = end; | 614 start = end; |
639 end += horizon_padding; | 615 end += horizon_padding; |
640 pad_buildings.push_back (Building (start, height, height - horizon
_padding, end)); | 616 pad_buildings.push_back (Building (start, height, height - horizon
_padding, end)); |
641 } | 617 } |
642 } | 618 } |
643 } | 619 } |
644 | 620 |
645 // The buildings may be overlapping, so resolve that. | 621 // The buildings may be overlapping, so resolve that. |
646 list<Building> pad_skyline = internal_build_skyline (&pad_buildings); | 622 vector<Building> pad_skyline = internal_build_skyline (&pad_buildings); |
647 | 623 |
648 // Merge the padding with the original, to make a new skyline. | 624 // Merge the padding with the original, to make a new skyline. |
649 Skyline padded (sky_); | 625 Skyline padded (sky_); |
650 list<Building> my_buildings = buildings_; | 626 vector<Building> my_buildings = buildings_; |
651 padded.buildings_.clear (); | 627 padded.buildings_.clear (); |
652 internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); | 628 internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); |
653 padded.normalize (); | |
654 | 629 |
655 return padded; | 630 return padded; |
656 } | 631 } |
657 | 632 |
658 Real | 633 Real |
659 Skyline::internal_distance (Skyline const &other, Real *touch_point) const | 634 Skyline::internal_distance (Skyline const &other, Real *touch_point) const |
660 { | 635 { |
661 assert (sky_ == -other.sky_); | 636 assert (sky_ == -other.sky_); |
662 | 637 |
663 list<Building>::const_iterator i = buildings_.begin (); | 638 auto i = buildings_.begin (); |
664 list<Building>::const_iterator j = other.buildings_.begin (); | 639 auto j = other.buildings_.begin (); |
665 | 640 |
666 Real dist = -infinity_f; | 641 Real dist = -infinity_f; |
667 Real start = -infinity_f; | 642 Real start = -infinity_f; |
668 Real touch = -infinity_f; | 643 Real touch = -infinity_f; |
669 while (i != buildings_.end () && j != other.buildings_.end ()) | 644 while (i != buildings_.end () && j != other.buildings_.end ()) |
670 { | 645 { |
671 Real end = std::min (i->x_[RIGHT], j->x_[RIGHT]); | 646 Real end = std::min (i->x_[RIGHT], j->x_[RIGHT]); |
672 Real start_dist = i->height (start) + j->height (start); | 647 Real start_dist = i->height (start) + j->height (start); |
673 Real end_dist = i->height (end) + j->height (end); | 648 Real end_dist = i->height (end) + j->height (end); |
674 dist = std::max (dist, std::max (start_dist, end_dist)); | 649 dist = std::max (dist, std::max (start_dist, end_dist)); |
(...skipping 12 matching lines...) Expand all Loading... |
687 | 662 |
688 *touch_point = touch; | 663 *touch_point = touch; |
689 return dist; | 664 return dist; |
690 } | 665 } |
691 | 666 |
692 Real | 667 Real |
693 Skyline::height (Real airplane) const | 668 Skyline::height (Real airplane) const |
694 { | 669 { |
695 assert (!std::isinf (airplane)); | 670 assert (!std::isinf (airplane)); |
696 | 671 |
697 list<Building>::const_iterator i; | 672 // TODO - use binary search |
698 for (i = buildings_.begin (); i != buildings_.end (); i++) | 673 for (auto const &b : buildings_) |
699 { | 674 { |
700 if (i->x_[RIGHT] >= airplane) | 675 if (b.x_[RIGHT] >= airplane) |
701 return sky_ * i->height (airplane); | 676 return sky_ * b.height (airplane); |
702 } | 677 } |
703 | 678 |
704 assert (0); | 679 assert (0); |
705 return 0; | 680 return 0; |
706 } | 681 } |
707 | 682 |
708 Real | 683 Real |
709 Skyline::max_height () const | 684 Skyline::max_height () const |
710 { | 685 { |
711 Real ret = -infinity_f; | 686 Real ret = -infinity_f; |
712 | 687 |
713 list<Building>::const_iterator i; | 688 for (auto const &b : buildings_) |
714 for (i = buildings_.begin (); i != buildings_.end (); ++i) | 689 { |
715 { | 690 // TODO: unnecessary calculations. |
716 ret = std::max (ret, i->height (i->x_[LEFT])); | 691 ret = std::max (ret, b.height (b.x_[LEFT])); |
717 ret = std::max (ret, i->height (i->x_[RIGHT])); | 692 ret = std::max (ret, b.height (b.x_[RIGHT])); |
718 } | 693 } |
719 | 694 |
720 return sky_ * ret; | 695 return sky_ * ret; |
721 } | 696 } |
722 | 697 |
723 Direction | 698 Direction |
724 Skyline::direction () const | 699 Skyline::direction () const |
725 { | 700 { |
726 return sky_; | 701 return sky_; |
727 } | 702 } |
728 | 703 |
| 704 // X of first building in skyline |
729 Real | 705 Real |
730 Skyline::left () const | 706 Skyline::left () const |
731 { | 707 { |
732 for (list<Building>::const_iterator i (buildings_.begin ()); | 708 for (auto const &b : buildings_) |
733 i != buildings_.end (); i++) | 709 if (b.y_intercept_ > -infinity_f) |
734 if (i->y_intercept_ > -infinity_f) | 710 return b.x_[LEFT]; |
735 return i->x_[LEFT]; | |
736 | 711 |
737 return infinity_f; | 712 return infinity_f; |
738 } | 713 } |
739 | 714 |
| 715 // X of end of last building in skyline |
740 Real | 716 Real |
741 Skyline::right () const | 717 Skyline::right () const |
742 { | 718 { |
743 for (list<Building>::const_reverse_iterator i (buildings_.rbegin ()); | 719 for (auto i = buildings_.rbegin (); i != buildings_.rend (); ++i) |
744 i != buildings_.rend (); ++i) | |
745 if (i->y_intercept_ > -infinity_f) | 720 if (i->y_intercept_ > -infinity_f) |
746 return i->x_[RIGHT]; | 721 return i->x_[RIGHT]; |
747 | 722 |
748 return -infinity_f; | 723 return -infinity_f; |
749 } | 724 } |
750 | 725 |
751 Real | 726 Real |
752 Skyline::max_height_position () const | 727 Skyline::max_height_position () const |
753 { | 728 { |
754 Skyline s (-sky_); | 729 Skyline s (-sky_); |
| 730 // TODO: should be able to calc without doing a merge? |
755 s.set_minimum_height (0); | 731 s.set_minimum_height (0); |
756 return touching_point (s); | 732 return touching_point (s); |
757 } | 733 } |
758 | 734 |
759 void | 735 void |
760 Skyline::set_minimum_height (Real h) | 736 Skyline::set_minimum_height (Real h) |
761 { | 737 { |
762 Skyline s (sky_); | 738 Skyline s (sky_); |
763 s.buildings_.front ().y_intercept_ = h * sky_; | 739 s.buildings_.front ().y_intercept_ = h * sky_; |
764 merge (s); | 740 merge (s); |
765 } | 741 } |
766 | 742 |
767 vector<Offset> | 743 vector<Offset> |
768 Skyline::to_points (Axis horizon_axis) const | 744 Skyline::to_points (Axis horizon_axis) const |
769 { | 745 { |
770 vector<Offset> out; | 746 vector<Offset> out; |
| 747 out.reserve (2 * buildings_.size ()); |
771 | 748 |
772 Real start = -infinity_f; | 749 Real start = -infinity_f; |
773 for (list<Building>::const_iterator i (buildings_.begin ()); | 750 for (auto const &b : buildings_) |
774 i != buildings_.end (); i++) | 751 { |
775 { | 752 out.push_back (Offset (start, sky_ * b.height (start))); |
776 out.push_back (Offset (start, sky_ * i->height (start))); | 753 out.push_back (Offset (b.x_[RIGHT], sky_ * b.height (b.x_[RIGHT]))); |
777 out.push_back (Offset (i->x_[RIGHT], sky_ * i->height (i->x_[RIGHT]))); | 754 start = b.x_[RIGHT]; |
778 start = i->x_[RIGHT]; | |
779 } | 755 } |
780 | 756 |
781 if (horizon_axis == Y_AXIS) | 757 if (horizon_axis == Y_AXIS) |
782 for (vsize i = 0; i < out.size (); i++) | 758 for (vsize i = 0; i < out.size (); i++) |
783 out[i] = out[i].swapped (); | 759 out[i] = out[i].swapped (); |
784 | 760 |
785 return out; | 761 return out; |
786 } | 762 } |
787 | 763 |
788 bool | 764 bool |
(...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
861 { | 837 { |
862 Real x = robust_scm2double (x_scm, 0.0); | 838 Real x = robust_scm2double (x_scm, 0.0); |
863 return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x)); | 839 return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x)); |
864 } | 840 } |
865 | 841 |
866 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", | 842 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", |
867 1, 0, 0, (SCM sky), | 843 1, 0, 0, (SCM sky), |
868 "Return whether @var{sky} is empty.") | 844 "Return whether @var{sky} is empty.") |
869 { | 845 { |
870 Skyline *s = unsmob<Skyline> (sky); | 846 Skyline *s = unsmob<Skyline> (sky); |
| 847 |
871 LY_ASSERT_SMOB (Skyline, sky, 1); | 848 LY_ASSERT_SMOB (Skyline, sky, 1); |
872 return scm_from_bool (s->is_empty ()); | 849 return scm_from_bool (s->is_empty ()); |
873 } | 850 } |
LEFT | RIGHT |