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--2012 Joe Neeman <joeneeman@gmail.com> | 4 Copyright (C) 2006--2012 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 <deque> | 22 #include <deque> |
22 #include <cstdio> | 23 #include <cstdio> |
23 | 24 |
24 #include "ly-smobs.icc" | 25 #include "ly-smobs.icc" |
25 | 26 |
26 /* A skyline is a sequence of non-overlapping buildings: something like | 27 /* A skyline is a sequence of non-overlapping buildings: something like |
27 this: | 28 this: |
28 _______ | 29 _______ |
29 | \ ________ | 30 | \ ________ |
30 | \ ________/ \ | 31 | \ ________/ \ |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
80 for (vsize i = 0; i < ps.size (); i++) | 81 for (vsize i = 0; i < ps.size (); i++) |
81 printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS], | 82 printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS], |
82 (i % 2) == 1 ? "\n" : " "); | 83 (i % 2) == 1 ? "\n" : " "); |
83 } | 84 } |
84 | 85 |
85 Building::Building (Real start, Real start_height, Real end_height, Real end) | 86 Building::Building (Real start, Real start_height, Real end_height, Real end) |
86 { | 87 { |
87 if (isinf (start) || isinf (end)) | 88 if (isinf (start) || isinf (end)) |
88 assert (start_height == end_height); | 89 assert (start_height == end_height); |
89 | 90 |
| 91 start_ = start; |
90 end_ = end; | 92 end_ = end; |
91 precompute (start, start_height, end_height, end); | 93 precompute (start, start_height, end_height, end); |
92 } | 94 } |
93 | 95 |
94 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direc
tion sky) | 96 Building::Building (Box const &b, Axis horizon_axis, Direction sky) |
95 { | 97 { |
96 Real start = b[horizon_axis][LEFT] - horizon_padding; | 98 Real start = b[horizon_axis][LEFT]; |
97 Real end = b[horizon_axis][RIGHT] + horizon_padding; | 99 Real end = b[horizon_axis][RIGHT]; |
98 Real height = sky * b[other_axis (horizon_axis)][sky]; | 100 Real height = sky * b[other_axis (horizon_axis)][sky]; |
99 | 101 |
| 102 start_ = start; |
100 end_ = end; | 103 end_ = end; |
101 precompute (start, height, height, end); | 104 precompute (start, height, height, end); |
102 } | 105 } |
103 | 106 |
104 void | 107 void |
105 Building::precompute (Real start, Real start_height, Real end_height, Real end) | 108 Building::precompute (Real start, Real start_height, Real end_height, Real end) |
106 { | 109 { |
107 slope_ = (end_height - start_height) / (end - start); | 110 slope_ = 0.0; /* if they were both infinite, we would get nan, not 0, from the
prev line */ |
108 if (start_height == end_height) /* if they were both infinite, we would get na
n, not 0, from the prev line */ | 111 if (start_height != end_height) |
109 slope_ = 0; | 112 slope_ = (end_height - start_height) / (end - start); |
110 | 113 |
111 assert (!isinf (slope_) && !isnan (slope_)); | 114 assert (!isinf (slope_) && !isnan (slope_)); |
112 | 115 |
113 if (isinf (start)) | 116 if (isinf (start)) |
114 { | 117 { |
115 assert (start_height == end_height); | 118 assert (start_height == end_height); |
116 y_intercept_ = start_height; | 119 y_intercept_ = start_height; |
117 } | 120 } |
118 else | 121 else |
119 y_intercept_ = start_height - slope_ * start; | 122 y_intercept_ = start_height - slope_ * start; |
120 } | 123 } |
121 | 124 |
122 Real | 125 inline Real |
123 Building::height (Real x) const | 126 Building::height (Real x) const |
124 { | 127 { |
125 return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; | 128 return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; |
126 } | 129 } |
127 | 130 |
128 void | 131 void |
129 Building::print () const | 132 Building::print () const |
130 { | 133 { |
131 printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_); | 134 printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_); |
132 } | 135 } |
133 | 136 |
134 Real | 137 inline Real |
135 Building::intersection_x (Building const &other) const | 138 Building::intersection_x (Building const &other) const |
136 { | 139 { |
137 Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); | 140 Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); |
138 return isnan (ret) ? -infinity_f : ret; | 141 return isnan (ret) ? -infinity_f : ret; |
139 } | 142 } |
140 | 143 |
141 void | 144 void |
142 Building::leading_part (Real chop) | 145 Building::leading_part (Real chop) |
143 { | 146 { |
144 assert (chop <= end_); | 147 assert (chop <= end_); |
145 end_ = chop; | 148 end_ = chop; |
146 } | 149 } |
147 | 150 |
148 Building | 151 // Returns a shift s such that (x + s, y) intersects the roof of |
149 Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const | 152 // this building. If no such shift exists, returns infinity_f. |
150 { | 153 Real |
151 Real x = (d == LEFT) ? start : end_; | 154 Building::shift_to_intersect (Real x, Real y) const |
152 Real left = x; | 155 { |
153 Real right = x + d * horizon_padding; | 156 // Solve for s: y = (x + s)*m + b |
154 Real left_height = height (x); | 157 Real ret = (y - y_intercept_ - slope_ * x) / slope_; |
155 Real right_height = left_height - horizon_padding; | 158 |
156 if (d == LEFT) | 159 if (ret >= start_ && ret <= end_ && !isinf (ret)) |
157 { | 160 return ret; |
158 swap (left, right); | 161 return infinity_f; |
159 swap (left_height, right_height); | 162 } |
160 } | 163 |
161 return Building (left, left_height, right_height, right); | 164 // Returns the interval of horizontal shifts for which this |
| 165 // building (pointing up) overlaps the other building (pointing down). |
| 166 Interval |
| 167 Building::overlapping_shift_interval (Building const &other) const |
| 168 { |
| 169 Interval iv; |
| 170 |
| 171 // If one building is empty, there will never be an overlap. |
| 172 if (y_intercept_ == -infinity_f || other.y_intercept_ == -infinity_f) |
| 173 return iv; |
| 174 |
| 175 // There are two kinds of interesting positions: |
| 176 // - when the horizontal extents of the buildings just touch |
| 177 // - when an endpoint of one building intersects the roof of the other. |
| 178 // The interval we are looking for is the smallest one that |
| 179 // contains all of the interesting points. |
| 180 |
| 181 |
| 182 Real my_y1 = height (start_); |
| 183 Real my_y2 = height (end_); |
| 184 Real his_y1 = -other.height (other.start_); // "-" because OTHER points down |
| 185 Real his_y2 = -other.height (other.end_); |
| 186 |
| 187 // If both buildings are infinite in the same direction, |
| 188 // the return value is either empty or full. |
| 189 if ((isinf (start_) && isinf (other.start_)) |
| 190 || (isinf (end_) && isinf (other.end_))) |
| 191 return (y_intercept_ > other.y_intercept_) |
| 192 ? Interval (-infinity_f, infinity_f) : Interval (); |
| 193 |
| 194 // ...when the horizontal extents of the buildings just touch... |
| 195 if (my_y1 >= his_y2) |
| 196 iv.add_point (other.end_ - start_); |
| 197 if (my_y2 >= his_y1) |
| 198 iv.add_point (other.start_ - end_); |
| 199 |
| 200 // ...when an endpoint of one building intersects the roof of the other. |
| 201 Real p1 = shift_to_intersect (other.start_, his_y1); |
| 202 Real p2 = shift_to_intersect (other.end_, his_y2); |
| 203 // "-my_y1" because OTHER points down: |
| 204 Real p3 = other.shift_to_intersect (start_, -my_y1); |
| 205 Real p4 = other.shift_to_intersect (end_, -my_y2); |
| 206 if (!isinf (p1)) |
| 207 iv.add_point (p1); |
| 208 if (!isinf (p2)) |
| 209 iv.add_point (p2); |
| 210 if (!isinf (p3)) |
| 211 iv.add_point (p3); |
| 212 if (!isinf (p4)) |
| 213 iv.add_point (p4); |
| 214 |
| 215 return iv; |
162 } | 216 } |
163 | 217 |
164 static Real | 218 static Real |
165 first_intersection (Building const &b, list<Building> *const s, Real start_x) | 219 first_intersection (Building const &b, list<Building> *const s, Real start_x) |
166 { | 220 { |
167 while (!s->empty () && start_x < b.end_) | 221 while (!s->empty () && start_x < b.end_) |
168 { | 222 { |
169 Building c = s->front (); | 223 Building c = s->front (); |
| 224 |
| 225 // conceals and intersection_x involve multiplication and |
| 226 // division. Avoid that, if we can. |
| 227 if (c.y_intercept_ == -infinity_f) |
| 228 { |
| 229 if (c.end_ > b.end_) |
| 230 return b.end_; |
| 231 start_x = c.end_; |
| 232 s->pop_front (); |
| 233 continue; |
| 234 } |
| 235 |
170 if (c.conceals (b, start_x)) | 236 if (c.conceals (b, start_x)) |
171 return start_x; | 237 return start_x; |
172 | 238 |
173 Real i = b.intersection_x (c); | 239 Real i = b.intersection_x (c); |
174 if (i > start_x && i <= b.end_ && i <= c.end_) | 240 if (i > start_x && i <= b.end_ && i <= c.end_) |
175 return i; | 241 return i; |
176 | 242 |
177 start_x = c.end_; | 243 start_x = c.end_; |
178 if (b.end_ > c.end_) | 244 if (b.end_ > c.end_) |
179 s->pop_front (); | 245 s->pop_front (); |
180 } | 246 } |
181 return b.end_; | 247 return b.end_; |
182 } | 248 } |
183 | 249 |
184 bool | 250 bool |
185 Building::conceals (Building const &other, Real x) const | 251 Building::conceals (Building const &other, Real x) const |
186 { | 252 { |
187 if (slope_ == other.slope_) | 253 if (slope_ == other.slope_) |
188 return y_intercept_ > other.y_intercept_; | 254 return y_intercept_ > other.y_intercept_; |
189 | 255 |
190 /* their slopes were not equal, so there is an intersection point */ | 256 /* their slopes were not equal, so there is an intersection point */ |
191 Real i = intersection_x (other); | 257 Real i = intersection_x (other); |
192 return (i <= x && slope_ > other.slope_) | 258 return (i <= x && slope_ > other.slope_) |
193 || (i > x && slope_ < other.slope_); | 259 || (i > x && slope_ < other.slope_); |
194 } | 260 } |
195 | 261 |
| 262 // Remove redundant empty buildings from the skyline. |
| 263 // If there are two adjacent empty buildings, they can be |
| 264 // turned into one. |
| 265 void |
| 266 Skyline::normalize () |
| 267 { |
| 268 bool last_empty = false; |
| 269 list<Building>::iterator i; |
| 270 for (i = buildings_.begin (); i != buildings_.end (); i++) |
| 271 { |
| 272 if (last_empty && i->y_intercept_ == -infinity_f) |
| 273 { |
| 274 list<Building>::iterator last = i; |
| 275 last--; |
| 276 last->end_ = i->end_; |
| 277 buildings_.erase (i); |
| 278 i = last; |
| 279 } |
| 280 last_empty = (i->y_intercept_ == -infinity_f); |
| 281 } |
| 282 |
| 283 assert (buildings_.front ().start_ == -infinity_f); |
| 284 assert (buildings_.back ().end_ == infinity_f); |
| 285 } |
| 286 |
| 287 void |
| 288 Skyline::deholify () |
| 289 { |
| 290 // Since a skyline should always be normalized, we can |
| 291 // assume that there are never two adjacent empty buildings. |
| 292 // That is, if center is empty then left and right are not. |
| 293 list<Building>::iterator left = buildings_.begin (); |
| 294 list<Building>::iterator center = buildings_.begin (); |
| 295 list<Building>::iterator right; |
| 296 |
| 297 for (right = buildings_.begin (); right != buildings_.end (); right++) |
| 298 { |
| 299 if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) |
| 300 { |
| 301 Real p1 = left->height (left->end_); |
| 302 Real p2 = right->height (right->start_); |
| 303 *center = Building (center->start_, p1, p2, center->end_); |
| 304 |
| 305 left = center; |
| 306 center = right; |
| 307 } |
| 308 } |
| 309 } |
| 310 |
196 void | 311 void |
197 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, | 312 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, |
198 list<Building> *const result) | 313 list<Building> *const result) const |
199 { | 314 { |
200 if (s1->empty () || s2->empty ()) | 315 if (s1->empty () || s2->empty ()) |
201 { | 316 { |
202 programming_error ("tried to merge an empty skyline"); | 317 programming_error ("tried to merge an empty skyline"); |
203 return; | 318 return; |
204 } | 319 } |
205 | 320 |
206 Real x = -infinity_f; | 321 Real x = -infinity_f; |
| 322 Real last_end = -infinity_f; |
207 while (!s1->empty ()) | 323 while (!s1->empty ()) |
208 { | 324 { |
209 if (s2->front ().conceals (s1->front (), x)) | 325 if (s2->front ().conceals (s1->front (), x)) |
210 swap (s1, s2); | 326 swap (s1, s2); |
211 | 327 |
212 Building b = s1->front (); | 328 Building b = s1->front (); |
| 329 Building c = s2->front (); |
| 330 |
| 331 // Optimization: if the other skyline is empty at this point, |
| 332 // we can avoid testing some intersections. Just grab as many |
| 333 // buildings from s1 as we can, and shove them onto the output. |
| 334 if (c.y_intercept_ == -infinity_f |
| 335 && c.end_ >= b.end_) |
| 336 { |
| 337 list<Building>::iterator i = s1->begin (); |
| 338 i++; |
| 339 while (i != s1->end () && i->end_ <= c.end_) |
| 340 i++; |
| 341 |
| 342 s1->front ().start_ = x; |
| 343 result->splice (result->end (), *s1, s1->begin (), i); |
| 344 x = result->back ().end_; |
| 345 last_end = x; |
| 346 continue; |
| 347 } |
| 348 |
213 Real end = first_intersection (b, s2, x); | 349 Real end = first_intersection (b, s2, x); |
214 | |
215 if (s2->empty ()) | 350 if (s2->empty ()) |
216 { | 351 { |
217 result->push_front (b); | 352 b.start_ = last_end; |
| 353 result->push_back (b); |
218 break; | 354 break; |
219 } | 355 } |
220 | 356 |
221 /* only include buildings wider than epsilon */ | 357 /* only include buildings wider than epsilon */ |
222 if (end > x + EPS) | 358 if (end > x + EPS) |
223 { | 359 { |
224 b.leading_part (end); | 360 b.leading_part (end); |
225 result->push_front (b); | 361 b.start_ = last_end; |
| 362 last_end = b.end_; |
| 363 result->push_back (b); |
226 } | 364 } |
227 | 365 |
228 if (end >= s1->front ().end_) | 366 if (end >= s1->front ().end_) |
229 s1->pop_front (); | 367 s1->pop_front (); |
230 | 368 |
231 x = end; | 369 x = end; |
232 } | 370 } |
233 result->reverse (); | |
234 } | 371 } |
235 | 372 |
236 static void | 373 static void |
237 empty_skyline (list<Building> *const ret) | 374 empty_skyline (list<Building> *const ret) |
238 { | 375 { |
239 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f))
; | 376 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f))
; |
240 } | 377 } |
241 | 378 |
242 /* | 379 /* |
243 Given Building 'b' with starting wall location 'start', extend each side | 380 Given Building 'b', build a skyline containing only that building. |
244 with a sloped roofline of width 'horizon_padding'; put the skyline in 'ret' | |
245 */ | 381 */ |
246 static void | 382 static void |
247 single_skyline (Building b, Real start, Real horizon_padding, list<Building> *co
nst ret) | 383 single_skyline (Building b, list<Building> *const ret) |
248 { | 384 { |
249 bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.en
d_); | 385 if (b.end_ > b.start_ + EPS) |
250 if (!isinf (b.end_)) | 386 { |
251 ret->push_front (Building (b.end_ + horizon_padding, -infinity_f, | 387 ret->push_back (Building (-infinity_f, -infinity_f, |
252 -infinity_f, infinity_f)); | 388 -infinity_f, b.start_)); |
253 if (sloped_neighbours) | 389 ret->push_back (b); |
254 ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT)); | 390 ret->push_back (Building (b.end_, -infinity_f, |
255 | 391 -infinity_f, infinity_f)); |
256 if (b.end_ > start + EPS) | 392 } |
257 ret->push_front (b); | 393 else |
258 | 394 { |
259 if (sloped_neighbours) | 395 empty_skyline (ret); |
260 ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT)); | 396 } |
261 | |
262 if (!isinf (start)) | |
263 ret->push_front (Building (-infinity_f, -infinity_f, | |
264 -infinity_f, start - horizon_padding)); | |
265 } | 397 } |
266 | 398 |
267 /* remove a non-overlapping set of boxes from BOXES and build a skyline | 399 /* remove a non-overlapping set of boxes from BOXES and build a skyline |
268 out of them */ | 400 out of them */ |
269 static list<Building> | 401 static list<Building> |
270 non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis hori
zon_axis, Direction sky) | 402 non_overlapping_skyline (list<Building> *const buildings) |
271 { | 403 { |
272 list<Building> result; | 404 list<Building> result; |
273 Real last_end = -infinity_f; | 405 Real last_end = -infinity_f; |
274 list<Box>::iterator i = boxes->begin (); | 406 Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); |
275 while (i != boxes->end ()) | 407 list<Building>::iterator i = buildings->begin (); |
276 { | 408 while (i != buildings->end ()) |
277 Interval iv = (*i)[horizon_axis]; | 409 { |
278 | 410 Real x1 = i->start_; |
279 if (iv[LEFT] - horizon_padding < last_end) | 411 Real y1 = i->height (i->start_); |
| 412 Real x2 = i->end_; |
| 413 Real y2 = i->height (i->end_); |
| 414 |
| 415 // Drop buildings that will obviously have no effect. |
| 416 if (last_building.height (x1) >= y1 |
| 417 && last_building.end_ >= x2 |
| 418 && last_building.height (x2) >= y2) |
| 419 { |
| 420 list<Building>::iterator j = i++; |
| 421 buildings->erase (j); |
| 422 continue; |
| 423 } |
| 424 |
| 425 if (x1 < last_end) |
280 { | 426 { |
281 i++; | 427 i++; |
282 continue; | 428 continue; |
283 } | 429 } |
284 | 430 |
285 if (iv[LEFT] - horizon_padding > last_end + EPS) | 431 if (x1 > last_end + EPS) |
286 result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT
] - 2 * horizon_padding)); | 432 result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); |
287 | 433 |
288 Building b (*i, horizon_padding, horizon_axis, sky); | 434 result.push_back (*i); |
289 bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ()); | 435 last_building = *i; |
290 if (sloped_neighbours) | 436 last_end = i->end_; |
291 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horiz
on_padding, LEFT)); | 437 |
292 result.push_front (b); | 438 list<Building>::iterator j = i++; |
293 if (sloped_neighbours) | 439 buildings->erase (j); |
294 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horiz
on_padding, RIGHT)); | 440 } |
295 | 441 |
296 list<Box>::iterator j = i++; | |
297 boxes->erase (j); | |
298 last_end = result.front ().end_; | |
299 } | |
300 if (last_end < infinity_f) | 442 if (last_end < infinity_f) |
301 result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f)
); | 443 result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f))
; |
302 result.reverse (); | |
303 return result; | 444 return result; |
304 } | 445 } |
305 | 446 |
306 class LessThanBox | 447 class LessThanBuilding |
307 { | 448 { |
308 Axis a_; | |
309 | |
310 public: | 449 public: |
311 LessThanBox (Axis a) | 450 bool operator () (Building const &b1, Building const &b2) |
312 { | 451 { |
313 a_ = a; | 452 return b1.start_ < b2.start_ |
314 } | 453 || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.s
tart_)); |
315 | |
316 bool operator () (Box const &b1, Box const &b2) | |
317 { | |
318 return b1[a_][LEFT] < b2[a_][LEFT]; | |
319 } | 454 } |
320 }; | 455 }; |
321 | 456 |
| 457 /** |
| 458 BUILDINGS is a list of buildings, but they could be overlapping |
| 459 and in any order. The returned list of buildings is ordered and non-overlapp
ing. |
| 460 */ |
322 list<Building> | 461 list<Building> |
323 Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis ho
rizon_axis, Direction sky) | 462 Skyline::internal_build_skyline (list<Building> *buildings) const |
324 { | 463 { |
325 vsize size = boxes->size (); | 464 vsize size = buildings->size (); |
326 | 465 |
327 if (size == 0) | 466 if (size == 0) |
328 { | 467 { |
329 list<Building> result; | 468 list<Building> result; |
330 empty_skyline (&result); | 469 empty_skyline (&result); |
331 return result; | 470 return result; |
332 } | 471 } |
333 else if (size == 1) | 472 else if (size == 1) |
334 { | 473 { |
335 list<Building> result; | 474 list<Building> result; |
336 single_skyline (Building (boxes->front (), horizon_padding, horizon_axis,
sky), | 475 single_skyline (buildings->front (), &result); |
337 boxes->front ()[horizon_axis][LEFT] - horizon_padding, | |
338 horizon_padding, &result); | |
339 return result; | 476 return result; |
340 } | 477 } |
341 | 478 |
342 deque<list<Building> > partials; | 479 deque<list<Building> > partials; |
343 boxes->sort (LessThanBox (horizon_axis)); | 480 buildings->sort (LessThanBuilding ()); |
344 while (!boxes->empty ()) | 481 while (!buildings->empty ()) |
345 partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon
_axis, sky)); | 482 partials.push_back (non_overlapping_skyline (buildings)); |
346 | 483 |
347 /* we'd like to say while (partials->size () > 1) but that's O (n). | 484 /* we'd like to say while (partials->size () > 1) but that's O (n). |
348 Instead, we exit in the middle of the loop */ | 485 Instead, we exit in the middle of the loop */ |
349 while (!partials.empty ()) | 486 while (!partials.empty ()) |
350 { | 487 { |
351 list<Building> merged; | 488 list<Building> merged; |
352 list<Building> one = partials.front (); | 489 list<Building> one = partials.front (); |
353 partials.pop_front (); | 490 partials.pop_front (); |
354 if (partials.empty ()) | 491 if (partials.empty ()) |
355 return one; | 492 return one; |
(...skipping 25 matching lines...) Expand all Loading... |
381 } | 518 } |
382 } | 519 } |
383 | 520 |
384 Skyline::Skyline (Direction sky) | 521 Skyline::Skyline (Direction sky) |
385 { | 522 { |
386 sky_ = sky; | 523 sky_ = sky; |
387 empty_skyline (&buildings_); | 524 empty_skyline (&buildings_); |
388 } | 525 } |
389 | 526 |
390 /* | 527 /* |
391 build padded skyline from an existing skyline with padding | 528 Build skyline from a set of boxes. |
392 added to it. | 529 |
393 */ | 530 Boxes should have fatness in the horizon_axis, otherwise they are ignored. |
394 | |
395 Skyline::Skyline (Skyline const &src, Real horizon_padding, Axis /*a*/) | |
396 { | |
397 /* | |
398 We extract boxes from the skyline, then build a new skyline from | |
399 the boxes. | |
400 A box is created for every horizontal portion of the skyline | |
401 Because skylines are defined positive, and then inverted if they | |
402 are to be down-facing, we create the new skyline in the UP | |
403 direction, then give it the down direction if needed. | |
404 */ | |
405 Real start = -infinity_f; | |
406 list<Box> boxes; | |
407 | |
408 // establish a baseline box | |
409 // FIXME: This has hardcoded logic, assuming a == X_AXIS! | |
410 boxes.push_back (Box (Interval (-infinity_f, infinity_f), | |
411 Interval (0, 0))); | |
412 list<Building>::const_iterator end = src.buildings_.end (); | |
413 for (list<Building>::const_iterator i = src.buildings_.begin (); i != end; sta
rt = i->end_, i++) | |
414 if ((i->slope_ == 0) && !isinf (i->y_intercept_)) | |
415 boxes.push_back (Box (Interval (start, i->end_), | |
416 Interval (-infinity_f, i->y_intercept_))); | |
417 buildings_ = internal_build_skyline (&boxes, horizon_padding, X_AXIS, UP); | |
418 sky_ = src.sky_; | |
419 } | |
420 | |
421 /* | |
422 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxe
s | |
423 by that amount and add 45-degree sloped boxes to the edges of each box (of | |
424 width horizon_padding). That is, the total amount of horizontal expansion is | |
425 horizon_padding*4, half of which is sloped and half of which is flat. | |
426 | |
427 Boxes should have fatness in the horizon_axis (after they are expanded by | |
428 horizon_padding), otherwise they are ignored. | |
429 */ | 531 */ |
430 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_a
xis, Direction sky) | 532 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) |
431 { | 533 { |
432 list<Box> filtered_boxes; | 534 list<Building> buildings; |
433 sky_ = sky; | 535 sky_ = sky; |
434 | 536 |
435 Axis vert_axis = other_axis (horizon_axis); | 537 Axis vert_axis = other_axis (horizon_axis); |
436 for (vsize i = 0; i < boxes.size (); i++) | 538 for (vsize i = 0; i < boxes.size (); i++) |
437 { | 539 { |
438 Interval iv = boxes[i][horizon_axis]; | 540 Interval iv = boxes[i][horizon_axis]; |
439 iv.widen (horizon_padding); | |
440 if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) | 541 if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) |
441 filtered_boxes.push_front (boxes[i]); | 542 buildings.push_front (Building (boxes[i], horizon_axis, sky)); |
442 } | 543 } |
443 | 544 |
444 buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon
_axis, sky); | 545 buildings_ = internal_build_skyline (&buildings); |
445 } | 546 normalize (); |
446 | 547 } |
447 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Directi
on sky) | 548 |
448 { | 549 /* |
| 550 build skyline from a set of line segments. |
| 551 |
| 552 Buildings should have fatness in the horizon_axis, otherwise they are ignored. |
| 553 */ |
| 554 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis
, Direction sky) |
| 555 { |
| 556 list<Building> buildings; |
449 sky_ = sky; | 557 sky_ = sky; |
450 Building front (b, horizon_padding, horizon_axis, sky); | 558 |
451 single_skyline (front, b[horizon_axis][LEFT] - horizon_padding, | 559 for (vsize i = 0; i < segments.size (); i++) |
452 horizon_padding, &buildings_); | 560 { |
| 561 Drul_array<Offset> const &seg = segments[i]; |
| 562 Offset left = seg[LEFT]; |
| 563 Offset right = seg[RIGHT]; |
| 564 if (left[horizon_axis] > right[horizon_axis]) |
| 565 swap (left, right); |
| 566 |
| 567 Real x1 = left[horizon_axis]; |
| 568 Real x2 = right[horizon_axis]; |
| 569 Real y1 = left[other_axis (horizon_axis)] * sky; |
| 570 Real y2 = right[other_axis (horizon_axis)] * sky; |
| 571 |
| 572 if (x1 + EPS < x2) |
| 573 buildings.push_back (Building (x1, y1, y2, x2)); |
| 574 } |
| 575 |
| 576 buildings_ = internal_build_skyline (&buildings); |
| 577 normalize (); |
| 578 } |
| 579 |
| 580 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) |
| 581 { |
| 582 sky_ = sky; |
| 583 |
| 584 deque<Skyline> partials; |
| 585 for (vsize i = 0; i < skypairs.size (); i++) |
| 586 partials.push_back (Skyline ((skypairs[i])[sky])); |
| 587 |
| 588 while (partials.size () > 1) |
| 589 { |
| 590 Skyline one = partials.front (); |
| 591 partials.pop_front (); |
| 592 Skyline two = partials.front (); |
| 593 partials.pop_front (); |
| 594 |
| 595 one.merge (two); |
| 596 partials.push_back (one); |
| 597 } |
| 598 |
| 599 if (partials.size ()) |
| 600 buildings_.swap (partials.front ().buildings_); |
| 601 else |
| 602 buildings_.clear (); |
| 603 } |
| 604 |
| 605 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) |
| 606 { |
| 607 sky_ = sky; |
| 608 Building front (b, horizon_axis, sky); |
| 609 single_skyline (front, &buildings_); |
453 } | 610 } |
454 | 611 |
455 void | 612 void |
456 Skyline::merge (Skyline const &other) | 613 Skyline::merge (Skyline const &other) |
457 { | 614 { |
458 assert (sky_ == other.sky_); | 615 assert (sky_ == other.sky_); |
| 616 |
| 617 if (other.is_empty ()) |
| 618 return; |
| 619 |
| 620 if (is_empty ()) |
| 621 { |
| 622 buildings_ = other.buildings_; |
| 623 return; |
| 624 } |
459 | 625 |
460 list<Building> other_bld (other.buildings_); | 626 list<Building> other_bld (other.buildings_); |
461 list<Building> my_bld; | 627 list<Building> my_bld; |
462 my_bld.splice (my_bld.begin (), buildings_); | 628 my_bld.splice (my_bld.begin (), buildings_); |
463 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | 629 internal_merge_skyline (&other_bld, &my_bld, &buildings_); |
464 } | 630 normalize (); |
465 | 631 } |
466 void | 632 |
467 Skyline::insert (Box const &b, Real horizon_padding, Axis a) | 633 void |
| 634 Skyline::insert (Box const &b, Axis a) |
468 { | 635 { |
469 list<Building> other_bld; | 636 list<Building> other_bld; |
470 list<Building> my_bld; | 637 list<Building> my_bld; |
471 | 638 |
472 if (isnan (b[other_axis (a)][LEFT]) | 639 if (isnan (b[other_axis (a)][LEFT]) |
473 || isnan (b[other_axis (a)][RIGHT])) | 640 || isnan (b[other_axis (a)][RIGHT])) |
474 { | 641 { |
475 programming_error ("insane box for skyline"); | 642 programming_error ("insane box for skyline"); |
476 return; | 643 return; |
477 } | 644 } |
478 | 645 |
479 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ | 646 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ |
480 Interval iv = b[a]; | 647 Interval iv = b[a]; |
481 iv.widen (horizon_padding); | |
482 if (iv.length () <= EPS || b[other_axis (a)].is_empty ()) | 648 if (iv.length () <= EPS || b[other_axis (a)].is_empty ()) |
483 return; | 649 return; |
484 | 650 |
485 my_bld.splice (my_bld.begin (), buildings_); | 651 my_bld.splice (my_bld.begin (), buildings_); |
486 single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT] - horizon_p
adding, | 652 single_skyline (Building (b, a, sky_), &other_bld); |
487 horizon_padding, &other_bld); | |
488 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | 653 internal_merge_skyline (&other_bld, &my_bld, &buildings_); |
| 654 normalize (); |
489 } | 655 } |
490 | 656 |
491 void | 657 void |
492 Skyline::raise (Real r) | 658 Skyline::raise (Real r) |
493 { | 659 { |
494 list<Building>::iterator end = buildings_.end (); | 660 list<Building>::iterator end = buildings_.end (); |
495 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | 661 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) |
496 i->y_intercept_ += sky_ * r; | 662 i->y_intercept_ += sky_ * r; |
497 } | 663 } |
498 | 664 |
499 void | 665 void |
500 Skyline::shift (Real s) | 666 Skyline::shift (Real s) |
501 { | 667 { |
502 list<Building>::iterator end = buildings_.end (); | 668 list<Building>::iterator end = buildings_.end (); |
503 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | 669 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) |
504 { | 670 { |
| 671 i->start_ += s; |
505 i->end_ += s; | 672 i->end_ += s; |
506 i->y_intercept_ -= s * i->slope_; | 673 i->y_intercept_ -= s * i->slope_; |
507 } | 674 } |
508 } | 675 } |
509 | 676 |
510 Real | 677 Real |
511 Skyline::distance (Skyline const &other, Real horizon_padding) const | 678 Skyline::distance (Skyline const &other, Real horizon_padding) const |
512 { | 679 { |
513 Real dummy; | 680 Real dummy; |
514 return internal_distance (other, horizon_padding, &dummy); | 681 return internal_distance (other, horizon_padding, &dummy); |
515 } | 682 } |
516 | 683 |
517 Real | 684 Real |
518 Skyline::touching_point (Skyline const &other, Real horizon_padding) const | 685 Skyline::touching_point (Skyline const &other, Real horizon_padding) const |
519 { | 686 { |
520 Real touch; | 687 Real touch; |
521 internal_distance (other, horizon_padding, &touch); | 688 internal_distance (other, horizon_padding, &touch); |
522 return touch; | 689 return touch; |
523 } | 690 } |
524 | 691 |
525 Real | 692 Real |
526 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *to
uch_point) const | 693 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *to
uch_point) const |
527 { | 694 { |
| 695 if (horizon_padding == 0.0) |
| 696 return internal_distance (other, touch_point); |
| 697 |
| 698 // Note that it is not necessary to build a padded version of other, |
| 699 // because the same effect can be achieved just by doubling horizon_padding. |
| 700 Skyline padded_this = padded (horizon_padding); |
| 701 return padded_this.internal_distance (other, touch_point); |
| 702 } |
| 703 |
| 704 Skyline |
| 705 Skyline::padded (Real horizon_padding) const |
| 706 { |
| 707 list<Building> pad_buildings; |
| 708 for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.e
nd (); ++i) |
| 709 { |
| 710 if (i->start_ > -infinity_f) |
| 711 { |
| 712 Real height = i->height (i->start_); |
| 713 if (height > -infinity_f) |
| 714 { |
| 715 // Add the sloped building that pads the left side of the current
building. |
| 716 Real start = i->start_ - 2 * horizon_padding; |
| 717 Real end = i->start_ - horizon_padding; |
| 718 pad_buildings.push_back (Building (start, height - horizon_padding
, height, end)); |
| 719 |
| 720 // Add the flat building that pads the left side of the current bu
ilding. |
| 721 start = i->start_ - horizon_padding; |
| 722 end = i->start_; |
| 723 pad_buildings.push_back (Building (start, height, height, end)); |
| 724 } |
| 725 } |
| 726 |
| 727 if (i->end_ < infinity_f) |
| 728 { |
| 729 Real height = i->height (i->end_); |
| 730 if (height > -infinity_f) |
| 731 { |
| 732 // Add the flat building that pads the right side of the current b
uilding. |
| 733 Real start = i->end_; |
| 734 Real end = start + horizon_padding; |
| 735 pad_buildings.push_back (Building (start, height, height, end)); |
| 736 |
| 737 // Add the sloped building that pads the right side of the current
building. |
| 738 start = end; |
| 739 end += horizon_padding; |
| 740 pad_buildings.push_back (Building (start, height, height - horizon
_padding, end)); |
| 741 } |
| 742 } |
| 743 } |
| 744 |
| 745 // The buildings may be overlapping, so resolve that. |
| 746 list<Building> pad_skyline = internal_build_skyline (&pad_buildings); |
| 747 |
| 748 // Merge the padding with the original, to make a new skyline. |
| 749 Skyline padded (sky_); |
| 750 list<Building> my_buildings = buildings_; |
| 751 padded.buildings_.clear (); |
| 752 internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); |
| 753 padded.normalize (); |
| 754 |
| 755 return padded; |
| 756 } |
| 757 |
| 758 Real |
| 759 Skyline::internal_distance (Skyline const &other, Real *touch_point) const |
| 760 { |
528 assert (sky_ == -other.sky_); | 761 assert (sky_ == -other.sky_); |
529 | 762 |
530 Skyline const *padded_this = this; | 763 list<Building>::const_iterator i = buildings_.begin (); |
531 Skyline const *padded_other = &other; | 764 list<Building>::const_iterator j = other.buildings_.begin (); |
532 bool created_tmp_skylines = false; | |
533 | |
534 /* | |
535 For systems, padding is not added at creation time. Padding is | |
536 added to AxisGroup objects when outside-staff objects are added. | |
537 Thus, when we want to place systems with horizontal padding, | |
538 we do it at distance calculation time. | |
539 */ | |
540 if (horizon_padding != 0.0) | |
541 { | |
542 padded_this = new Skyline (*padded_this, horizon_padding, X_AXIS); | |
543 padded_other = new Skyline (*padded_other, horizon_padding, X_AXIS); | |
544 created_tmp_skylines = true; | |
545 } | |
546 | |
547 list<Building>::const_iterator i = padded_this->buildings_.begin (); | |
548 list<Building>::const_iterator j = padded_other->buildings_.begin (); | |
549 | 765 |
550 Real dist = -infinity_f; | 766 Real dist = -infinity_f; |
551 Real start = -infinity_f; | 767 Real start = -infinity_f; |
552 Real touch = -infinity_f; | 768 Real touch = -infinity_f; |
553 while (i != padded_this->buildings_.end () && j != padded_other->buildings_.en
d ()) | 769 while (i != buildings_.end () && j != other.buildings_.end ()) |
554 { | 770 { |
555 Real end = min (i->end_, j->end_); | 771 Real end = min (i->end_, j->end_); |
556 Real start_dist = i->height (start) + j->height (start); | 772 Real start_dist = i->height (start) + j->height (start); |
557 Real end_dist = i->height (end) + j->height (end); | 773 Real end_dist = i->height (end) + j->height (end); |
558 dist = max (dist, max (start_dist, end_dist)); | 774 dist = max (dist, max (start_dist, end_dist)); |
559 | 775 |
560 if (end_dist == dist) | 776 if (end_dist == dist) |
561 touch = end; | 777 touch = end; |
562 else if (start_dist == dist) | 778 else if (start_dist == dist) |
563 touch = start; | 779 touch = start; |
564 | 780 |
565 if (i->end_ <= j->end_) | 781 if (i->end_ <= j->end_) |
566 i++; | 782 i++; |
567 else | 783 else |
568 j++; | 784 j++; |
569 start = end; | 785 start = end; |
570 } | 786 } |
571 | 787 |
572 if (created_tmp_skylines) | |
573 { | |
574 delete padded_this; | |
575 delete padded_other; | |
576 } | |
577 | |
578 *touch_point = touch; | 788 *touch_point = touch; |
579 return dist; | 789 return dist; |
580 } | 790 } |
581 | 791 |
| 792 // changes the direction that the skyline is pointing |
| 793 void |
| 794 Skyline::invert () |
| 795 { |
| 796 list<Building>::iterator i; |
| 797 for (i = buildings_.begin (); i != buildings_.end (); i++) |
| 798 if (!isinf (i->y_intercept_)) |
| 799 { |
| 800 i->y_intercept_ *= -1; |
| 801 i->slope_ *= -1; |
| 802 } |
| 803 |
| 804 sky_ = -sky_; |
| 805 } |
| 806 |
582 Real | 807 Real |
583 Skyline::height (Real airplane) const | 808 Skyline::height (Real airplane) const |
584 { | 809 { |
585 assert (!isinf (airplane)); | 810 assert (!isinf (airplane)); |
586 | 811 |
587 list<Building>::const_iterator i; | 812 list<Building>::const_iterator i; |
588 for (i = buildings_.begin (); i != buildings_.end (); i++) | 813 for (i = buildings_.begin (); i != buildings_.end (); i++) |
589 { | 814 { |
590 if (i->end_ >= airplane) | 815 if (i->end_ >= airplane) |
591 return sky_ * i->height (airplane); | 816 return sky_ * i->height (airplane); |
592 } | 817 } |
593 | 818 |
594 assert (0); | 819 assert (0); |
595 return 0; | 820 return 0; |
596 } | 821 } |
597 | 822 |
598 Real | 823 Real |
599 Skyline::max_height () const | 824 Skyline::max_height () const |
600 { | 825 { |
601 Skyline s (-sky_); | 826 Real ret = -infinity_f; |
602 s.set_minimum_height (0); | 827 |
603 return sky_ * distance (s); | 828 list<Building>::const_iterator i; |
| 829 for (i = buildings_.begin (); i != buildings_.end (); ++i) |
| 830 { |
| 831 ret = max (ret, i->height (i->start_)); |
| 832 ret = max (ret, i->height (i->end_)); |
| 833 } |
| 834 |
| 835 return sky_ * ret; |
604 } | 836 } |
605 | 837 |
606 Real | 838 Real |
607 Skyline::max_height_position () const | 839 Skyline::max_height_position () const |
608 { | 840 { |
609 Skyline s (-sky_); | 841 Skyline s (-sky_); |
610 s.set_minimum_height (0); | 842 s.set_minimum_height (0); |
611 return touching_point (s); | 843 return touching_point (s); |
612 } | 844 } |
613 | 845 |
(...skipping 19 matching lines...) Expand all Loading... |
633 start = i->end_; | 865 start = i->end_; |
634 } | 866 } |
635 | 867 |
636 if (horizon_axis == Y_AXIS) | 868 if (horizon_axis == Y_AXIS) |
637 for (vsize i = 0; i < out.size (); i++) | 869 for (vsize i = 0; i < out.size (); i++) |
638 out[i] = out[i].swapped (); | 870 out[i] = out[i].swapped (); |
639 | 871 |
640 return out; | 872 return out; |
641 } | 873 } |
642 | 874 |
| 875 // Returns the smallest (non-negative) shift in the given |
| 876 // direction which will result in THIS and OTHER not overlapping. |
| 877 // Warning: this function is O(n^2 log n). Use sparingly. |
| 878 Real |
| 879 Skyline::smallest_shift (Skyline const &other, |
| 880 Direction d, |
| 881 Real horizon_padding, |
| 882 Real vertical_padding) const |
| 883 { |
| 884 // If one or both of the paddings is zero, this can |
| 885 // be optimized... |
| 886 Skyline padded_me = padded (horizon_padding); |
| 887 padded_me.raise (vertical_padding); |
| 888 |
| 889 list<Building>::const_iterator i = padded_me.buildings_.begin (); |
| 890 list<Building>::const_iterator j = other.buildings_.begin (); |
| 891 list<Building>::const_iterator i_end = padded_me.buildings_.end (); |
| 892 list<Building>::const_iterator j_end = other.buildings_.end (); |
| 893 |
| 894 // Find all shifts that are not allowed. |
| 895 vector<Interval> forbidden_shifts; |
| 896 for (; i != i_end; ++i) |
| 897 if (i->y_intercept_ != -infinity_f) |
| 898 for (j = other.buildings_.begin (); j != j_end; ++j) |
| 899 { |
| 900 Interval iv = i->overlapping_shift_interval (*j); |
| 901 if (!iv.is_empty ()) |
| 902 forbidden_shifts.push_back (iv); |
| 903 } |
| 904 |
| 905 // Now comes the trick: we want to find the smallest point |
| 906 // that is not in the union of forbidden_shifts. We can represent |
| 907 // the union of forbidden_shifts as a skyline, where a point is |
| 908 // allowed if it has height -infinity_f and forbidden otherwise. |
| 909 vector<Box> boxes; |
| 910 for (vector<Interval>::iterator k = forbidden_shifts.begin (); |
| 911 k != forbidden_shifts.end (); ++k) |
| 912 boxes.push_back (Box (*k, Interval (-1, 0))); |
| 913 Skyline s (boxes, X_AXIS, UP); |
| 914 |
| 915 // Find the smallest (ie. closest to zero, in the appropriate direction) |
| 916 // coordinate where the height of s is -infinity_f. |
| 917 Real last_good_point = -infinity_f; |
| 918 for (i = s.buildings_.begin (); i != s.buildings_.end (); ++i) |
| 919 { |
| 920 if (d == LEFT && i->start_ > 0) |
| 921 return last_good_point; |
| 922 |
| 923 if (i->y_intercept_ == -infinity_f) |
| 924 { |
| 925 if (i->start_ <= 0 && i->end_ >= 0) |
| 926 return 0; |
| 927 if (d == RIGHT && i->start_ >= 0) |
| 928 return i->start_; |
| 929 |
| 930 last_good_point = i->end_; |
| 931 } |
| 932 } |
| 933 |
| 934 return infinity_f * d; |
| 935 } |
| 936 |
643 Real | 937 Real |
644 Skyline::left () const | 938 Skyline::left () const |
645 { | 939 { |
646 Building b = buildings_.front (); | 940 for (list<Building>::const_iterator i (buildings_.begin ()); |
647 return b.end_; | 941 i != buildings_.end (); i++) |
| 942 if (i->y_intercept_ > -infinity_f) |
| 943 return i->start_; |
| 944 |
| 945 return infinity_f; |
648 } | 946 } |
649 | 947 |
650 Real | 948 Real |
651 Skyline::right () const | 949 Skyline::right () const |
652 { | 950 { |
653 if (buildings_.size () == 1) | 951 for (list<Building>::const_reverse_iterator i (buildings_.rbegin ()); |
654 return -infinity_f; | 952 i != buildings_.rend (); ++i) |
655 | 953 if (i->y_intercept_ > -infinity_f) |
656 Real out = 0.0; | 954 return i->end_; |
657 for (list<Building>::const_iterator i (buildings_.begin ()); | 955 |
658 i != buildings_.end (); i++) | 956 return -infinity_f; |
659 if (i->end_ < infinity_f) | |
660 out = i->end_; | |
661 | |
662 return out; | |
663 } | 957 } |
664 | 958 |
665 bool | 959 bool |
666 Skyline::is_empty () const | 960 Skyline::is_empty () const |
667 { | 961 { |
| 962 if (!buildings_.size ()) |
| 963 return true; |
668 Building b = buildings_.front (); | 964 Building b = buildings_.front (); |
669 return b.end_ == infinity_f && b.y_intercept_ == -infinity_f; | 965 return b.end_ == infinity_f && b.y_intercept_ == -infinity_f; |
| 966 } |
| 967 |
| 968 bool |
| 969 Skyline::is_singleton () const |
| 970 { |
| 971 return buildings_.size () == 3; |
670 } | 972 } |
671 | 973 |
672 void | 974 void |
673 Skyline::clear () | 975 Skyline::clear () |
674 { | 976 { |
675 buildings_.clear (); | 977 buildings_.clear (); |
676 empty_skyline (&buildings_); | 978 empty_skyline (&buildings_); |
677 } | 979 } |
678 | 980 |
679 /****************************************************************/ | 981 /****************************************************************/ |
680 | 982 |
681 IMPLEMENT_SIMPLE_SMOBS (Skyline); | 983 IMPLEMENT_SIMPLE_SMOBS (Skyline); |
682 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); | 984 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?"); |
683 IMPLEMENT_DEFAULT_EQUAL_P (Skyline); | 985 IMPLEMENT_DEFAULT_EQUAL_P (Skyline); |
684 | 986 |
685 SCM | 987 SCM |
686 Skyline::mark_smob (SCM) | 988 Skyline::mark_smob (SCM s) |
687 { | 989 { |
688 ASSERT_LIVE_IS_ALLOWED (); | 990 ASSERT_LIVE_IS_ALLOWED (s); |
689 return SCM_EOL; | 991 return SCM_EOL; |
690 } | 992 } |
691 | 993 |
692 int | 994 int |
693 Skyline::print_smob (SCM s, SCM port, scm_print_state *) | 995 Skyline::print_smob (SCM s, SCM port, scm_print_state *) |
694 { | 996 { |
695 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s); | 997 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s); |
696 (void) r; | 998 (void) r; |
697 | 999 |
698 scm_puts ("#<Skyline>", port); | 1000 scm_puts ("#<Skyline>", port); |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
750 return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ())
; | 1052 return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ())
; |
751 } | 1053 } |
752 | 1054 |
753 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2) | 1055 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2) |
754 SCM | 1056 SCM |
755 Skyline::get_height (SCM skyline_scm, SCM x_scm) | 1057 Skyline::get_height (SCM skyline_scm, SCM x_scm) |
756 { | 1058 { |
757 Real x = robust_scm2double (x_scm, 0.0); | 1059 Real x = robust_scm2double (x_scm, 0.0); |
758 return scm_from_double (Skyline::unsmob (skyline_scm)->height (x)); | 1060 return scm_from_double (Skyline::unsmob (skyline_scm)->height (x)); |
759 } | 1061 } |
LEFT | RIGHT |