[cairo] Intersection, Union, Difference of Paths?

[Carl Worth]

On Thu, 2008-09-04 at 18:48 -0400, Jose Aliste wrote:
> Hi all, 
> 
> I'm working in a geometry program(to work with polygons mainly) in
> python using cairo. I would like to know if there is a lib where I can
> take two cairo paths and get their intersection, union and or
> difference as a cairo path? 

There are some non-cairo-specific libraries that provide similar
functionality, (but perhaps without cairo path data structures).

> i searched but I havent found any public API in cairo for doing that,
> although I presume that there is some of this already implemented in
> the inner workings of cairo, no? If so, how difficult would be to work
> to define a public API and expose this functionality? any thoughts? 

Perhaps surprisingly, cairo doesn't actually have any such operations
internally. The core of what's needed for these kinds of path operations
is an intersection finder, (which cairo *does* have inside its
tessellator). But there are a few assumptions that are made inside the
intersection finder that would be violated if it were called from
something other than the tessellator. Also, there would be the need to
generalize from line segments to Bézier curves to handle arbitrary cairo
paths.

Finally, we've been wanting to add an implementation of John Hobby's
"tolerance square" approach to improve the robustness of our
intersection finder as well.

So, we don't yet have exactly what you're looking for in cairo, so we
can't just export it. (And if we did, it would probably make sense to
export it as a cairo-independent library.)

And as I mentioned earlier, there are other libraries that might do what
you want. One is lib2geom, which is being designed and implemented to
satisfy all the geometry needs of inkscape. I haven't looked at its
status in quite some time, so you might want to look to see if it has
what you need.

Good luck!

-Carl