#include "skyline.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.
#define EPS 1e-10
static inline bool
-equal (Real x, Real y)
+approx_equal (Real x, Real y)
{
return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
}
+static inline bool
+approx_greater_than (Real x, Real y)
+{
+ return x > y + EPS;
+}
+
+static inline bool
+approx_less_than (Real x, Real y)
+{
+ return x < y - EPS;
+}
+
+static inline bool
+approx_less_equal (Real x, Real y)
+{
+ return x <= y + EPS;
+}
+
+static inline bool
+approx_greater_equal (Real x, Real y)
+{
+ return x >= y - EPS;
+}
+
+void
+Skyline::print () const
+{
+ for (list<Building>::const_iterator i = buildings_.begin ();
+ i != buildings_.end (); i++)
+ {
+ (*i).print ();
+ }
+}
+
bool
Skyline::is_legal_skyline () const
{
Real last_x = -infinity_f;
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
- if (isinf (i->start_height_) != isinf (i->end_height_))
- return false;
if (i->iv_[LEFT] != last_x)
return false;
- if (isinf (i->iv_.length ()) && i->start_height_ != i->end_height_)
- return false;
last_x = i->iv_[RIGHT];
+ if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
+ return false;
}
return last_x == infinity_f;
}
Building::Building (Real start, Real start_height, Real end_height, Real end)
: iv_ (start, end)
{
- start_height_ = start_height;
- end_height_ = end_height;
+ height_[LEFT] = start_height;
+ height_[RIGHT] = end_height;
- if (isinf (start_height) || isinf (start) || isinf (end))
- end_height_ = start_height;
- else if (isinf (end_height))
- start_height_ = end_height;
+ if (isinf (start) || isinf (end))
+ assert (start_height == end_height);
- m_ = (end_height - start_height) / (end - start);
- b_ = start_height - m_*start;
+ precompute ();
+}
+
+void
+Building::precompute ()
+{
+ slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
+ if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
+ slope_ = 0;
- if (isinf (start_height) || isinf (start) || isinf (end))
+ assert (!isinf (slope_) && !isnan (slope_));
+
+ if (isinf (iv_[START]))
{
- m_ = 0;
- b_ = start_height;
+ assert (slope_ == 0);
+ y_intercept_ = height_[LEFT];
}
+ else
+ y_intercept_ = height_[LEFT] - slope_ * iv_[START];
}
Real
Building::height (Real x) const
{
if (isinf (x))
- return start_height_;
- return m_*x + b_;
+ return (x > 0) ? height_[RIGHT] : height_[LEFT];
+ return slope_*x + y_intercept_;
+}
+
+void
+Building::print () const
+{
+ printf ("X[%f,%f] -> Y[%f,%f]\n",
+ iv_[LEFT], iv_[RIGHT],
+ height_[LEFT], height_[RIGHT]);
}
Real
Building::intersection (Building const &other) const
{
- return (b_ - other.b_) / (other.m_ - m_);
+ return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
}
void
Building::leading_part (Real chop)
{
- assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
+ assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
iv_[RIGHT] = chop;
- end_height_ = height (chop);
+ height_[RIGHT] = height (chop);
+}
+
+Building
+Building::sloped_neighbour (Real horizon_padding, Direction d) const
+{
+ Real left = iv_[d];
+ Real right = iv_[d] + d * horizon_padding;
+ Real left_height = height_[d];
+ Real right_height = height_[d] - horizon_padding;
+ if (d == LEFT)
+ {
+ swap (left, right);
+ swap (left_height, right_height);
+ }
+ return Building (left, left_height, right_height, right);
}
static void
skyline_trailing_part (list<Building> *sky, Real x)
{
- if (equal (x, sky->front ().iv_[RIGHT]))
+ if (approx_equal (x, sky->front ().iv_[RIGHT]))
sky->pop_front ();
else
assert (x < sky->front ().iv_[RIGHT]);
if (!sky->empty ())
{
sky->front ().iv_[LEFT] = x;
- sky->front ().start_height_ = sky->front ().height (x);
+ sky->front ().height_[LEFT] = sky->front ().height (x);
}
}
bool
-Building::obstructs (Building const &other) const
+Building::conceals_beginning (Building const &other) const
{
- if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
- return m_ > other.m_;
- return start_height_ > other.start_height_;
+ if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
+ return slope_ > other.slope_;
+ return height_[LEFT] > other.height_[LEFT];
}
-
-/* precondition: the building should be visible above the first
- building in skyline. The building and the skyline should
- start at the same point.
-
- return the point at which the building b is no longer visible,
- either because it has ended or because the skyline has risen
- above it. Truncate the skyline at that point.
-*/
-Real
-Skyline::last_visible_point (Building const &b, list<Building> *const skyline)
+bool
+Building::conceals (Building const &other) const
{
- assert (!skyline->front ().obstructs (b));
- while (1)
- {
- Building other = skyline->front ();
-
- /* there are 3 interesting cases:
- 1) the roofs intersect within the spans of the buildings */
- Real intersect = b.intersection (other);
- if (intersection (b.iv_, other.iv_).contains (intersect))
- {
- if (equal (intersect, b.iv_[LEFT]))
- {
- /* if the buildings have almost the same starting height, we can find
- that their intersection "equals" the start point. In this case, we
- just skip the intersection.
- */
- assert (b.m_ >= other.m_);
- }
- else
- {
- skyline_trailing_part (skyline, intersect);
- return intersect;
- }
- }
-
- /* 2) the first building ends. This is guaranteed to happen before
- the skyline becomes empty because it has to end at infinity */
- if (skyline->empty () && !other.iv_.contains (b.iv_[RIGHT]))
- assert (0);
- if (other.iv_.contains (b.iv_[RIGHT]))
- {
- skyline_trailing_part (skyline, b.iv_[RIGHT]);
- return b.iv_[RIGHT];
- }
-
- assert (!skyline->empty ());
- skyline->pop_front ();
- other = skyline->front ();
-
- /* 3) the next building in the skyline starts above b */
- if (other.start_height_ > b.height (other.iv_[LEFT]))
- return other.iv_[LEFT];
- }
+ assert (iv_[LEFT] <= other.iv_[LEFT]);
+ return (iv_[RIGHT] >= other.iv_[RIGHT])
+ && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
+ && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
}
void
{
while (!s1->empty ())
{
- if (s2->front ().obstructs (s1->front ()))
+ if (s2->front ().conceals_beginning (s1->front ()))
swap (s1, s2);
Building b = s1->front ();
- Real end = last_visible_point (b, s2);
+ while (!s2->empty () && b.conceals (s2->front ()))
+ s2->pop_front ();
+ if (s2->empty ())
+ {
+ result->push_front (b);
+ break;
+ }
+
+ /* s2 either intersects with b or it ends after b */
+ Real end = infinity_f;
+ Real s2_start_height = s2->front ().height_[LEFT];
+ Real s2_end_height = s2->front ().height_[RIGHT];
+ Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
+ Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
+ if (approx_greater_than (s2_start_height, s1_start_height))
+ end = s2->front ().iv_[LEFT];
+ else if (approx_greater_than (s2_end_height, s1_end_height))
+ end = b.intersection (s2->front ());
+ end = min (end, b.iv_[RIGHT]);
b.leading_part (end);
result->push_front (b);
skyline_trailing_part (s1, end);
+ skyline_trailing_part (s2, end);
}
result->reverse ();
}
}
static void
-single_skyline (Building const &b, list<Building> *const ret)
+single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
{
+ b.iv_.widen (horizon_padding);
+
if (!isinf (b.iv_[RIGHT]))
- ret->push_front (Building (b.iv_[RIGHT], -infinity_f, -infinity_f, infinity_f));
- ret->push_front (b);
+ ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
+ -infinity_f, infinity_f));
+ if (horizon_padding > 0)
+ ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
+
+ if (b.iv_[RIGHT] > b.iv_[LEFT])
+ ret->push_front (b);
+
+ if (horizon_padding > 0)
+ ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
if (!isinf (b.iv_[LEFT]))
- ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, b.iv_[LEFT]));
+ ret->push_front (Building (-infinity_f, -infinity_f,
+ -infinity_f, b.iv_[LEFT]));
}
void
}
else if (size == 1)
{
- single_skyline (buildings->front (), result);
+ single_skyline (buildings->front (), 0, result);
return;
}
Skyline::Skyline ()
{
sky_ = UP;
- empty_skyline (&buildings_);
+ empty_skyline (&buildings_);
+}
+
+Skyline::Skyline (Skyline const &src)
+{
+ sky_ = src.sky_;
+
+ for (list<Building>::const_iterator i = src.buildings_.begin ();
+ i != src.buildings_.end (); i++)
+ {
+ buildings_.push_back (Building ((*i)));
+ }
}
Skyline::Skyline (Direction 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;
sky_ = sky;
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]));
+ Interval iv = boxes[i][horizon_axis];
+ Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
+
+ iv.widen (horizon_padding);
+ if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT]))
+ {
+ iv.widen (EPS);
+ Building front = Building (iv[LEFT], height, height, iv[RIGHT]);
+ bldgs.push_front (front);
+ if (horizon_padding > 0)
+ {
+ bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
+ bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
+ }
+ }
}
+
internal_build_skyline (&bldgs, &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;
Interval iv = b[a];
Real height = sky_ * b[other_axis (a)][sky_];
- single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld);
+ assert (!iv.is_empty ());
+ iv.widen (EPS);
+
+ my_bld.splice (my_bld.begin (), buildings_);
+ single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), horizon_padding, &other_bld);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
assert (is_legal_skyline ());
}
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->height_[LEFT] += sky_ * r;
+ i->height_[RIGHT] += sky_ * r;
+ i->y_intercept_ += sky_ * r;
}
assert (is_legal_skyline ());
}
list<Building>::const_iterator j = other.buildings_.begin ();
Real dist = -infinity_f;
- for (; i != buildings_.end () && j != other.buildings_.end (); i++)
+ while (i != buildings_.end () && j != other.buildings_.end ())
{
- while (j->iv_[RIGHT] < i->iv_[LEFT])
+ 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])));
+ if (i->iv_[RIGHT] <= j->iv_[RIGHT])
+ i++;
+ else
j++;
-
- list<Building>::const_iterator k;
- for (k = j; k->iv_[LEFT] <= i->iv_[RIGHT] && k != other.buildings_.end (); k++)
- {
- Interval iv = intersection (i->iv_, k->iv_);
- dist = max (dist, max (i->height (iv[LEFT]) + k->height (iv[LEFT]),
- i->height (iv[RIGHT]) + k->height (iv[RIGHT])));
- }
}
return dist;
}
list<Building>::const_iterator i;
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
- if (i->iv_[RIGHT] > airplane)
+ if (i->iv_[RIGHT] >= airplane)
return sky_ * i->height (airplane);
- if (i->iv_[RIGHT] == airplane)
- {
- assert (i != buildings_.end ());
- list<Building>::const_iterator j = i;
- j++;
- return sky_ * (max (i->end_height_, j->start_height_));
- }
}
+
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 ().height_[LEFT] = h * sky_;
+ s.buildings_.front ().height_[RIGHT] = h * sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
+
+
+vector<Offset>
+Skyline::to_points () const
+{
+ vector<Offset> out;
+
+ for (list<Building>::const_iterator i (buildings_.begin ());
+ i != buildings_.end (); i++)
+ {
+ if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
+ out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
+ if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
+ out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
+ }
+ return out;
+}
+
+/****************************************************************/
+
+
+IMPLEMENT_SIMPLE_SMOBS (Skyline);
+IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
+IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
+
+SCM
+Skyline::mark_smob (SCM)
+{
+ 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