source file of the GNU LilyPond music typesetter
- (c) 2006 Joe Neeman <joeneeman@gmail.com>
+ (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
*/
#include "skyline.hh"
+#include <deque>
#include "ly-smobs.icc"
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
}
bool
-Skyline::is_legal_skyline () const
+is_legal_skyline (list<Building> const &buildings)
{
list<Building>::const_iterator i;
Real last_x = -infinity_f;
- for (i = buildings_.begin (); i != buildings_.end (); i++)
+ for (i = buildings.begin (); i != buildings.end (); i++)
{
if (i->iv_[LEFT] != last_x)
return false;
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;
+
+ if (sane ())
+ precompute ();
+}
+
void
Building::precompute ()
{
- slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
+ slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length ());
if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
slope_ = 0;
}
Real
-Building::intersection (Building const &other) const
+Building::intersection_x (Building const &other) const
{
return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
}
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)
{
bool
Building::conceals_beginning (Building const &other) const
{
- 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 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
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 = b.intersection_x (s2->front ());
end = min (end, b.iv_[RIGHT]);
b.leading_part (end);
-infinity_f, b.iv_[LEFT]));
}
-void
-Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
+/* remove a non-overlapping set of buildings from BUILDINGS and build a skyline
+ out of them */
+static list<Building>
+non_overlapping_skyline (list<Building> *const buildings)
+{
+ list<Building> result;
+ Real last_end = -infinity_f;
+ list<Building>::iterator i = buildings->begin ();
+ while (i != buildings->end ())
+ {
+ if (approx_less_than (i->iv_[LEFT], last_end))
+ {
+ i++;
+ continue;
+ }
+
+ if (approx_greater_than (i->iv_[LEFT], last_end))
+ result.push_back (Building (last_end, -infinity_f, -infinity_f, i->iv_[LEFT]));
+ else
+ i->iv_[LEFT] = last_end;
+
+ last_end = i->iv_[RIGHT];
+ list<Building>::iterator j = i;
+ i++;
+ result.splice (result.end (), *buildings, j);
+ }
+ if (last_end < infinity_f)
+ result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
+ assert (is_legal_skyline (result));
+ return result;
+}
+
+list<Building>
+Skyline::internal_build_skyline (list<Building> *buildings)
{
vsize size = buildings->size ();
if (size == 0)
{
- empty_skyline (result);
- return;
+ list<Building> result;
+ empty_skyline (&result);
+ return result;
}
else if (size == 1)
{
- single_skyline (buildings->front (), 0, result);
- return;
+ list<Building> result;
+ single_skyline (buildings->front (), 0, &result);
+ return result;
}
- list<Building> right_half;
- list<Building>::iterator i = buildings->begin ();
-
- for (vsize s = 0; s < size/2; s++)
- i++;
- right_half.splice (right_half.end (), *buildings, i, buildings->end ());
+ deque<list<Building> > partials;
+ buildings->sort ();
+ while (!buildings->empty ())
+ partials.push_back (non_overlapping_skyline (buildings));
- 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 ()
for (vsize i = 0; i < boxes.size (); i++)
{
- 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]))
+ Building front (boxes[i], horizon_padding, horizon_axis, sky);
+ if (front.sane ())
{
- iv.widen (EPS);
- Building front = Building (iv[LEFT], height, height, iv[RIGHT]);
bldgs.push_front (front);
if (horizon_padding > 0 && !isinf (front.iv_.length ()))
{
}
}
- internal_build_skyline (&bldgs, &buildings_);
- assert (is_legal_skyline ());
+ buildings_ = internal_build_skyline (&bldgs);
+ assert (is_legal_skyline (buildings_));
+}
+
+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
list<Building> my_bld;
my_bld.splice (my_bld.begin (), buildings_);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
- assert (is_legal_skyline ());
+ assert (is_legal_skyline (buildings_));
}
void
{
list<Building> other_bld;
list<Building> my_bld;
- Interval iv = b[a];
- Real height = sky_ * b[other_axis (a)][sky_];
-
- 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);
+ single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
- assert (is_legal_skyline ());
+ assert (is_legal_skyline (buildings_));
}
void
i->height_[RIGHT] += sky_ * r;
i->y_intercept_ += sky_ * r;
}
- assert (is_legal_skyline ());
+ assert (is_legal_skyline (buildings_));
+}
+
+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
return out;
}
+bool
+Skyline::is_empty () const
+{
+ return buildings_.empty ();
+}
+
+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]);
+}
+
+bool
+Skyline_pair::is_empty () const
+{
+ return skylines_[UP].is_empty ()
+ && skylines_[DOWN].is_empty ();
+}
+
+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)
{
+ ASSERT_LIVE_IS_ALLOWED ();
return SCM_EOL;
}
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