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. That would probably be far too slow for my snapping
> purposes, or am I missing something?

You might play with the boolops, self-intersect, pair-intersect to get a 
feel for their performance.

No, it only considers potential pairs, so for a single intersection it 
might do at most 12 comparisons.  In practice it can do far less 
comparisons than this.  You should also use existing structural 
information to avoid unnecessary comparisons (we can talk about this). 
This was one of the early applications for 2geom and the reason I 
implemented the quadtree-like database.

There are really only three approaches to curve-curve intersection:
* subdivision with accceleration (which is what we do)
* transform to sylvester matrix or resultant form and do poly root 
finding/eigenvalue decomposition.
* convergent iterative approximation such as NR or GNR

The first two are robust (will find the same number of roots and roughly 
the right positions) at a cost of more computation.  The last can be 
faster but gives no guarantees about the number found.  I have implemented 
all three but found that the performance advantages of the last two are 
outweighed by their poor worst case and inexact nature respectively.

If we do end up using gsl as a dependancy I will include eigenvalue 
decomposition based approaches for both roots and curve-curve 
intersection.

New implementations are of course welcome!

> BTW, I'm asking this because I'd like to snap to intersections of guides
> with grids, but also snap objects with other objects, with guides, or
> with grids.

Well for grids you would use roots instead.  Pop into 
lib...@co... and talk to mgsloan or me.

njh