source file of the GNU LilyPond music typesetter
- (c) 2006 Joe Neeman <joeneeman@gmail.com>
+ (c) 2006--2008 Joe Neeman <joeneeman@gmail.com>
*/
#include "skyline.hh"
+#include <deque>
-#include "line-interface.hh"
+#include "ly-smobs.icc"
/* A skyline is a sequence of non-overlapping buildings: something like
this:
_______
- / \ ________
- / \ ________/ \
- /\ / \ / \
- / -----/ \ / \
- / \ / \
- / ------------/ ----
+ | \ ________
+ | \ ________/ \
+ /\ | \ / \
+ / -------- \ / \
+ / \ / \
+ / ------------/ ----
--
Each building has a starting position, and ending position, a starting
height and an ending height.
but the distance routine does.
*/
-#define EPS 1e-10
+/* If we start including very thin buildings, numerical accuracy errors can
+ arise. Therefore, we ignore all buildings that are less than epsilon wide. */
+#define EPS 1e-5
-static inline bool
-equal (Real x, Real y)
+static void
+print_buildings (list<Building> const &b)
{
- return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
+ for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++)
+ i->print ();
}
-bool
-Skyline::is_legal_skyline () const
+void
+Skyline::print () const
{
- list<Building>::const_iterator i;
- Real last_x = -infinity_f;
- Real last_h = -infinity_f;
- for (i = buildings_.begin (); i != buildings_.end (); i++)
- {
- if (i->iv_[LEFT] != last_x)
- return false;
- if (i != buildings_.begin () && !equal (i->start_height_, last_h))
- return false;
- last_x = i->iv_[RIGHT];
- last_h = i->end_height_;
- }
- return last_x == infinity_f;
+ print_buildings (buildings_);
}
-Building::Building (Real start, Real start_height, Real end_height, Real end, Real max_slope)
- : iv_ (start, end)
+void
+Skyline::print_points () const
{
- start_height_ = start_height;
- end_height_ = end_height;
+ vector<Offset> ps (to_points (X_AXIS));
- if (isinf (start))
- assert (isinf (start_height) || start_height == end_height);
- if (isinf (end))
- assert (isinf (end_height) || start_height == end_height);
+ for (vsize i = 0; i < ps.size (); i++)
+ printf ("(%f,%f)%s" , ps[i][X_AXIS], ps[i][Y_AXIS],
+ (i%2)==1 ? "\n" : " ");
+}
+
+Building::Building (Real start, Real start_height, Real end_height, Real end)
+{
+ if (isinf (start) || isinf (end))
+ assert (start_height == end_height);
- m_ = (end_height - start_height) / (end - start);
- if (start_height == end_height)
- m_ = 0;
- if (isinf (m_) || isnan (m_))
- m_ = max_slope * (start_height < end_height ? 1 : -1);
- assert (abs (m_) <= max_slope);
+ end_ = end;
+ precompute (start, start_height, end_height, end);
+}
+
+Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ Real start = b[horizon_axis][LEFT] - horizon_padding;
+ Real end = b[horizon_axis][RIGHT] + horizon_padding;
+ Real height = sky * b[other_axis (horizon_axis)][sky];
+
+ end_ = end;
+ precompute (start, height, height, end);
+}
+
+void
+Building::precompute (Real start, Real start_height, Real end_height, Real end)
+{
+ slope_ = (end_height - start_height) / (end - start);
+ if (start_height == end_height) /* if they were both infinite, we would get nan, not 0, from the prev line */
+ slope_ = 0;
+
+ assert (!isinf (slope_) && !isnan (slope_));
if (isinf (start))
{
- if (isinf (end))
- b_ = start_height;
- else
- b_ = end_height - m_*end;
+ assert (start_height == end_height);
+ y_intercept_ = start_height;
}
else
- b_ = start_height - m_*start;
+ y_intercept_ = start_height - slope_ * start;
}
Real
Building::height (Real x) const
{
- if (isinf (x))
- return (x > 0) ? end_height_ : start_height_;
- return m_*x + b_;
+ return isinf (x) ? y_intercept_ : slope_*x + y_intercept_;
+}
+
+void
+Building::print () const
+{
+ printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_);
}
Real
-Building::intersection (Building const &other) const
+Building::intersection_x (Building const &other) const
{
- return (b_ - other.b_) / (other.m_ - m_);
+ Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
+ return isnan (ret) ? -infinity_f : ret;
}
void
-Building::leading_part (Real chop, Real h)
+Building::leading_part (Real chop)
{
- assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
- assert (equal (h, height (chop)));
- iv_[RIGHT] = chop;
- end_height_ = h;
+ assert (chop <= end_);
+ end_ = chop;
}
-static void
-skyline_trailing_part (list<Building> *sky, Real x)
+Building
+Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const
{
- if (equal (x, sky->front ().iv_[RIGHT]))
- sky->pop_front ();
- else
- assert (x < sky->front ().iv_[RIGHT]);
+ Real x = (d == LEFT) ? start : end_;
+ Real left = x;
+ Real right = x + d * horizon_padding;
+ Real left_height = height (x);
+ Real right_height = left_height - horizon_padding;
+ if (d == LEFT)
+ {
+ swap (left, right);
+ swap (left_height, right_height);
+ }
+ return Building (left, left_height, right_height, right);
+}
- if (!sky->empty ())
+static Real
+first_intersection (Building const &b, list<Building> *const s, Real start_x)
+{
+ while (!s->empty () && start_x < b.end_)
{
- sky->front ().iv_[LEFT] = x;
- sky->front ().start_height_ = sky->front ().height (x);
+ Building c = s->front ();
+ if (c.conceals (b, start_x))
+ return start_x;
+
+ Real i = b.intersection_x (c);
+ if (i > start_x && i <= b.end_ && i <= c.end_)
+ return i;
+
+ start_x = c.end_;
+ if (b.end_ > c.end_)
+ s->pop_front ();
}
+ return b.end_;
}
bool
-Building::obstructs (Building const &other) const
+Building::conceals (Building const &other, Real x) const
{
- if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
- return m_ > other.m_ || (m_ == other.m_ && b_ > other.b_);
- return start_height_ > other.start_height_;
+ if (slope_ == other.slope_)
+ return y_intercept_ > other.y_intercept_;
+
+ /* their slopes were not equal, so there is an intersection point */
+ Real i = intersection_x (other);
+ return (i <= x && slope_ > other.slope_)
+ || (i > x && slope_ < other.slope_);
}
void
Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
list<Building> *const result)
{
+ if (s1->empty () || s2->empty ())
+ {
+ programming_error ("tried to merge an empty skyline");
+ return;
+ }
+
+ Real x = -infinity_f;
while (!s1->empty ())
{
- if (s2->front ().obstructs (s1->front ()))
+ if (s2->front ().conceals (s1->front (), x))
swap (s1, s2);
Building b = s1->front ();
- while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
- && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]))
- s2->pop_front ();
-
- /* the front of s2 either intersects with b or it ends after b */
- Real end = infinity_f;
- if (s2->front ().end_height_ > b.height (s2->front ().iv_[RIGHT]))
- end = b.intersection (s2->front ());
- end = min (end, b.iv_[RIGHT]);
- Real height = b.height (end);
-
- b.leading_part (end, height);
- result->push_front (b);
-
- skyline_trailing_part (s1, end);
- if (!s1->empty ())
- s1->front ().start_height_ = height;
- skyline_trailing_part (s2, end);
+ Real end = first_intersection (b, s2, x);
+
+ if (s2->empty ())
+ {
+ result->push_front (b);
+ break;
+ }
+
+ /* only include buildings wider than epsilon */
+ if (end > x + EPS)
+ {
+ b.leading_part (end);
+ result->push_front (b);
+ }
+
+ if (end >= s1->front ().end_)
+ s1->pop_front ();
+
+ x = end;
}
result->reverse ();
}
static void
empty_skyline (list<Building> *const ret)
{
- ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
+ ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
}
static void
-single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
+single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret)
{
- if (!isinf (b.iv_[RIGHT]))
- ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
- ret->push_front (b);
- if (!isinf (b.iv_[LEFT]))
- ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
+ 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));
}
-void
-Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
+/* 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)
{
- vsize size = buildings->size ();
+ 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)
{
- empty_skyline (result);
- return;
+ list<Building> result;
+ empty_skyline (&result);
+ return result;
}
else if (size == 1)
{
- single_skyline (buildings->front (), result, max_slope_);
- return;
+ list<Building> result;
+ single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky),
+ boxes->front ()[horizon_axis][LEFT], horizon_axis, &result);
+ return result;
}
- list<Building> right_half;
- list<Building>::iterator i = buildings->begin ();
+ deque<list<Building> > partials;
+ boxes->sort (LessThanBox (horizon_axis));
+ while (!boxes->empty ())
+ partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky));
- for (vsize s = 0; s < size/2; s++)
- i++;
- right_half.splice (right_half.end (), *buildings, i, buildings->end ());
-
- list<Building> right;
- list<Building> left;
- internal_build_skyline (&right_half, &right);
- internal_build_skyline (buildings, &left);
- internal_merge_skyline (&right, &left, result);
+ /* 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 ()
{
- max_slope_ = 2;
sky_ = UP;
empty_skyline (&buildings_);
}
+Skyline::Skyline (Skyline const &src)
+{
+ sky_ = src.sky_;
+
+ /* doesn't a list's copy constructor do this? -- jneem */
+ for (list<Building>::const_iterator i = src.buildings_.begin ();
+ i != src.buildings_.end (); i++)
+ {
+ buildings_.push_back (Building ((*i)));
+ }
+}
+
Skyline::Skyline (Direction sky)
{
- max_slope_ = 2;
sky_ = sky;
empty_skyline (&buildings_);
}
-Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
+/*
+ build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
+ by that amount and add 45-degree sloped boxes to the edges of each box (of
+ width horizon_padding). That is, the total amount of horizontal expansion is
+ horizon_padding*4, half of which is sloped and half of which is flat.
+
+ Boxes should have fatness in the horizon_axis (after they are expanded by
+ horizon_padding), otherwise they are ignored.
+ */
+Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
{
- list<Building> bldgs;
+ list<Box> filtered_boxes;
sky_ = sky;
- max_slope_ = 2;
+ Axis vert_axis = other_axis (horizon_axis);
for (vsize i = 0; i < boxes.size (); i++)
{
- Interval iv = boxes[i][a];
- Real height = sky * boxes[i][other_axis (a)][sky];
- if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
- bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
+ Interval iv = boxes[i][horizon_axis];
+ iv.widen (horizon_padding);
+ if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
+ filtered_boxes.push_front (boxes[i]);
}
- internal_build_skyline (&bldgs, &buildings_);
- assert (is_legal_skyline ());
+
+ buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky);
+}
+
+Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ sky_ = sky;
+ Building front (b, horizon_padding, horizon_axis, sky);
+ single_skyline (front, b[horizon_axis][LEFT], horizon_padding, &buildings_);
}
void
list<Building> my_bld;
my_bld.splice (my_bld.begin (), buildings_);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
- assert (is_legal_skyline ());
}
void
-Skyline::insert (Box const &b, Axis a)
+Skyline::insert (Box const &b, Real horizon_padding, Axis a)
{
list<Building> other_bld;
- list<Building> my_bld (buildings_);
+ list<Building> my_bld;
+
+ if (isnan (b[other_axis (a)][LEFT])
+ || isnan (b[other_axis (a)][RIGHT]))
+ {
+ programming_error ("insane box for skyline");
+ return;
+ }
+
+ /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
Interval iv = b[a];
- Real height = sky_ * b[other_axis (a)][sky_];
+ iv.widen (horizon_padding);
+ if (iv.length () <= EPS || b[other_axis (a)].is_empty ())
+ return;
- single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
+ my_bld.splice (my_bld.begin (), buildings_);
+ single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT], horizon_padding, &other_bld);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
- assert (is_legal_skyline ());
}
void
Skyline::raise (Real r)
+{
+ list<Building>::iterator end = buildings_.end ();
+ for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
+ i->y_intercept_ += sky_ * r;
+}
+
+void
+Skyline::shift (Real s)
{
list<Building>::iterator end = buildings_.end ();
for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
{
- i->start_height_ += sky_ * r;
- i->end_height_ += sky_ * r;
- i->b_ += sky_ * r;
+ i->end_ += s;
+ i->y_intercept_ -= s * i->slope_;
}
- assert (is_legal_skyline ());
}
Real
list<Building>::const_iterator j = other.buildings_.begin ();
Real dist = -infinity_f;
- for (; i != buildings_.end () && j != other.buildings_.end (); i++)
+ Real start = -infinity_f;
+ while (i != buildings_.end () && j != other.buildings_.end ())
{
- while (j->iv_[RIGHT] < i->iv_[LEFT])
+ Real end = min (i->end_, j->end_);
+ Real start_dist = i->height (start) + j->height (start);
+ Real end_dist = i->height (end) + j->height (end);
+ dist = max (dist, max (start_dist, end_dist));
+ if (i->end_ <= j->end_)
+ i++;
+ else
j++;
-
- Interval iv = intersection (i->iv_, j->iv_);
- dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
- i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
+ start = end;
}
return dist;
}
list<Building>::const_iterator i;
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
- if (i->iv_[RIGHT] >= airplane)
+ if (i->end_ >= airplane)
return sky_ * i->height (airplane);
}
+
assert (0);
return 0;
}
Skyline::set_minimum_height (Real h)
{
Skyline s (sky_);
- s.buildings_.front ().start_height_ = h*sky_;
- s.buildings_.front ().end_height_ = h*sky_;
- s.buildings_.front ().b_ = h*sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
-Stencil
-Skyline::stencil ()
+
+vector<Offset>
+Skyline::to_points (Axis horizon_axis) const
{
- Stencil ret;
- for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
+ vector<Offset> out;
+
+ Real start = -infinity_f;
+ for (list<Building>::const_iterator i (buildings_.begin ());
+ i != buildings_.end (); i++)
{
- if (!isinf (i->iv_.length ()))
- {
- Stencil line = Line_interface::make_line (0.1,
- Offset (i->iv_[LEFT], sky_*i->start_height_),
- Offset (i->iv_[RIGHT], sky_*i->end_height_));
- ret.add_stencil (line);
- }
+ out.push_back (Offset (start, sky_ * i->height (start)));
+ out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
+ start = i->end_;
}
- return ret;
+
+ if (horizon_axis == Y_AXIS)
+ for (vsize i = 0; i < out.size (); i++)
+ out[i] = out[i].swapped ();
+
+ return out;
+}
+
+bool
+Skyline::is_empty () const
+{
+ Building b = buildings_.front ();
+ return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
+}
+
+
+/****************************************************************/
+
+
+IMPLEMENT_SIMPLE_SMOBS (Skyline);
+IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
+IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
+
+SCM
+Skyline::mark_smob (SCM)
+{
+ ASSERT_LIVE_IS_ALLOWED ();
+ return SCM_EOL;
+}
+
+int
+Skyline::print_smob (SCM s, SCM port, scm_print_state *)
+{
+ Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
+ (void) r;
+
+ scm_puts ("#<Skyline>", port);
+
+ return 1;
}
projects / lilypond.git / blobdiff