#include "skyline.hh"
-#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.
#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
{
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_;
+ 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, Real max_slope)
+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) || isinf (end))
+ assert (start_height == end_height);
+
+ precompute ();
+}
+
+Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ Real height = sky * b[other_axis (horizon_axis)][sky];
- if (isinf (start))
- assert (isinf (start_height) || start_height == end_height);
- if (isinf (end))
- assert (isinf (end_height) || start_height == end_height);
+ iv_ = b[horizon_axis];
+ iv_.widen (horizon_padding + EPS);
+ height_[LEFT] = height;
+ height_[RIGHT] = height;
+
+ if (sane ())
+ precompute ();
+}
+
+void
+Building::precompute ()
+{
+ slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
+ if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
+ slope_ = 0;
- 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);
+ assert (!isinf (slope_) && !isnan (slope_));
- if (isinf (start))
+ if (isinf (iv_[START]))
{
- if (isinf (end))
- b_ = start_height;
- else
- b_ = end_height - m_*end;
+ assert (slope_ == 0);
+ y_intercept_ = height_[LEFT];
}
else
- b_ = start_height - m_*start;
+ y_intercept_ = height_[LEFT] - slope_ * iv_[START];
}
Real
Building::height (Real x) const
{
if (isinf (x))
- return (x > 0) ? end_height_ : 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, Real h)
+Building::leading_part (Real chop)
{
- assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
- assert (equal (h, height (chop)));
+ assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
iv_[RIGHT] = chop;
- end_height_ = h;
+ 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);
+}
+
+bool
+Building::sane () const
+{
+ return approx_less_than (iv_[LEFT], iv_[RIGHT])
+ && !isinf (height_[RIGHT])
+ && !isinf (height_[LEFT]);
}
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_ || (m_ == other.m_ && b_ > other.b_);
- 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];
+}
+
+bool
+Building::conceals (Building const &other) const
+{
+ 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 ();
- while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
- && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]) + EPS)
+ while (!s2->empty () && b.conceals (s2->front ()))
s2->pop_front ();
+ if (s2->empty ())
+ {
+ result->push_front (b);
+ break;
+ }
- /* the front of s2 either intersects with b or it ends after b */
+ /* s2 either intersects with b or it ends after b */
Real end = infinity_f;
- Real s2_end_height = s2->front ().end_height_;
+ 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 (s2_end_height > s1_end_height + EPS)
+ 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]);
- Real height = b.height (end);
- b.leading_part (end, height);
+ b.leading_part (end);
result->push_front (b);
skyline_trailing_part (s1, end);
- if (!s1->empty ())
- s1->front ().start_height_ = height;
skyline_trailing_part (s2, 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 horizon_padding, list<Building> *const ret)
{
+ b.iv_.widen (horizon_padding);
+
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);
+ ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
+ -infinity_f, infinity_f));
+ if (horizon_padding > 0 && !isinf (b.iv_.length ()))
+ ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
+
+ if (b.iv_[RIGHT] > b.iv_[LEFT])
+ ret->push_front (b);
+
+ if (horizon_padding > 0 && !isinf (b.iv_.length ()))
+ ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
if (!isinf (b.iv_[LEFT]))
- ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
+ ret->push_front (Building (-infinity_f, -infinity_f,
+ -infinity_f, b.iv_[LEFT]));
}
void
}
else if (size == 1)
{
- single_skyline (buildings->front (), result, max_slope_);
+ single_skyline (buildings->front (), 0, result);
return;
}
Skyline::Skyline ()
{
- max_slope_ = 2;
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)
{
- 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;
sky_ = sky;
- max_slope_ = 2;
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_));
+ Building front (boxes[i], horizon_padding, horizon_axis, sky);
+ if (front.sane ())
+ {
+ bldgs.push_front (front);
+ if (horizon_padding > 0 && !isinf (front.iv_.length ()))
+ {
+ 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 ());
}
+Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
+{
+ sky_ = sky;
+ Building front (b, 0, horizon_axis, sky);
+ single_skyline (front, horizon_padding, &buildings_);
+}
+
void
Skyline::merge (Skyline const &other)
{
}
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;
- Interval iv = b[a];
- Real height = sky_ * b[other_axis (a)][sky_];
my_bld.splice (my_bld.begin (), buildings_);
- single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
+ single_skyline (Building (b, 0, a, sky_), 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 ());
}
+void
+Skyline::shift (Real r)
+{
+ list<Building>::iterator end = buildings_.end ();
+ for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
+ {
+ i->iv_[LEFT] += r;
+ i->iv_[RIGHT] += r;
+ }
+}
+
Real
Skyline::distance (Skyline const &other) const
{
if (i->iv_[RIGHT] >= 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 ().height_[LEFT] = h * sky_;
+ s.buildings_.front ().height_[RIGHT] = h * sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
-Stencil
-Skyline::stencil ()
+
+vector<Offset>
+Skyline::to_points () const
{
- Stencil ret;
- for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
+ vector<Offset> out;
+
+ 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);
- }
+ 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 ret;
+ return out;
+}
+
+Skyline_pair::Skyline_pair ()
+ : skylines_ (Skyline (DOWN), Skyline (UP))
+{
+}
+
+Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
+ : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
+{
+}
+
+Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
+ : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
+{
+}
+
+void
+Skyline_pair::raise (Real r)
+{
+ skylines_[UP].raise (r);
+ skylines_[DOWN].raise (r);
+}
+
+void
+Skyline_pair::shift (Real r)
+{
+ skylines_[UP].shift (r);
+ skylines_[DOWN].shift (r);
+}
+
+void
+Skyline_pair::insert (Box const &b, Real padding, Axis a)
+{
+ skylines_[UP].insert (b, padding, a);
+ skylines_[DOWN].insert (b, padding, a);
+}
+
+void
+Skyline_pair::merge (Skyline_pair const &other)
+{
+ skylines_[UP].merge (other[UP]);
+ skylines_[DOWN].merge (other[DOWN]);
+}
+
+Skyline&
+Skyline_pair::operator [] (Direction d)
+{
+ return skylines_[d];
+}
+
+Skyline const&
+Skyline_pair::operator [] (Direction d) const
+{
+ return skylines_[d];
+}
+
+/****************************************************************/
+
+
+IMPLEMENT_SIMPLE_SMOBS (Skyline);
+IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
+IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
+
+IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
+IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
+IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
+
+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;
+}
+
+SCM
+Skyline_pair::mark_smob (SCM)
+{
+ return SCM_EOL;
+}
+
+int
+Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
+{
+ Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
+ (void) r;
+
+ scm_puts ("#<Skyline-pair>", port);
+ return 1;
}