Re: [Lib2geom-devel] Recent progress on boolops

[Krzysztof K. <twe...@gm...>]

2014-08-14 23:24 GMT+02:00 Nathan Hurst <nj...@nj...>:
> On Thu, Aug 14, 2014 at 05:12:48PM +0200, Krzysztof Kosiński wrote:
> ...
>> Regarding the second issue, I added some unit tests that indicate that
>> subdivision of one fragment (be it Bezier or SBasis) is actually
>> exact, in the sense that A.at1() == B.at0(). The actual problem is the
>> simultaneous subdivision of two fragments. If we have fragments A and
>> B and we determine that they intersect at time values (a, b), we need
>> an API that produces four Beziers A1, A2, B1, B2 such that A1.at1() ==
>> A2.at0() == B1.at1() == B2.at0() exactly. This is required because
>> A.valueAt(a) will almost always be slightly different from
>> B.valueAt(b). More generally, given a vector of time value pairs, we
>> need to create a vector of result Beziers adhering to the above
>> condition.
>
> That makes sense, nice analysis.  I suspect averaging the results of
> A1(a), A2(a) for x, B for y, and setting the end points appropriately
> will be good enough.
>
> njh

I implemented this procedure for Bezier. It is in basic-intersection.h.

I discovered that SBasis subdivision is actually not exact, though
very rarely. The problem manifested only for subdivision values very
close to 0 or 1. Some example values for which subdivision generated
incorrect results are:

9.236844517377745e-7
0.000002178347805105465
0.9999939507854229
0.9999942671178794
0.999997049626076
0.9999978101666039

This was probably caused by the implementation of portion() by means
of compose(), where the calculation of endpoints involves a
subtraction. This is now fixed by forcibly setting the endpoints to
the result of valueAt at the specified times.

Regards, Krzysztof