+/* 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)