Re: [Lib2geom-devel] Intersection

[Diederik v. L. <ma...@di...>]

njh wrote:
> and the reason I implemented the quadtree-like database.

Never heard of a quadtree-like database before, but Wikipedia again 
proved to be very helpful ;-)

> 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.

I'm impressed!

> Well for grids you would use roots instead.

Thanks for the hint. I've now got a feeling how to handle snapping of 
intersections. Let's see how far I can get with this...

Diederik