Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Nathan H. <nj...@nj...>]

On Wed, Jun 27, 2012 at 09:16:34PM +0200, Vincent Barrielle wrote:
> Hello,
> 
> I'm considering using lib2geom in my vector graphics tool to implement
> boolean operations. But before I try that I'd like to know how it
> handles hard cases such as computing intersections between two bezier
> segments that overlap, ie that have (mathematically) an infinite
> number of intersections. This case happens quite often in my project,
> so it's really important.
> 
> For what I've read of lib2geom's code, I haven't seen code dedicated
> to handling such cases, but perhaps I'm missing something?
> 
> If lib2geom does not handle this case, I'd be glad to try and
> contribute so that it is handled (I'm already trying to tackle this
> issue in my own boolops framework right now, but integrating lib2geom
> would be a great thing for my project).

The existing boolops code is in a some what disappointing state as it
turned out harder than anyone thought.

The specific case of coincident polynomial curves is actually quite
easy to detect - you just have to find more than m*n common points for
a degree m and degree n curve.  In practice you probably need far
fewer of these for a non equal curve because a randomly selected point
has a low probability of being on both curves.  This includes conic
sections (such as eliptical arcs).  To find partial overlaping bezier
segments you can start with the existing intersector and when it finds
sufficient matched points consider it equal.  (Note that
mathematically equal curves can not share points due to rounding; in
general floating point makes everything three times harder)

The hardest problem to solve is correctly dealing with the imprecision
around intersection points (determining the topology of the
intersections).  We have not found a good answer to this problem,
though we have many yet untried ideas.

If you want to try boolops we are all very happy to help, but be
warned, it's one of the hardest problems in 2d geometry processing we
know of :)

njh