a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
This means that the merging routine doesn't need to be aware of direction,
but the distance routine does.
-*/
-/* 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
+ Be careful about numerical accuracy. When dealing with extremely small values,
+ computation errors may arise due to the use of floating point arithmetic.
+ For example, if left and right have equal values to start with, in C++
+ they may not receive the same value after
+
+ left = left*factor + offset;
+ right = right*factor + offset;
+
+ Which is very unfortunate. Maybe using GCC compiler options to disallow
+ extended precision for intermediate results and/or the choice to store
+ intermediates with less than full precision would retain some kind of
+ deterministic behavior that way.
+
+ Anyway, it seems that accepting extremely narrow building in skylines
+ doesn't cause accuracy problems to us, so we allow arbitrarily small buildings.
+ However, as Keith pointed out, problems may appear if more than one operation
+ is done before storing the result, and/or there are different code paths
+ for doing the operations to the different ends of an interval.
+*/
static void
print_buildings (list<Building> const &b)
return infinity_f;
}
-// Returns the interval of horizontal shifts for which this
-// building (pointing up) overlaps the other building (pointing down).
-Interval
-Building::overlapping_shift_interval (Building const &other) const
-{
- Interval iv;
-
- // If one building is empty, there will never be an overlap.
- if (y_intercept_ == -infinity_f || other.y_intercept_ == -infinity_f)
- return iv;
-
- // There are two kinds of interesting positions:
- // - when the horizontal extents of the buildings just touch
- // - when an endpoint of one building intersects the roof of the other.
- // The interval we are looking for is the smallest one that
- // contains all of the interesting points.
-
-
- Real my_y1 = height (start_);
- Real my_y2 = height (end_);
- Real his_y1 = -other.height (other.start_); // "-" because OTHER points down
- Real his_y2 = -other.height (other.end_);
-
- // If both buildings are infinite in the same direction,
- // the return value is either empty or full.
- if ((isinf (start_) && isinf (other.start_))
- || (isinf (end_) && isinf (other.end_)))
- return (y_intercept_ > other.y_intercept_)
- ? Interval (-infinity_f, infinity_f) : Interval ();
-
- // ...when the horizontal extents of the buildings just touch...
- if (my_y1 >= his_y2)
- iv.add_point (other.end_ - start_);
- if (my_y2 >= his_y1)
- iv.add_point (other.start_ - end_);
-
- // ...when an endpoint of one building intersects the roof of the other.
- Real p1 = shift_to_intersect (other.start_, his_y1);
- Real p2 = shift_to_intersect (other.end_, his_y2);
- // "-my_y1" because OTHER points down:
- Real p3 = other.shift_to_intersect (start_, -my_y1);
- Real p4 = other.shift_to_intersect (end_, -my_y2);
- if (!isinf (p1))
- iv.add_point (p1);
- if (!isinf (p2))
- iv.add_point (p2);
- if (!isinf (p3))
- iv.add_point (p3);
- if (!isinf (p4))
- iv.add_point (p4);
-
- return iv;
-}
-
static Real
first_intersection (Building const &b, list<Building> *const s, Real start_x)
{
{
bool last_empty = false;
list<Building>::iterator i;
+
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
if (last_empty && i->y_intercept_ == -infinity_f)
break;
}
- /* only include buildings wider than epsilon */
- if (end > x + EPS)
+ if (end >= x)
{
b.leading_part (end);
b.start_ = last_end;
static void
single_skyline (Building b, list<Building> *const ret)
{
- if (b.end_ > b.start_ + EPS)
- {
- ret->push_back (Building (-infinity_f, -infinity_f,
- -infinity_f, b.start_));
- ret->push_back (b);
- ret->push_back (Building (b.end_, -infinity_f,
- -infinity_f, infinity_f));
- }
- else
- {
- empty_skyline (ret);
- }
+ assert (b.end_ >= b.start_);
+
+ if (b.start_ != -infinity_f)
+ ret->push_back (Building (-infinity_f, -infinity_f,
+ -infinity_f, b.start_));
+ ret->push_back (b);
+ if (b.end_ != infinity_f)
+ ret->push_back (Building (b.end_, -infinity_f,
+ -infinity_f, infinity_f));
}
/* remove a non-overlapping set of boxes from BOXES and build a skyline
continue;
}
- if (x1 > last_end + EPS)
+ if (x1 >= last_end)
result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
result.push_back (*i);
/*
Build skyline from a set of boxes.
- Boxes should have fatness in the horizon_axis, otherwise they are ignored.
+ Boxes should be non-empty on both axes. Otherwise, they will be ignored
*/
Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
{
list<Building> buildings;
sky_ = sky;
- Axis vert_axis = other_axis (horizon_axis);
for (vsize i = 0; i < boxes.size (); i++)
- {
- Interval iv = boxes[i][horizon_axis];
- if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
- buildings.push_front (Building (boxes[i], horizon_axis, sky));
- }
+ if (!boxes[i].is_empty ())
+ buildings.push_front (Building (boxes[i], horizon_axis, sky));
buildings_ = internal_build_skyline (&buildings);
normalize ();
/*
build skyline from a set of line segments.
- Buildings should have fatness in the horizon_axis, otherwise they are ignored.
+ Segments can be articulated from left to right or right to left.
+ In the case of the latter, they will be stored internally as left to right.
*/
Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
{
Real y1 = left[other_axis (horizon_axis)] * sky;
Real y2 = right[other_axis (horizon_axis)] * sky;
- if (x1 + EPS < x2)
+ if (x1 <= x2)
buildings.push_back (Building (x1, y1, y2, x2));
}
sky_ = sky;
Building front (b, horizon_axis, sky);
single_skyline (front, &buildings_);
+ normalize ();
}
void
}
/* do the same filtering as in Skyline (vector<Box> const&, etc.) */
- Interval iv = b[a];
- if (iv.length () <= EPS || b[other_axis (a)].is_empty ())
+ if (b.is_empty ())
return;
my_bld.splice (my_bld.begin (), buildings_);
Skyline
Skyline::padded (Real horizon_padding) const
{
+ if (horizon_padding < 0.0)
+ warning ("Cannot have negative horizon padding. Junking.");
+
+ if (horizon_padding <= 0.0)
+ return *this;
+
list<Building> pad_buildings;
for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
{
return sky_ * ret;
}
+Direction
+Skyline::direction () const
+{
+ return sky_;
+}
+
+Real
+Skyline::left () const
+{
+ for (list<Building>::const_iterator i (buildings_.begin ());
+ i != buildings_.end (); i++)
+ if (i->y_intercept_ > -infinity_f)
+ return i->start_;
+
+ return infinity_f;
+}
+
+Real
+Skyline::right () const
+{
+ for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
+ i != buildings_.rend (); ++i)
+ if (i->y_intercept_ > -infinity_f)
+ return i->end_;
+
+ return -infinity_f;
+}
+
Real
Skyline::max_height_position () const
{
Real x = robust_scm2double (x_scm, 0.0);
return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
}
+
+LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
+ 1, 0, 0, (SCM sky),
+ "Return whether @var{sky} is empty.")
+{
+ Skyline *s = Skyline::unsmob (sky);
+ LY_ASSERT_SMOB (Skyline, sky, 1);
+ return scm_from_bool (s->is_empty ());
+}
projects / lilypond.git / blobdiff