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

[Vincent B. <vin...@po...>]

On Wed, Jun 27, 2012 at 23:24 PM, Nathan Hurst wrote:
> 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)

I've been using some other way to detect overlap : two bezier segments
overlap if at least one extremtity of each segment belongs to the
other. This test seems to work pretty well in my own framework, and I
guess it's faster than computing the intersections to find out there
are too many of them (especially as I'm using recursive method which
is not the fastest..). It allows generating intersections at the
extremities of the overlap, and can orient them correctly using the
next parts of the paths.

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

I've got exactly the same problem in my framework right now, I've got
some cases were I handle the topology right, and some where I don't.
Right now my boolop procedure looks similar to the one you have in
lib2geom, though a bit different it seems as I'm implementing a
connected components on the graph defined by the two paths and their
crossings. Right now it works if there is no too long overlaping
portion (more than 3 consecutive bezier segments overlaping I'd say).
The problem that arises in that case is that I can't find a way to
orient the intersections in the middle of the path, as there's no way
to tell wether the intersection leads inside or outside the other
curve. I was thinking of possibly caching the orientation of previous
intersections during the visit of the graph, but I didn't try and
implement this method yet.

> 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 :)

I've been trying to link my application against lib2geom to try out
boolops, but the problem is, I'm using visual studio 2008 (have to,
unfortunately), and it fails when including lib2geom headers, problem
with boost optional as it seems :
"boost/optional/optional.hpp(392) : error C2664:
'Geom::GenericInterval<C>::GenericInterval(C)' : cannot convert
parameter 1 from 'const Geom::GenericOptInterval<C>' to
'Geom::IntCoord'"
So I can't try it right now, but perhaps there's a way around this
compiling issue? That would be great, as it would allow me pushing my
firm into using lib2geom, and I could contribute what I've already
done on boolops if you're interested.

--
Vincent