[cairo] API request: obtain the trapezoids that are outside of the surface

[Carl Worth]

On Wed, 18 Aug 2004 17:43:36 +0200, Jost Boekemeier wrote:
> On Tue, 2004-08-17 at 21:14, Carl Worth wrote:
> > Being able to ask cairo for the bounding box of the current path seems
> > like a perfectly reasonable option. 
> 
> Probably.  Do you know an efficient way to calculate the bounding box of
> a spline? 

It depends on how tight you want the bounds to be.

It is very easy to generate a correct bounding box, (which the shape is
guaranteed not to exceed), but it won't necessarily be tight. Here are
the insights necessary, (beyond trivial things like filling with
straight line segments):

1) Given a cubic Bézier spline, it is guaranteed to be contained within
   the polygon formed by its four control points.

2) If stroking rather than filling, the bounds needs to be increased by
   one half the line width in each dimension, (this includes the space
   needed for the stroke, any caps, and for bevel and round joins).

3) If stroking with miter joins, then the increase in step 2 should
   instead be: 0.5 * (miter_limit * line_width).

So, that should lead to a calculation that is plenty fast, and is
sufficient for you to get a positive test result if a shape ever exceeds
the surface bounds. It's not necessarily tight, so it can give false
positives when the shape gets close, but I would imagine you can deal
with that, right?

> I think walking along a flat path is nearly as expensive as tesselating,
> and not necessary, imho, because the information we need will be
> calculated during tesselation anyway.

It's all linear in the number of path elements, so I can't foresee any
performance problem here. This is quite a bit easier than tessellating,
(which requires at least an O(n log n) operation).

-Carl