
Boost : 
Subject: Re: [boost] GGL Review
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 20091116 14:49:50
Hartmut Kaiser wrote:
>> Brandon Kohn wrote:
>
>> There
>> are many buggy floating point boolean op libraries out there. Why do
>> we need another?
>
> I would like to ask you to refrain from spreading FUD with regards to
> the library under review without any concrete proof.
Hartmut, please see Barend's reply to my question about robustness:
"
> 4. If the nonselfintersecting invariant is violated at the input of the polygon pair intersection algorithm what does the algorithm do?
>
This depends on how the polygon selfintersects, and how the
selfintersection intersects with the other polygon. If the
selfintersection is untouched by the other polygon, you'll get exactly
that selfintesection back (for a union) or it is discarded (for an
intersection).
The selfintersections are not even tried to be detected. This is on
purpose because it saves another call of get_intersection_points, which
is the most timeconsuming in the current implementation.
If the selfintersection interferes with the other polygon, you can get
an invalid polygon back. As the input was already considered as
invalid, this is what is to be expected.
We've researched this recently because it occured in practice. The
algorithm will find an invalid path, detect that and skip that output
built up so far.
"
and
"
> 7. When intersection points are snapped to the floating point grid at the output of the polygon pair intersection algorithm edges may move laterally some small distance which may introduce self intersection artifacts. How is this handled by the polygon intersection algorithm?
>
This is not handled explicitly. On segmentsegment intersection in the
epsilonregions, the intersection will fall between the endpoints of
both segments. Even if it is rounded, it will not surpass those
endpoints. Therefore, selfintersections will be unlikely in most cases.
I'll not say that it is impossible, but it is unlikely.
Our implementation is not yet checked on 100% numerical robustness. If
using floating point (IEEEsingle), there might be errors in the 1e3x
regions. If using double precision, there will be less errors. That is
to say: in closeto100% of the usecases: no errors. But in the regions
of 1e3xx differences, errors might be expected, and in some cases they
might even cause selfintersections, I'll not deny that now, we've to do
more research here.
"
I might add that the robustness problem with line segment intersection is worse than that caused by snapping to floating point grid, since many bits of precision are lost during the line segment intersection point computation.
I am not arguing for rejection of the library. I am arguing that it should be accepted when it meets requirements of algorithmic correctness, performance and numerical robustness and provides sufficiently generic interfaces for performing multipolygon intersection operations. I'd like to add that the work to support infinite precision floating point coordinates in the intersection should be done before it is accepted, since it turns out that isn't actually supported yet. Basically I'm arguing that the library should be finished before becoming a part of boost, and that we accept in on condition that Barend finish it and do the things he says he plans to do before it is released.
Thanks,
Luke
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk