/* 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.
*/
+/*
+ FIXME:
+
+ * Consider to use
+
+ typedef list<Skyline_point> Skyline;
+ struct Skyline_point
+ {
+ Real x;
+ Drul_array<Real> ys;
+ };
+
+ this is a cleaner representation, as it doesn't duplicate the X, and
+ doesn't need bogus buildings at infinity --hwn.
+
+
+ * All the messing around with EPS is very fishy. There are no
+ complicated numerical algorithms involved, so EPS should not be
+ necessary.
+
+ --hwn
+
+
+ */
+
#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
{
{
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->height_[LEFT], last_h))
- return false;
last_x = i->iv_[RIGHT];
- last_h = i->height_[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, Real max_slope)
+Building::Building (Real start, Real start_height, Real end_height, Real end)
: iv_ (start, end)
{
height_[LEFT] = start_height;
height_[RIGHT] = end_height;
- if (isinf (start))
- assert (isinf (start_height) || start_height == end_height);
- if (isinf (end))
- assert (isinf (end_height) || start_height == 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];
+
+ iv_ = b[horizon_axis];
+ iv_.widen (horizon_padding + EPS);
+ height_[LEFT] = height;
+ height_[RIGHT] = height;
- precompute (max_slope);
+ if (sane ())
+ precompute ();
}
void
-Building::precompute (Real max_slope)
+Building::precompute ()
{
slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
- if (height_[LEFT] == height_[RIGHT])
+ if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
slope_ = 0;
- if (isinf (slope_) || isnan (slope_))
- slope_ = max_slope * (height_[LEFT] < height_[RIGHT] ? 1 : -1);
-
-#if 0
- /*
- this check is sensitive to roundoff errors when converting to/from
- sequences of points.
- */
- assert (abs (slope_) <= max_slope + EPS);
-#endif
-
+
+ assert (!isinf (slope_) && !isnan (slope_));
+
if (isinf (iv_[START]))
{
- if (isinf (iv_[STOP]))
- zero_height_ = height_[LEFT];
- else
- zero_height_ = height_[RIGHT] - slope_ * iv_[STOP];
+ assert (slope_ == 0);
+ y_intercept_ = height_[LEFT];
}
else
- zero_height_ = height_[LEFT] - slope_ * iv_[START];
+ y_intercept_ = height_[LEFT] - slope_ * iv_[START];
}
Real
{
if (isinf (x))
return (x > 0) ? height_[RIGHT] : height_[LEFT];
- return slope_*x + zero_height_;
+ return slope_*x + y_intercept_;
}
void
}
Real
-Building::intersection (Building const &other) const
+Building::intersection_x (Building const &other) const
{
- return (zero_height_ - other.zero_height_) / (other.slope_ - slope_);
+ 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;
- height_[RIGHT] = 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]);
}
bool
-Building::obstructs (Building const &other) const
+Building::conceals_beginning (Building const &other) const
+{
+ bool w = false;
+ Real h = other.height (iv_[LEFT]);
+ if (approx_equal (height_[LEFT], h))
+ w = slope_ > other.slope_;
+ else if (height_[LEFT] > h)
+ w = true;
+ else
+ w = false;
+
+ return w;
+}
+
+bool
+Building::conceals (Building const &other) const
{
- if (equal (intersection (other), iv_[LEFT]) || equal (height_[LEFT], other.height_[LEFT]))
- return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
- return height_[LEFT] > other.height_[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 ();
- while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
- && s2->front ().height_[RIGHT] <= 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_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)
- end = b.intersection (s2->front ());
+ 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_x (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 ().height_[LEFT] = 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.height_[RIGHT],
- -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.height_[LEFT], b.iv_[LEFT], max_slope));
+ -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)
{
- max_slope_ = src.max_slope_;
sky_ = src.sky_;
for (list<Building>::const_iterator i = src.buildings_.begin ();
Skyline::Skyline (Direction sky)
{
- max_slope_ = 2;
sky_ = sky;
empty_skyline (&buildings_);
}
/*
- build skyline from a set of boxes.
+ 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, otherwise they are ignored.
+ 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, Axis horizon_axis, Direction sky)
+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][horizon_axis];
- Real height = sky * boxes[i][other_axis (horizon_axis)][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 (vector<Offset> const &points, Real max_slope, Direction sky)
+Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
{
sky_ = sky;
- max_slope_ = max_slope;
-
- for (vsize i = 1; i < points.size (); i++)
- {
- buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS],
- sky * points[i][Y_AXIS],
-
- points[i][X_AXIS],
- max_slope));
-
- }
-
- assert (is_legal_skyline ());
+ Building front (b, 0, horizon_axis, sky);
+ single_skyline (front, horizon_padding, &buildings_);
}
void
}
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_];
-
- assert (!iv.is_empty ());
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 ());
}
{
i->height_[LEFT] += sky_ * r;
i->height_[RIGHT] += sky_ * r;
- i->zero_height_ += 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
{
Skyline s (sky_);
s.buildings_.front ().height_[LEFT] = h * sky_;
s.buildings_.front ().height_[RIGHT] = h * sky_;
- s.buildings_.front ().zero_height_ = h * sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
{
vector<Offset> out;
- bool first = true;
for (list<Building>::const_iterator i (buildings_.begin ());
i != buildings_.end (); i++)
{
- if (first)
- out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).height_[LEFT]));
-
- first = false;
- out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).height_[RIGHT]));
+ 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;
}
+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_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 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;
+}
projects / lilypond.git / blobdiff