[cairo] Culling geometry outside the target surface

[Federico Mena Quintero]

On Mon, 2005-03-07 at 11:04 -0500, Carl Worth wrote:

> I had an earlier formulation of the algorithm which I believe does not
> have the bug, (which I introduced when rewriting it to make it simpler
> to understand, and to match the current cairo_polygon interface). The
> previous version was:
> 
> 	When adding a new point to a polygon, consider it together
> 	with the previous two points in the polygon. If the bounding
> 	box of the three points is "outside" the target region, then
> 	the middle point can be discarded before the new point is
> 	added.
> 
> Additionally, I noticed another corner case that affects either
> formulation. When considering whether a bounding box is "outside" of
> the target region, (for the purpose of guaranteeing that enclosed
> segments are outside the region), it is not sufficient that the box
> does not intersect the region. It must also be the case that the box
> does not entirely contain the target region.

Look up "Clipping, Liang-Barsky polygon algorithm" in Foley & Van Dam.
it describes a nice algorithm for clipping a complex polygon to a
rectangular region.

  Federico