Re: [Lib2geom-devel] Intersection

[njh <nj...@nj...>]

On Tue, 2 Oct 2007, Diederik van Lierop wrote:

> Hi All,
>
> Does lib2geom currently provide a way to efficiently calculate the
> intersection of two Bezier paths? I've browsed through the code, but
> only found path_intersection so far. I haven't tested it, but it looks
> quite slow as it first divides one of the paths in 2^12 pieces and
> subsequently tries to do a linear_intersection for each of those pieces
> to the other path.

I had a look at implementing a direct version of the bezout approach for 
sbasis last night, didn't get it working but I did add instrumentation to 
pair-intersect toy to print the number of steps required to compute the 
intersection.  For order 10 beziers and a particularly complex example 
with 8 crossings it took 240 steps - still well under the 16 million your 
suggested polyline conversion would entail.

If anyone has any ideas about efficient ways to estimate flatness of 
arbitrary order beziers, do tell.  My best guess is to compute the max 
norm of the distance from each bezier handle to i/(n-1) along the endpoint 
line segment.  Expensive...

njh