Left: | ||
Right: |
OLD | NEW |
---|---|
1 /* | 1 /* |
2 This file is part of LilyPond, the GNU music typesetter. | 2 This file is part of LilyPond, the GNU music typesetter. |
3 | 3 |
4 Copyright (C) 2006--2020 Joe Neeman <joeneeman@gmail.com> | 4 Copyright (C) 2006--2020 Joe Neeman <joeneeman@gmail.com> |
5 | 5 |
6 LilyPond is free software: you can redistribute it and/or modify | 6 LilyPond is free software: you can redistribute it and/or modify |
7 it under the terms of the GNU General Public License as published by | 7 it under the terms of the GNU General Public License as published by |
8 the Free Software Foundation, either version 3 of the License, or | 8 the Free Software Foundation, either version 3 of the License, or |
9 (at your option) any later version. | 9 (at your option) any later version. |
10 | 10 |
11 LilyPond is distributed in the hope that it will be useful, | 11 LilyPond is distributed in the hope that it will be useful, |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | 12 but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 GNU General Public License for more details. | 14 GNU General Public License for more details. |
15 | 15 |
16 You should have received a copy of the GNU General Public License | 16 You should have received a copy of the GNU General Public License |
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. | 17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. |
18 */ | 18 */ |
19 | 19 |
20 #include <cstdio> | |
21 #include <deque> | |
22 #include <vector> | |
23 | |
24 #include "box.hh" | |
25 #include "direction.hh" | |
26 #include "lily-guile.hh" | |
27 #include "skyline-pair.hh" | |
20 #include "skyline.hh" | 28 #include "skyline.hh" |
21 #include "skyline-pair.hh" | |
22 #include <deque> | |
23 #include <cstdio> | |
24 | 29 |
25 using std::deque; | 30 using std::deque; |
26 using std::list; | 31 using std::isinf; |
32 using std::isnan; | |
33 using std::swap; | |
27 using std::vector; | 34 using std::vector; |
28 | 35 |
29 /* A skyline is a sequence of non-overlapping buildings: something like | 36 /* A skyline is a sequence of non-overlapping buildings: something like |
30 this: | 37 this: |
31 _______ | 38 _______ |
32 | \ ________ | 39 | \ ________ |
33 | \ ________/ \ | 40 | \ ________/ \ |
34 /\ | \ / \ | 41 /\ | \ / \ |
35 / -------- \ / \ | 42 / -------- \ / \ |
36 / \ / \ | 43 / \ / \ |
37 / ------------/ ---- | 44 / ------------/ ---- |
38 -- | 45 -- |
46 | |
39 Each building has a starting position, and ending position, a starting | 47 Each building has a starting position, and ending position, a starting |
40 height and an ending height. | 48 height and an ending height. |
41 | 49 |
42 The following invariants are observed: | 50 The following invariants are observed: |
43 - the start of the first building is at -infinity | |
44 - the end of the last building is at infinity | |
45 - if a building has infinite length (ie. the first and last buildings), | 51 - if a building has infinite length (ie. the first and last buildings), |
46 then its starting height and ending height are equal | 52 then its starting height and ending height are equal |
47 - the end of one building is the same as the beginning of the next | |
48 building | |
49 | 53 |
50 We also allow skylines to point down (the structure is exactly the same, | 54 We also allow skylines to point down (the structure is exactly the same, |
51 but we think of the part above the line as being filled with mass and the | 55 but we think of the part above the line as being filled with mass and the |
52 part below as being empty). ::distance finds the minimum distance between | 56 part below as being empty). ::distance finds the minimum distance between |
53 an UP skyline and a DOWN skyline. | 57 an UP skyline and a DOWN skyline. |
54 | 58 |
55 Note that we store DOWN skylines upside-down. That is, in order to compare | 59 Note that we store DOWN skylines upside-down. That is, in order to compare |
56 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first. | 60 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first. |
57 This means that the merging routine doesn't need to be aware of direction, | 61 This means that the merging routine doesn't need to be aware of direction, |
58 but the distance routine does. | 62 but the distance routine does. |
59 | 63 |
60 From 2007 through 2012, buildings of width less than EPS were discarded, | 64 From 2007 through 2012, buildings of width less than EPS were discarded, |
61 citing numerical accuracy concerns. We remember that floating point | 65 citing numerical accuracy concerns. We remember that floating point |
62 comparisons of nearly-equal values can be affected by rounding error. | 66 comparisons of nearly-equal values can be affected by rounding error. |
63 Also, some target machines use the x87 floating point unit, which provides | 67 Also, some target machines use the x87 floating point unit, which provides |
64 extended precision for intermediate results held in registers. On this type | 68 extended precision for intermediate results held in registers. On this type |
65 of hardware comparisons such as | 69 of hardware comparisons such as |
66 double c = 1.0/3.0; boolean compare = (c == 1.0/3.0) | 70 double c = 1.0/3.0; boolean compare = (c == 1.0/3.0) |
67 could go either way because the 1.0/3.0 is allowed to be kept | 71 could go either way because the 1.0/3.0 is allowed to be kept |
68 higher precision than the variable 'c'. | 72 higher precision than the variable 'c'. |
69 Alert to these considerations, we now accept buildings of zero-width. | 73 Alert to these considerations, we now accept buildings of zero-width. |
70 */ | 74 */ |
71 | 75 |
76 bool | |
77 Building::intersect (Building const &o, Real *inter_x) const | |
78 { | |
79 // Solve y1 + (x - x1) * slope1 == y2 + (x - x2) * slope2 | |
80 Real s = o.slope () - slope (); | |
81 if (s == 0.0) | |
82 { | |
83 return false; | |
84 } | |
85 | |
86 *inter_x = ((y () + (o.slope () ? o.slope () * o.start () : 0.0)) | |
87 - (o.y () + (slope () ? slope () * start () : 0.0))) | |
88 / s; | |
89 assert (!isnan (*inter_x)); | |
90 if (*inter_x < start () || *inter_x < o.start ()) | |
91 { | |
92 return false; | |
93 } | |
94 if (*inter_x > end () || *inter_x > o.end ()) | |
95 { | |
96 return false; | |
97 } | |
98 | |
99 return true; | |
100 } | |
101 | |
102 class BuildingQueue | |
103 { | |
104 const vector<Building> &bs_; | |
105 size_t i_; | |
106 Building front_; | |
107 | |
108 public: | |
109 BuildingQueue (vector<Building> const &v) : bs_ (v) | |
110 { | |
111 i_ = 0; | |
112 front_ = v[0]; | |
113 } | |
114 | |
115 bool ok () const { return i_ < bs_.size (); } | |
116 Real start () const { return front_.start (); } | |
117 Real end () const { return front_.end (); } | |
118 Real y () const { return front_.y (); } | |
119 Real slope () const { return front_.slope (); } | |
120 Building front () const { return front_; } | |
121 Real height_at (Real x) const { return front_.height_at (x); } | |
122 void next () | |
123 { | |
124 i_++; | |
125 if (ok ()) | |
126 { | |
127 front_ = bs_[i_]; | |
128 } | |
129 } | |
130 | |
131 // Split the current building at x, return the left part, and keep | |
132 // the right part. If `x` falls outside of the building, call `next`. | |
133 Building split_off (Real x) | |
134 { | |
135 Building b = front_; | |
136 if (x < front_.end ()) | |
137 { | |
138 b.trim_right (x); | |
139 front_.trim_left (x); | |
140 } | |
141 else | |
142 { | |
143 next (); | |
144 } | |
145 return b; | |
146 } | |
147 }; | |
148 | |
149 // Ensure top provides the building that will be on top | |
72 static void | 150 static void |
73 print_buildings (list<Building> const &b) | 151 reorder (BuildingQueue *&top, BuildingQueue *&bot) |
74 { | 152 { |
75 for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++) | 153 while (top->ok () && top->start () == top->end ()) |
76 i->print (); | 154 { |
155 top->next (); | |
156 } | |
157 while (bot->ok () && bot->start () == bot->end ()) | |
158 { | |
159 bot->next (); | |
160 } | |
161 | |
162 if (!top->ok ()) | |
163 { | |
164 swap (top, bot); | |
165 } | |
166 | |
167 if (!top->ok () || !bot->ok ()) | |
168 { | |
169 return; | |
170 } | |
171 | |
172 if (Building::less (bot->front (), top->front ())) | |
173 { | |
174 swap (top, bot); | |
175 } | |
77 } | 176 } |
78 | 177 |
79 void | 178 void |
80 Skyline::print () const | 179 add_merge_result (vector<Building> *dest, Building const &b) |
81 { | 180 { |
82 print_buildings (buildings_); | 181 assert (!isnan (b.y ()) && !isinf (b.y ())); |
83 } | 182 if (!dest->empty () && b.start () == dest->back ().end () && b.slope () == 0.0 |
84 | 183 && b.y () == dest->back ().y () && dest->back ().slope () == 0.0) |
85 void | 184 { |
86 Skyline::print_points () const | 185 dest->back ().extend (b.end ()); |
87 { | |
88 vector<Offset> ps (to_points (X_AXIS)); | |
89 | |
90 for (vsize i = 0; i < ps.size (); i++) | |
91 printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS], | |
92 (i % 2) == 1 ? "\n" : " "); | |
93 } | |
94 | |
95 Building::Building (Real start, Real start_height, Real end_height, Real end) | |
96 : x_ (start, end) | |
97 { | |
98 if (std::isinf (start) || std::isinf (end)) | |
99 assert (start_height == end_height); | |
100 | |
101 precompute (start_height, end_height); | |
102 } | |
103 | |
104 Building::Building (Box const &b, Axis horizon_axis, Direction sky) | |
105 : x_ (b[horizon_axis]) | |
106 { | |
107 Real height = sky * b[other_axis (horizon_axis)][sky]; | |
108 | |
109 precompute (height, height); | |
110 } | |
111 | |
112 void | |
113 Building::precompute (Real start_height, Real end_height) | |
114 { | |
115 slope_ = 0.0; /* if they were both infinite, we would get nan, not 0, from the prev line */ | |
116 if (start_height != end_height) | |
117 slope_ = (end_height - start_height) / x_.length (); | |
118 | |
119 assert (std::isfinite (slope_)); | |
120 | |
121 if (std::isinf (x_[LEFT])) | |
122 { | |
123 assert (start_height == end_height); | |
124 y_intercept_ = start_height; | |
125 } | |
126 else if (fabs (slope_) > 1e6) | |
127 // too steep to be stored in slope-intercept form, given round-off error | |
128 { | |
129 slope_ = 0.0; | |
130 y_intercept_ = std::max (start_height, end_height); | |
131 } | 186 } |
132 else | 187 else |
133 y_intercept_ = start_height - slope_ * x_[LEFT]; | 188 { |
134 } | 189 dest->push_back (b); |
135 | 190 } |
136 inline Real | 191 } |
137 Building::height (Real x) const | 192 |
138 { | 193 vector<Building> static internal_merge_skylines (const vector<Building> &b1, |
139 return std::isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; | 194 const vector<Building> &b2) |
140 } | 195 { |
141 | 196 if (b1.empty ()) |
142 void | 197 { |
143 Building::print () const | 198 return b2; |
144 { | 199 } |
145 printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, x_[LEFT], | 200 if (b2.empty ()) |
146 x_[RIGHT]); | 201 { |
147 } | 202 return b1; |
148 | 203 } |
149 inline Real | 204 |
150 Building::intersection_x (Building const &other) const | 205 vector<Building> result; |
151 { | 206 BuildingQueue q1 (b1), q2 (b2); |
152 Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); | 207 |
153 return std::isnan (ret) ? -infinity_f : ret; | 208 BuildingQueue *top = &q1; |
154 } | 209 BuildingQueue *bot = &q2; |
155 | 210 reorder (top, bot); |
156 // Returns a shift s such that (x + s, y) intersects the roof of | 211 |
157 // this building. If no such shift exists, returns infinity_f. | 212 while (top->ok () && bot->ok ()) |
158 Real | 213 { |
159 Building::shift_to_intersect (Real x, Real y) const | 214 if (bot->start () >= top->end ()) |
160 { | 215 { |
161 // Solve for s: y = (x + s)*m + b | 216 // no overlap. |
162 Real ret = (y - y_intercept_ - slope_ * x) / slope_; | 217 add_merge_result (&result, top->front ()); |
163 | 218 top->next (); |
164 if (ret >= x_[LEFT] && ret <= x_[RIGHT] && !std::isinf (ret)) | 219 reorder (top, bot); |
165 return ret; | 220 continue; |
166 return infinity_f; | 221 } |
167 } | 222 |
168 | 223 // top and bot have overlap. |
169 bool | 224 |
170 Building::above (Building const &other, Real x) const | 225 Real inter_x; |
171 { | 226 if (top->front ().intersect (bot->front (), &inter_x)) |
172 return (std::isinf (y_intercept_) || std::isinf (other.y_intercept_) || std::i sinf (x)) | 227 { |
173 ? y_intercept_ > other.y_intercept_ | 228 if (bot->slope () < top->slope ()) |
174 : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_; | |
175 } | |
176 | |
177 // Remove redundant empty buildings from the skyline. | |
178 // If there are two adjacent empty buildings, they can be | |
179 // turned into one. | |
180 void | |
181 Skyline::normalize () | |
182 { | |
183 bool last_empty = false; | |
184 list<Building>::iterator i; | |
185 | |
186 for (i = buildings_.begin (); i != buildings_.end (); i++) | |
187 { | |
188 if (last_empty && i->y_intercept_ == -infinity_f) | |
189 { | |
190 list<Building>::iterator last = i; | |
191 last--; | |
192 last->x_[RIGHT] = i->x_[RIGHT]; | |
193 buildings_.erase (i); | |
194 i = last; | |
195 } | |
196 last_empty = (i->y_intercept_ == -infinity_f); | |
197 } | |
198 | |
199 assert (buildings_.front ().x_[LEFT] == -infinity_f); | |
200 assert (buildings_.back ().x_[RIGHT] == infinity_f); | |
201 } | |
202 | |
203 void | |
204 Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc, | |
205 list<Building> *const result) const | |
206 { | |
207 if (sb->empty () || sc->empty ()) | |
208 { | |
209 programming_error ("tried to merge an empty skyline"); | |
210 return; | |
211 } | |
212 | |
213 Building b = sb->front (); | |
214 for (; !sc->empty (); sc->pop_front ()) | |
215 { | |
216 /* Building b is continuing from the previous pass through the loop. | |
217 Building c is newly-considered, and starts no earlier than b started. | |
218 The comments draw b as if its roof had zero slope ----. | |
219 with dashes where b lies above c. | |
220 The roof of c could rise / or fall \ through the roof of b, | |
221 or the vertical sides | of c could intersect the roof of b. */ | |
222 Building c = sc->front (); | |
223 if (b.x_[RIGHT] < c.x_[RIGHT]) /* finish with b */ | |
224 { | |
225 if (b.x_[RIGHT] <= b.x_[LEFT]) /* we are already finished with b */ | |
226 ; | |
227 else if (c.above (b, c.x_[LEFT])) /* -| . | */ | |
228 { | 229 { |
229 Building m (b); | 230 // bot is descending into top, so it must start above. |
230 m.x_[RIGHT] = c.x_[LEFT]; | 231 add_merge_result (&result, top->split_off (bot->start ())); |
231 if (m.x_[RIGHT] > m.x_[LEFT]) | 232 top->split_off (inter_x); |
232 result->push_back (m); | 233 add_merge_result (&result, bot->split_off (inter_x)); |
233 if (b.above (c, b.x_[RIGHT])) /* -|\--. */ | 234 } |
234 { | 235 else if (bot->slope () > top->slope ()) |
235 Building n (c); | 236 { |
236 n.x_[RIGHT] = b.x_[LEFT] = b.intersection_x (c); | 237 // bot is erupting from below, so it will be the new top. |
237 result->push_back (n); | 238 add_merge_result (&result, top->split_off (inter_x)); |
238 result->push_back (b); | 239 bot->split_off (inter_x); |
239 } | 240 swap (top, bot); |
241 } | |
242 | |
243 // Process the intersection now, so we don't find an | |
244 // intersection at x==start() on the next round | |
245 if (top->end () > bot->end ()) | |
246 { | |
247 bot->next (); | |
240 } | 248 } |
241 else | 249 else |
242 { | 250 { |
243 if (c.above (b, b.x_[RIGHT])) /* ---/ . | */ | 251 // top finishes first. |
244 b.x_[RIGHT] = b.intersection_x (c); | 252 add_merge_result (&result, top->front ()); |
245 else /* -----. */ | 253 bot->split_off (top->end ()); |
246 c.x_[LEFT] = b.x_[RIGHT]; | 254 top->next (); |
247 result->push_back (b); | 255 reorder (top, bot); |
248 } | 256 } |
249 /* 'c' continues further, so move it into 'b' for the next pass. */ | 257 continue; |
250 b = c; | 258 } |
251 std::swap (sb, sc); | 259 |
252 } | 260 // No intersection. |
253 else /* b.x_[RIGHT] > c.x_[RIGHT] so finish with c */ | 261 |
254 { | 262 if (bot->start () == top->start ()) |
255 if (c.above (b, c.x_[LEFT])) /* -| |---. */ | 263 { |
256 { | 264 Real x = std::min (top->end (), bot->end ()); |
257 Building m (b); | 265 add_merge_result (&result, top->split_off (x)); |
258 m.x_[RIGHT] = c.x_[LEFT]; | 266 bot->split_off (x); |
259 if (m.x_[RIGHT] > m.x_[LEFT]) | 267 reorder (top, bot); |
260 result->push_back (m); | 268 continue; |
261 if (b.above (c, c.x_[RIGHT])) /* -| \---. */ | 269 } |
262 c.x_[RIGHT] = b.intersection_x (c); | 270 else if (top->front ().height_at (bot->start ()) > bot->y ()) |
263 } | 271 { |
264 else if (c.above (b, c.x_[RIGHT])) /* ---/|--. */ | 272 bot->split_off (top->end ()); |
265 { | 273 reorder (top, bot); |
266 Building m (b); | 274 continue; |
267 c.x_[LEFT] = m.x_[RIGHT] = b.intersection_x (c); | 275 } |
268 result->push_back (m); | 276 else |
269 } | 277 { |
270 else /* c is completely hidden by b */ | 278 add_merge_result (&result, top->split_off (bot->start ())); |
271 continue; | 279 swap (top, bot); |
272 result->push_back (c); | 280 continue; |
273 b.x_[LEFT] = c.x_[RIGHT]; | 281 } |
274 } | 282 } |
275 } | 283 |
276 if (b.x_[RIGHT] > b.x_[LEFT]) | 284 if (bot->ok ()) |
277 result->push_back (b); | 285 { |
278 } | 286 swap (top, bot); |
279 | 287 } |
288 | |
289 while (top->ok ()) | |
290 { | |
291 add_merge_result (&result, top->front ()); | |
292 top->next (); | |
293 } | |
294 | |
295 return result; | |
296 } | |
297 | |
298 /* Partition BUILDINGS into a non-overlapping set of boxes and the rest */ | |
280 static void | 299 static void |
281 empty_skyline (list<Building> *const ret) | 300 non_overlapping_skyline (vector<Building> const &buildings, |
282 { | 301 vector<Building> *trimmed, vector<Building> *result) |
283 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f)) ; | 302 { |
284 } | 303 trimmed->reserve (buildings.size () / 2); |
285 | 304 result->reserve (buildings.size () / 2); |
286 /* | 305 |
287 Given Building 'b', build a skyline containing only that building. | 306 for (auto const &b : buildings) |
288 */ | 307 { |
289 static void | 308 if (result->empty () || !result->back ().x ().contains (b[LEFT])) |
290 single_skyline (Building b, list<Building> *const ret) | 309 { |
291 { | 310 result->push_back (b); |
292 assert (b.x_[RIGHT] >= b.x_[LEFT]); | 311 } |
293 | 312 else |
294 if (b.x_[LEFT] != -infinity_f) | 313 { |
295 ret->push_back ( | 314 trimmed->push_back (b); |
296 Building (-infinity_f, -infinity_f, -infinity_f, b.x_[LEFT])); | 315 } |
297 ret->push_back (b); | 316 } |
298 if (b.x_[RIGHT] != infinity_f) | |
299 ret->push_back ( | |
300 Building (b.x_[RIGHT], -infinity_f, -infinity_f, infinity_f)); | |
301 } | |
302 | |
303 /* remove a non-overlapping set of boxes from BOXES and build a skyline | |
304 out of them */ | |
305 static list<Building> | |
306 non_overlapping_skyline (list<Building> *const buildings) | |
307 { | |
308 list<Building> result; | |
309 Real last_end = -infinity_f; | |
310 Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); | |
311 list<Building>::iterator i = buildings->begin (); | |
312 while (i != buildings->end ()) | |
313 { | |
314 Real x1 = i->x_[LEFT]; | |
315 Real y1 = i->height (i->x_[LEFT]); | |
316 Real x2 = i->x_[RIGHT]; | |
317 Real y2 = i->height (i->x_[RIGHT]); | |
318 | |
319 // Drop buildings that will obviously have no effect. | |
320 if (last_building.height (x1) >= y1 && last_building.x_[RIGHT] >= x2 | |
321 && last_building.height (x2) >= y2) | |
322 { | |
323 list<Building>::iterator j = i++; | |
324 buildings->erase (j); | |
325 continue; | |
326 } | |
327 | |
328 if (x1 < last_end) | |
329 { | |
330 i++; | |
331 continue; | |
332 } | |
333 | |
334 // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH) | |
335 if (x1 > last_end) | |
336 result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); | |
337 | |
338 result.push_back (*i); | |
339 last_building = *i; | |
340 last_end = i->x_[RIGHT]; | |
341 | |
342 list<Building>::iterator j = i++; | |
343 buildings->erase (j); | |
344 } | |
345 | |
346 if (last_end < infinity_f) | |
347 result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f)) ; | |
348 return result; | |
349 } | 317 } |
350 | 318 |
351 class LessThanBuilding | 319 class LessThanBuilding |
352 { | 320 { |
353 public: | 321 public: |
354 bool operator () (Building const &b1, Building const &b2) | 322 bool operator () (Building const &b1, Building const &b2) |
355 { | 323 { |
356 return b1.x_[LEFT] < b2.x_[LEFT] | 324 return Building::less (b1, b2); |
357 || (b1.x_[LEFT] == b2.x_[LEFT] | |
358 && b1.height (b1.x_[LEFT]) > b2.height (b1.x_[LEFT])); | |
359 } | 325 } |
360 }; | 326 }; |
361 | 327 |
362 /** | 328 /** |
363 BUILDINGS is a list of buildings, but they could be overlapping | 329 BUILDINGS is a list of buildings, but they could be overlapping |
364 and in any order. The returned list of buildings is ordered and non-overlapp ing. | 330 and in any order. The returned list of buildings is ordered and non-overlapp ing. |
331 BUILDING is mutated, for efficiency reasons.. | |
365 */ | 332 */ |
366 list<Building> | 333 static vector<Building> |
367 Skyline::internal_build_skyline (list<Building> *buildings) const | 334 internal_build_skyline (vector<Building> *buildings) |
368 { | 335 { |
369 vsize size = buildings->size (); | 336 vsize size = buildings->size (); |
370 | 337 |
371 if (size == 0) | 338 if (size == 0) |
372 { | 339 { |
373 list<Building> result; | 340 vector<Building> result; |
374 empty_skyline (&result); | |
375 return result; | 341 return result; |
376 } | 342 } |
377 else if (size == 1) | 343 else if (size == 1) |
378 { | 344 { |
379 list<Building> result; | 345 return *buildings; |
380 single_skyline (buildings->front (), &result); | 346 } |
381 return result; | 347 |
382 } | 348 deque<vector<Building>> partials; |
383 | 349 |
384 deque<list<Building> > partials; | 350 sort (buildings->begin (), buildings->end (), LessThanBuilding ()); |
385 buildings->sort (LessThanBuilding ()); | |
386 while (!buildings->empty ()) | 351 while (!buildings->empty ()) |
387 partials.push_back (non_overlapping_skyline (buildings)); | 352 { |
353 vector<Building> trimmed, partial; | |
354 non_overlapping_skyline (*buildings, &trimmed, &partial); | |
355 partials.push_back (partial); | |
356 std::swap (*buildings, trimmed); | |
357 } | |
388 | 358 |
389 /* we'd like to say while (partials->size () > 1) but that's O (n). | 359 /* we'd like to say while (partials->size () > 1) but that's O (n). |
390 Instead, we exit in the middle of the loop */ | 360 Instead, we exit in the middle of the loop */ |
391 while (!partials.empty ()) | 361 while (!partials.empty ()) |
392 { | 362 { |
393 list<Building> merged; | 363 vector<Building> one = partials.front (); |
394 list<Building> one = partials.front (); | |
395 partials.pop_front (); | 364 partials.pop_front (); |
396 if (partials.empty ()) | 365 if (partials.empty ()) |
397 return one; | 366 return one; |
398 | 367 |
399 list<Building> two = partials.front (); | 368 vector<Building> two = partials.front (); |
400 partials.pop_front (); | 369 partials.pop_front (); |
401 internal_merge_skyline (&one, &two, &merged); | 370 vector<Building> merged = internal_merge_skylines (one, two); |
402 partials.push_back (merged); | 371 partials.push_back (merged); |
403 } | 372 } |
404 assert (0); | 373 assert (0); |
405 return list<Building> (); | 374 return vector<Building> (); |
406 } | 375 } |
407 | 376 |
408 Skyline::Skyline () | 377 Skyline::Skyline (vector<Building> const &bs, Direction sky) : buildings_ (bs) |
409 { | |
410 sky_ = UP; | |
411 empty_skyline (&buildings_); | |
412 } | |
413 | |
414 Skyline::Skyline (Direction sky) | |
415 { | 378 { |
416 sky_ = sky; | 379 sky_ = sky; |
417 empty_skyline (&buildings_); | 380 } |
418 } | 381 |
382 Skyline::Skyline () { sky_ = UP; } | |
383 | |
384 Skyline::Skyline (Direction sky) { sky_ = sky; } | |
419 | 385 |
420 /* | 386 /* |
421 Build skyline from a set of boxes. | 387 Build skyline from a set of boxes. |
422 | 388 |
423 Boxes should be non-empty on both axes. Otherwise, they will be ignored | 389 Boxes should be non-empty on both axes. Otherwise, they will be ignored |
424 */ | 390 */ |
425 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) | 391 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) |
426 { | 392 { |
427 list<Building> buildings; | 393 vector<Building> buildings; |
394 buildings.reserve (boxes.size ()); | |
428 sky_ = sky; | 395 sky_ = sky; |
429 | 396 |
430 for (vsize i = 0; i < boxes.size (); i++) | 397 for (Box b : boxes) |
431 if (!boxes[i].is_empty (X_AXIS) | 398 if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS)) |
432 && !boxes[i].is_empty (Y_AXIS)) | 399 { |
433 buildings.push_front (Building (boxes[i], horizon_axis, sky)); | 400 buildings.push_back (Building (b, horizon_axis, sky)); |
434 | 401 } |
435 buildings_ = internal_build_skyline (&buildings); | 402 buildings_ = internal_build_skyline (&buildings); |
436 normalize (); | |
437 } | 403 } |
438 | 404 |
439 /* | 405 void |
440 build skyline from a set of line segments. | 406 print_buildings (vector<Building> const &bs, Direction sky) |
407 { | |
408 for (auto const &b : bs) | |
409 { | |
410 printf ("%f,%f -> %f,%f\n", b.start (), sky * b.y (), b.end (), | |
411 sky * b.p2 ()[Y_AXIS]); | |
412 } | |
413 } | |
441 | 414 |
442 Segments can be articulated from left to right or right to left. | 415 void |
443 In the case of the latter, they will be stored internally as left to right. | 416 Skyline::print () const |
444 */ | 417 { |
418 print_buildings (buildings_, sky_); | |
419 } | |
420 | |
445 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis , Direction sky) | 421 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis , Direction sky) |
446 { | 422 { |
447 list<Building> buildings; | 423 vector<Building> buildings; |
424 buildings.reserve (segments.size ()); | |
448 sky_ = sky; | 425 sky_ = sky; |
449 | 426 |
450 for (vsize i = 0; i < segments.size (); i++) | 427 for (Drul_array<Offset> const &seg : segments) |
451 { | 428 { |
452 Drul_array<Offset> const &seg = segments[i]; | |
453 Offset left = seg[LEFT]; | 429 Offset left = seg[LEFT]; |
454 Offset right = seg[RIGHT]; | 430 Offset right = seg[RIGHT]; |
455 if (left[horizon_axis] > right[horizon_axis]) | 431 if (left[horizon_axis] > right[horizon_axis]) |
456 std::swap (left, right); | 432 std::swap (left, right); |
457 | 433 |
458 Real x1 = left[horizon_axis]; | 434 Real x1 = left[horizon_axis]; |
459 Real x2 = right[horizon_axis]; | 435 Real x2 = right[horizon_axis]; |
460 Real y1 = left[other_axis (horizon_axis)] * sky; | 436 if (x1 < x2) |
461 Real y2 = right[other_axis (horizon_axis)] * sky; | 437 { |
462 | 438 Real y1 = left[other_axis (horizon_axis)] * sky; |
463 if (x1 <= x2) | 439 Real y2 = right[other_axis (horizon_axis)] * sky; |
464 buildings.push_back (Building (x1, y1, y2, x2)); | 440 buildings.push_back (Building (Offset (x1, y1), Offset (x2, y2))); |
441 } | |
465 } | 442 } |
466 | 443 |
467 buildings_ = internal_build_skyline (&buildings); | 444 buildings_ = internal_build_skyline (&buildings); |
468 normalize (); | |
469 } | 445 } |
470 | 446 |
471 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) | 447 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) |
472 { | 448 { |
473 sky_ = sky; | 449 sky_ = sky; |
474 | 450 |
475 deque<Skyline> partials; | 451 deque<Skyline> partials; |
476 for (vsize i = 0; i < skypairs.size (); i++) | 452 for (Skyline_pair const &sk : skypairs) |
477 partials.push_back (Skyline ((skypairs[i])[sky])); | 453 { |
454 partials.push_back (sk[sky]); | |
455 } | |
478 | 456 |
479 while (partials.size () > 1) | 457 while (partials.size () > 1) |
480 { | 458 { |
481 Skyline one = partials.front (); | 459 Skyline one = partials.front (); |
482 partials.pop_front (); | 460 partials.pop_front (); |
483 Skyline two = partials.front (); | 461 Skyline two = partials.front (); |
484 partials.pop_front (); | 462 partials.pop_front (); |
485 | 463 |
486 one.merge (two); | 464 one.merge (two); |
487 partials.push_back (one); | 465 partials.push_back (one); |
488 } | 466 } |
489 | 467 |
490 if (partials.size ()) | 468 if (partials.size ()) |
491 buildings_.swap (partials.front ().buildings_); | 469 buildings_.swap (partials.front ().buildings_); |
492 else | 470 else |
493 buildings_.clear (); | 471 buildings_.clear (); |
494 } | 472 } |
495 | 473 |
496 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) | 474 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) |
497 { | 475 { |
498 sky_ = sky; | 476 sky_ = sky; |
499 if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS)) | 477 buildings_.push_back (Building (b, horizon_axis, sky)); |
500 { | |
501 Building front (b, horizon_axis, sky); | |
502 single_skyline (front, &buildings_); | |
503 normalize (); | |
504 } | |
505 } | 478 } |
506 | 479 |
507 void | 480 void |
508 Skyline::merge (Skyline const &other) | 481 Skyline::merge (Skyline const &other) |
509 { | 482 { |
510 assert (sky_ == other.sky_); | 483 assert (sky_ == other.sky_); |
511 | 484 |
512 if (other.is_empty ()) | 485 buildings_ = internal_merge_skylines (buildings_, other.buildings_); |
513 return; | |
514 | |
515 if (is_empty ()) | |
516 { | |
517 buildings_ = other.buildings_; | |
518 return; | |
519 } | |
520 | |
521 list<Building> other_bld (other.buildings_); | |
522 list<Building> my_bld; | |
523 my_bld.splice (my_bld.begin (), buildings_); | |
524 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | |
525 normalize (); | |
526 } | 486 } |
527 | 487 |
528 void | 488 void |
529 Skyline::insert (Box const &b, Axis a) | 489 Skyline::insert (Box const &b, Axis a) |
530 { | 490 { |
531 list<Building> other_bld; | |
532 list<Building> my_bld; | |
533 | |
534 if (std::isnan (b[other_axis (a)][LEFT]) | 491 if (std::isnan (b[other_axis (a)][LEFT]) |
535 || std::isnan (b[other_axis (a)][RIGHT])) | 492 || std::isnan (b[other_axis (a)][RIGHT])) |
536 { | 493 { |
537 programming_error ("insane box for skyline"); | 494 programming_error ("insane box for skyline"); |
538 return; | 495 return; |
539 } | 496 } |
540 | 497 |
541 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ | 498 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ |
542 if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS)) | 499 if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS)) |
543 return; | 500 return; |
544 | 501 |
545 my_bld.splice (my_bld.begin (), buildings_); | 502 vector<Building> other{Building (b, a, sky_)}; |
546 single_skyline (Building (b, a, sky_), &other_bld); | 503 buildings_ = internal_merge_skylines (other, buildings_); |
547 internal_merge_skyline (&other_bld, &my_bld, &buildings_); | |
548 normalize (); | |
549 } | 504 } |
550 | 505 |
551 void | 506 void |
552 Skyline::raise (Real r) | 507 Skyline::raise (Real r) |
553 { | 508 { |
554 list<Building>::iterator end = buildings_.end (); | 509 for (auto &b : buildings_) |
555 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | 510 { |
556 i->y_intercept_ += sky_ * r; | 511 b.raise (sky_ * r); |
512 } | |
557 } | 513 } |
558 | 514 |
559 void | 515 void |
560 Skyline::shift (Real s) | 516 Skyline::shift (Real s) |
561 { | 517 { |
562 list<Building>::iterator end = buildings_.end (); | 518 for (auto &b : buildings_) |
563 for (list<Building>::iterator i = buildings_.begin (); i != end; i++) | |
564 { | 519 { |
565 i->x_[LEFT] += s; | 520 b.horizontal_shift (s); |
566 i->x_[RIGHT] += s; | |
567 i->y_intercept_ -= s * i->slope_; | |
568 } | 521 } |
569 } | 522 } |
570 | 523 |
571 Real | 524 Real |
572 Skyline::distance (Skyline const &other, Real horizon_padding) const | 525 Skyline::distance (Skyline const &other, Real horizon_padding) const |
573 { | 526 { |
574 Real dummy; | 527 Real dummy; |
575 return internal_distance (other, horizon_padding, &dummy); | 528 return internal_distance (other, horizon_padding, &dummy); |
576 } | 529 } |
577 | 530 |
(...skipping 10 matching lines...) Expand all Loading... | |
588 { | 541 { |
589 if (horizon_padding == 0.0) | 542 if (horizon_padding == 0.0) |
590 return internal_distance (other, touch_point); | 543 return internal_distance (other, touch_point); |
591 | 544 |
592 // Note that it is not necessary to build a padded version of other, | 545 // Note that it is not necessary to build a padded version of other, |
593 // because the same effect can be achieved just by doubling horizon_padding. | 546 // because the same effect can be achieved just by doubling horizon_padding. |
594 Skyline padded_this = padded (horizon_padding); | 547 Skyline padded_this = padded (horizon_padding); |
595 return padded_this.internal_distance (other, touch_point); | 548 return padded_this.internal_distance (other, touch_point); |
596 } | 549 } |
597 | 550 |
551 static vector<Building> | |
552 padded_skyline (const vector<Building> &input, Real padding) | |
553 { | |
554 vector<Building> pads; | |
555 pads.reserve (4 * input.size ()); | |
556 for (auto const &b : input) | |
557 { | |
558 if (!isinf (b[LEFT])) | |
559 { | |
560 pads.push_back (Building (b.p1 () + padding * Offset (-2, -1), | |
561 b.p1 () + padding * Offset (-1, 0))); | |
562 pads.push_back ( | |
563 Building (b.p1 () + padding * Offset (-1, 0), b.p1 ())); | |
564 } | |
565 | |
566 if (!isinf (b[RIGHT])) | |
567 { | |
568 pads.push_back ( | |
569 Building (b.p2 (), b.p2 () + padding * Offset (1, 0))); | |
570 pads.push_back (Building (b.p2 () + padding * Offset (1, 0), | |
571 b.p2 () + padding * Offset (2, -1))); | |
572 } | |
573 } | |
574 | |
575 // The buildings may be overlapping, so resolve that. | |
576 vector<Building> pad_skyline = internal_build_skyline (&pads); | |
577 | |
578 // Merge with original | |
579 return internal_merge_skylines (pad_skyline, input); | |
580 } | |
581 | |
598 Skyline | 582 Skyline |
599 Skyline::padded (Real horizon_padding) const | 583 Skyline::padded (Real horizon_padding) const |
600 { | 584 { |
601 if (horizon_padding < 0.0) | 585 if (horizon_padding < 0.0) |
602 warning ("Cannot have negative horizon padding. Junking."); | 586 warning ("Cannot have negative horizon padding. Junking."); |
603 | 587 |
604 if (horizon_padding <= 0.0) | 588 if (horizon_padding <= 0.0) |
605 return *this; | 589 return *this; |
606 | 590 |
607 list<Building> pad_buildings; | 591 return Skyline (padded_skyline (buildings_, horizon_padding), sky_); |
608 for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.e nd (); ++i) | 592 } |
593 | |
594 Real | |
595 skyline_internal_distance (vector<Building> const &bs1, | |
596 vector<Building> const &bs2, Real *touch_point) | |
597 { | |
598 Real max_dist = -infinity_f; | |
599 Real max_x = -infinity_f; | |
600 if (bs1.empty () || bs2.empty ()) | |
609 { | 601 { |
610 if (i->x_[LEFT] > -infinity_f) | 602 *touch_point = max_x; |
603 return max_dist; | |
604 } | |
605 | |
606 BuildingQueue bq1 (bs1); | |
607 BuildingQueue bq2 (bs2); | |
608 | |
609 while (bq1.ok () && bq2.ok ()) | |
610 { | |
611 BuildingQueue *first = &bq1; | |
612 BuildingQueue *second = &bq2; | |
613 | |
614 if (second->start () < first->start ()) | |
611 { | 615 { |
612 Real height = i->height (i->x_[LEFT]); | 616 std::swap (first, second); |
613 if (height > -infinity_f) | |
614 { | |
615 // Add the sloped building that pads the left side of the current building. | |
616 Real start = i->x_[LEFT] - 2 * horizon_padding; | |
617 Real end = i->x_[LEFT] - horizon_padding; | |
618 pad_buildings.push_back (Building (start, height - horizon_padding , height, end)); | |
619 | |
620 // Add the flat building that pads the left side of the current bu ilding. | |
621 start = i->x_[LEFT] - horizon_padding; | |
622 end = i->x_[LEFT]; | |
623 pad_buildings.push_back (Building (start, height, height, end)); | |
624 } | |
625 } | 617 } |
626 | 618 |
627 if (i->x_[RIGHT] < infinity_f) | 619 if (second->start () > first->end ()) |
628 { | 620 { |
629 Real height = i->height (i->x_[RIGHT]); | 621 // No overlap. |
630 if (height > -infinity_f) | 622 first->next (); |
623 continue; | |
624 } | |
625 | |
626 // second->start <= first.end , so we have some overlap. | |
627 Real d = first->height_at (second->start ()) + second->y (); | |
628 if (d > max_dist) | |
629 { | |
630 max_dist = d; | |
631 max_x = second->start (); | |
632 } | |
633 | |
634 if (first->end () >= second->end ()) | |
635 { | |
636 // second is completely contained in the first. | |
637 Real x = second->end (); | |
638 Real d = second->height_at (x) + first->height_at (x); | |
639 if (d > max_dist) | |
631 { | 640 { |
632 // Add the flat building that pads the right side of the current b uilding. | 641 max_dist = d; |
633 Real start = i->x_[RIGHT]; | 642 max_x = x; |
634 Real end = start + horizon_padding; | 643 } |
635 pad_buildings.push_back (Building (start, height, height, end)); | |
636 | 644 |
637 // Add the sloped building that pads the right side of the current building. | 645 second->next (); |
638 start = end; | 646 continue; |
639 end += horizon_padding; | 647 } |
640 pad_buildings.push_back (Building (start, height, height - horizon _padding, end)); | 648 else |
649 { | |
650 // first->end < second->end | |
651 Real x = first->end (); | |
652 Real d = second->height_at (x) + first->height_at (x); | |
653 if (d > max_dist) | |
654 { | |
655 max_dist = d; | |
656 max_x = x; | |
641 } | 657 } |
658 | |
659 first->next (); | |
660 continue; | |
642 } | 661 } |
643 } | 662 } |
644 | 663 |
645 // The buildings may be overlapping, so resolve that. | 664 *touch_point = max_x; |
646 list<Building> pad_skyline = internal_build_skyline (&pad_buildings); | 665 return max_dist; |
647 | |
648 // Merge the padding with the original, to make a new skyline. | |
649 Skyline padded (sky_); | |
650 list<Building> my_buildings = buildings_; | |
651 padded.buildings_.clear (); | |
652 internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); | |
653 padded.normalize (); | |
654 | |
655 return padded; | |
656 } | 666 } |
657 | 667 |
658 Real | 668 Real |
659 Skyline::internal_distance (Skyline const &other, Real *touch_point) const | 669 Skyline::internal_distance (Skyline const &other, Real *touch_point) const |
660 { | 670 { |
661 assert (sky_ == -other.sky_); | 671 assert (sky_ == -other.sky_); |
662 | 672 return skyline_internal_distance (buildings_, other.buildings_, touch_point); |
663 list<Building>::const_iterator i = buildings_.begin (); | |
664 list<Building>::const_iterator j = other.buildings_.begin (); | |
665 | |
666 Real dist = -infinity_f; | |
667 Real start = -infinity_f; | |
668 Real touch = -infinity_f; | |
669 while (i != buildings_.end () && j != other.buildings_.end ()) | |
670 { | |
671 Real end = std::min (i->x_[RIGHT], j->x_[RIGHT]); | |
672 Real start_dist = i->height (start) + j->height (start); | |
673 Real end_dist = i->height (end) + j->height (end); | |
674 dist = std::max (dist, std::max (start_dist, end_dist)); | |
675 | |
676 if (end_dist == dist) | |
677 touch = end; | |
678 else if (start_dist == dist) | |
679 touch = start; | |
680 | |
681 if (i->x_[RIGHT] <= j->x_[RIGHT]) | |
682 i++; | |
683 else | |
684 j++; | |
685 start = end; | |
686 } | |
687 | |
688 *touch_point = touch; | |
689 return dist; | |
690 } | 673 } |
691 | 674 |
692 Real | 675 Real |
693 Skyline::height (Real airplane) const | 676 Skyline::height (Real x) const |
694 { | 677 { |
695 assert (!std::isinf (airplane)); | 678 assert (!std::isinf (x)); |
696 | 679 |
697 list<Building>::const_iterator i; | 680 // TODO - use binary search |
698 for (i = buildings_.begin (); i != buildings_.end (); i++) | 681 for (Building const &b : buildings_) |
699 { | 682 { |
700 if (i->x_[RIGHT] >= airplane) | 683 if (b[RIGHT] >= x) |
701 return sky_ * i->height (airplane); | 684 { |
685 if (b[LEFT] < x) | |
686 return sky_ * b.height_at (x); | |
687 | |
688 return -sky_ * infinity_f; | |
689 } | |
702 } | 690 } |
703 | 691 |
704 assert (0); | 692 assert (0); |
705 return 0; | 693 return 0; |
706 } | 694 } |
707 | 695 |
708 Real | 696 Real |
709 Skyline::max_height () const | 697 Skyline::max_height () const |
710 { | 698 { |
711 Real ret = -infinity_f; | 699 Real ret = -infinity_f; |
712 | 700 |
713 list<Building>::const_iterator i; | 701 vector<Building>::const_iterator i; |
714 for (i = buildings_.begin (); i != buildings_.end (); ++i) | 702 for (Building const &b : buildings_) |
715 { | 703 { |
716 ret = std::max (ret, i->height (i->x_[LEFT])); | 704 ret = std::max (ret, b.y ()); |
717 ret = std::max (ret, i->height (i->x_[RIGHT])); | 705 ret = std::max (ret, b.height_at (b[RIGHT])); |
718 } | 706 } |
719 | 707 |
720 return sky_ * ret; | 708 return sky_ * ret; |
721 } | 709 } |
722 | 710 |
723 Direction | 711 Direction |
724 Skyline::direction () const | 712 Skyline::direction () const |
725 { | 713 { |
726 return sky_; | 714 return sky_; |
727 } | 715 } |
728 | 716 |
717 // X of first building in skyline | |
729 Real | 718 Real |
730 Skyline::left () const | 719 Skyline::left () const |
731 { | 720 { |
732 for (list<Building>::const_iterator i (buildings_.begin ()); | 721 if (buildings_.empty ()) |
733 i != buildings_.end (); i++) | 722 return infinity_f; |
734 if (i->y_intercept_ > -infinity_f) | 723 |
735 return i->x_[LEFT]; | 724 return buildings_[0][LEFT]; |
736 | 725 } |
737 return infinity_f; | 726 |
738 } | 727 // X of end of last building in skyline |
739 | |
740 Real | 728 Real |
741 Skyline::right () const | 729 Skyline::right () const |
742 { | 730 { |
743 for (list<Building>::const_reverse_iterator i (buildings_.rbegin ()); | 731 if (buildings_.empty ()) |
744 i != buildings_.rend (); ++i) | 732 return -infinity_f; |
745 if (i->y_intercept_ > -infinity_f) | 733 |
746 return i->x_[RIGHT]; | 734 return buildings_.back ()[RIGHT]; |
747 | |
748 return -infinity_f; | |
749 } | 735 } |
750 | 736 |
751 Real | 737 Real |
752 Skyline::max_height_position () const | 738 Skyline::max_height_position () const |
753 { | 739 { |
754 Skyline s (-sky_); | 740 Real max = -infinity_f; |
755 s.set_minimum_height (0); | 741 Real xmax = -infinity_f; |
756 return touching_point (s); | 742 for (auto const &b : buildings_) |
743 { | |
744 if (b.y () > max) | |
745 { | |
746 max = b.y (); | |
747 xmax = b[LEFT]; | |
748 } | |
749 | |
750 Real h = b.height_at (b[RIGHT]); | |
751 if (h > max) | |
752 { | |
753 max = h; | |
754 xmax = b[RIGHT]; | |
755 } | |
756 } | |
757 | |
758 return xmax; | |
757 } | 759 } |
758 | 760 |
759 void | 761 void |
760 Skyline::set_minimum_height (Real h) | 762 Skyline::set_minimum_height (Real h) |
761 { | 763 { |
762 Skyline s (sky_); | 764 if (h == -sky_ * infinity_f) |
763 s.buildings_.front ().y_intercept_ = h * sky_; | 765 { |
766 return; | |
767 } | |
768 | |
769 assert (!isinf (h)); | |
770 Box b; | |
771 b[X_AXIS].set_full (); | |
772 b[Y_AXIS].set_full (); | |
773 b[Y_AXIS][sky_] = h; | |
774 | |
775 Skyline s (b, X_AXIS, sky_); | |
764 merge (s); | 776 merge (s); |
765 } | 777 } |
766 | 778 |
767 vector<Offset> | 779 vector<Drul_array<Offset>> |
768 Skyline::to_points (Axis horizon_axis) const | 780 Skyline::to_segments (Axis horizon_axis) const |
hahnjo
2020/04/24 16:33:04
What's the advantage of this code over the old met
hanwenn
2020/04/24 17:12:48
the buildings making up the skylines have become n
| |
769 { | 781 { |
770 vector<Offset> out; | 782 vector<Drul_array<Offset>> out; |
771 | 783 out.reserve (2 * buildings_.size ()); |
772 Real start = -infinity_f; | 784 |
773 for (list<Building>::const_iterator i (buildings_.begin ()); | 785 for (auto const &b : buildings_) |
774 i != buildings_.end (); i++) | |
775 { | 786 { |
776 out.push_back (Offset (start, sky_ * i->height (start))); | 787 Offset p1 = b.p1 (); |
777 out.push_back (Offset (i->x_[RIGHT], sky_ * i->height (i->x_[RIGHT]))); | 788 Offset p2 = b.p2 (); |
778 start = i->x_[RIGHT]; | 789 if (sky_ == DOWN) |
790 { | |
791 p1.mirror (Y_AXIS); | |
792 p2.mirror (Y_AXIS); | |
793 } | |
794 if (horizon_axis == Y_AXIS) | |
795 { | |
796 p1 = p1.swapped (); | |
797 p2 = p2.swapped (); | |
798 } | |
799 out.push_back (Drul_array<Offset> (p1, p2)); | |
779 } | 800 } |
780 | 801 |
781 if (horizon_axis == Y_AXIS) | |
782 for (vsize i = 0; i < out.size (); i++) | |
783 out[i] = out[i].swapped (); | |
784 | |
785 return out; | 802 return out; |
786 } | 803 } |
787 | 804 |
788 bool | 805 bool |
789 Skyline::is_empty () const | 806 Skyline::is_empty () const |
790 { | 807 { |
791 if (!buildings_.size ()) | 808 return buildings_.empty (); |
792 return true; | |
793 Building b = buildings_.front (); | |
794 return b.x_[RIGHT] == infinity_f && b.y_intercept_ == -infinity_f; | |
795 } | 809 } |
796 | 810 |
797 void | 811 void |
798 Skyline::clear () | 812 Skyline::clear () |
799 { | 813 { |
800 buildings_.clear (); | 814 buildings_.clear (); |
801 empty_skyline (&buildings_); | 815 } |
802 } | 816 |
803 | 817 ///////////////// |
804 /****************************************************************/ | 818 // testing |
819 | |
820 LY_DEFINE (ly_unittest_skyline, "ly:unittest-skyline", 0, 0, 0, (), | |
821 "unittest skyline code.") | |
822 { | |
823 { | |
824 Building b (Offset (0, 1), Offset (10, 1)); | |
825 Real x; | |
826 assert (b.intersect (Building (Offset (3, 0), Offset (7, 2)), &x)); | |
827 assert (x == 5); | |
828 } | |
829 { | |
830 Building b (Offset (1, 1), Offset (2, 2)); | |
831 assert ((b.p2 () - Offset (2, 2)).length () < 1e-10); | |
832 } | |
833 { | |
834 vector<Building> bs1{Building (Offset (0, 0), Offset (3, 3))}; | |
835 vector<Building> bs2{Building (Offset (4, 3), Offset (7, 0))}; | |
836 Real x; | |
837 Real d = skyline_internal_distance (bs1, bs2, &x); | |
838 assert (d == -infinity_f); | |
839 } | |
840 { | |
841 vector<Building> bs1{Building (Offset (0, 1), Offset (3, 1))}; | |
842 vector<Building> bs2{Building (Offset (0, 1), Offset (2, 1))}; | |
843 vector<Building> res = internal_merge_skylines (bs1, bs2); | |
844 vector<Building> want{ | |
845 Building (Offset (0, 1), Offset (3, 1)), | |
846 }; | |
847 assert (res.size () == want.size ()); | |
848 for (vsize i = 0; i < want.size (); i++) | |
849 { | |
850 assert (want[i].equal (res[i])); | |
851 } | |
852 } | |
853 { | |
854 vector<Building> bs1{ | |
855 Building (Offset (-infinity_f, 1), Offset (infinity_f, 1))}; | |
856 vector<Building> bs2{ | |
857 Building (Offset (0, 0), Offset (2, 2)), | |
858 Building (Offset (2, 2), Offset (4, 0)), | |
859 }; | |
860 vector<Building> res = internal_merge_skylines (bs1, bs2); | |
861 vector<Building> want{ | |
862 Building (Offset (-infinity_f, 1), Offset (1, 1)), | |
863 Building (Offset (1, 1), Offset (2, 2)), | |
864 Building (Offset (2, 2), Offset (3, 1)), | |
865 Building (Offset (3, 1), Offset (infinity_f, 1)), | |
866 }; | |
867 assert (res.size () == want.size ()); | |
868 for (vsize i = 0; i < want.size (); i++) | |
869 { | |
870 assert (want[i].equal (res[i])); | |
871 } | |
872 } | |
873 { | |
874 vector<Building> bs1{Building (Offset (0, 1), Offset (3, 1))}; | |
875 vector<Building> bs2{Building (Offset (1, 2), Offset (2, 2))}; | |
876 vector<Building> res = internal_merge_skylines (bs1, bs2); | |
877 vector<Building> want{ | |
878 Building (Offset (0, 1), Offset (1, 1)), | |
879 Building (Offset (1, 2), Offset (2, 2)), | |
880 Building (Offset (2, 1), Offset (3, 1)), | |
881 }; | |
882 assert (res.size () == want.size ()); | |
883 for (vsize i = 0; i < want.size (); i++) | |
884 { | |
885 assert (want[i].equal (res[i])); | |
886 } | |
887 } | |
888 { | |
889 vector<Building> bs1{Building (Offset (0, 1), Offset (10, 1))}; | |
890 vector<Building> bs2{ | |
891 Building (Offset (1, 0), Offset (3, 2)), | |
892 }; | |
893 vector<Building> res = internal_merge_skylines (bs1, bs2); | |
894 vector<Building> want{ | |
895 Building (Offset (0, 1), Offset (2, 1)), | |
896 Building (Offset (2, 1), Offset (3, 2)), | |
897 Building (Offset (3, 1), Offset (10, 1)), | |
898 }; | |
899 assert (res.size () == want.size ()); | |
900 for (vsize i = 0; i < want.size (); i++) | |
901 { | |
902 assert (want[i].equal (res[i])); | |
903 } | |
904 } | |
905 { | |
906 vector<Building> bs1{Building (Offset (0, 1), Offset (10, 1))}; | |
907 vector<Building> bs2{ | |
908 Building (Offset (1, 0), Offset (3, 2)), | |
909 Building (Offset (4, 3), Offset (5, 3)), | |
910 Building (Offset (5, 3), Offset (8, 0)), | |
911 }; | |
912 vector<Building> res = internal_merge_skylines (bs1, bs2); | |
913 vector<Building> want{ | |
914 Building (Offset (0, 1), Offset (2, 1)), | |
915 Building (Offset (2, 1), Offset (3, 2)), | |
916 Building (Offset (3, 1), Offset (4, 1)), | |
917 Building (Offset (4, 3), Offset (5, 3)), | |
918 Building (Offset (5, 3), Offset (7, 1)), | |
919 Building (Offset (7, 1), Offset (10, 1)), | |
920 }; | |
921 assert (res.size () == want.size ()); | |
922 for (vsize i = 0; i < want.size (); i++) | |
923 { | |
924 assert (want[i].equal (res[i])); | |
925 } | |
926 } | |
927 | |
928 return SCM_EOL; | |
929 } | |
805 | 930 |
806 const char *const Skyline::type_p_name_ = "ly:skyline?"; | 931 const char *const Skyline::type_p_name_ = "ly:skyline?"; |
807 | 932 |
808 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "") | 933 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "") |
809 SCM | 934 SCM |
810 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon _padding_scm) | 935 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon _padding_scm) |
811 { | 936 { |
812 LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1); | 937 LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1); |
813 | 938 |
814 Real horizon_padding = 0; | 939 Real horizon_padding = 0; |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
861 { | 986 { |
862 Real x = robust_scm2double (x_scm, 0.0); | 987 Real x = robust_scm2double (x_scm, 0.0); |
863 return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x)); | 988 return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x)); |
864 } | 989 } |
865 | 990 |
866 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", | 991 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?", |
867 1, 0, 0, (SCM sky), | 992 1, 0, 0, (SCM sky), |
868 "Return whether @var{sky} is empty.") | 993 "Return whether @var{sky} is empty.") |
869 { | 994 { |
870 Skyline *s = unsmob<Skyline> (sky); | 995 Skyline *s = unsmob<Skyline> (sky); |
996 | |
871 LY_ASSERT_SMOB (Skyline, sky, 1); | 997 LY_ASSERT_SMOB (Skyline, sky, 1); |
872 return scm_from_bool (s->is_empty ()); | 998 return scm_from_bool (s->is_empty ()); |
873 } | 999 } |
OLD | NEW |