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