+static void
+single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret)
+{
+ bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_);
+ if (!isinf (b.end_))
+ ret->push_front (Building (b.end_ + horizon_padding, -infinity_f,
+ -infinity_f, infinity_f));
+ if (sloped_neighbours)
+ ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT));
+
+ if (b.end_ > start + EPS)
+ ret->push_front (b);
+
+ if (sloped_neighbours)
+ ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT));
+
+ if (!isinf (start))
+ ret->push_front (Building (-infinity_f, -infinity_f,
+ -infinity_f, start - horizon_padding));
+}
+
+/* remove a non-overlapping set of boxes from BOXES and build a skyline
+ out of them */
+static list<Building>
+non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ list<Building> result;
+ Real last_end = -infinity_f;
+ list<Box>::iterator i = boxes->begin ();
+ while (i != boxes->end ())
+ {
+ Interval iv = (*i)[horizon_axis];
+
+ if (iv[LEFT] - horizon_padding < last_end)
+ {
+ i++;
+ continue;
+ }
+
+ if (iv[LEFT] - horizon_padding > last_end + EPS)
+ result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - 2*horizon_padding));
+
+ Building b (*i, horizon_padding, horizon_axis, sky);
+ bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ());
+ if (sloped_neighbours)
+ result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT));
+ result.push_front (b);
+ if (sloped_neighbours)
+ result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT));
+
+ list<Box>::iterator j = i++;
+ boxes->erase (j);
+ last_end = result.front ().end_;
+ }
+ if (last_end < infinity_f)
+ result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f));
+ result.reverse ();
+ return result;
+}
+
+class LessThanBox
+{
+ Axis a_;
+
+public:
+ LessThanBox (Axis a)
+ {
+ a_ = a;
+ }
+
+ bool operator() (Box const &b1, Box const &b2)
+ {
+ return b1[a_][LEFT] < b2[a_][LEFT];
+ }
+};
+
+list<Building>
+Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ vsize size = boxes->size ();
+
+ if (size == 0)
+ {
+ list<Building> result;
+ empty_skyline (&result);
+ return result;
+ }
+ else if (size == 1)
+ {
+ list<Building> result;
+ single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky),
+ boxes->front ()[horizon_axis][LEFT] - horizon_padding,
+ horizon_padding, &result);
+ return result;
+ }
+
+ deque<list<Building> > partials;
+ boxes->sort (LessThanBox (horizon_axis));
+ while (!boxes->empty ())
+ partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky));
+
+ /* we'd like to say while (partials->size () > 1) but that's O (n).
+ Instead, we exit in the middle of the loop */
+ while (!partials.empty ())
+ {
+ list<Building> merged;
+ list<Building> one = partials.front ();
+ partials.pop_front ();
+ if (partials.empty ())
+ return one;
+
+ list<Building> two = partials.front ();
+ partials.pop_front ();
+ internal_merge_skyline (&one, &two, &merged);
+ partials.push_back (merged);
+ }
+ assert (0);
+ return list<Building> ();
+}
+
+Skyline::Skyline ()