Boost logo

Boost :

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-27 17:23:15


Simonson, Lucanus J wrote:
> Andreas Fabri wrote:
>> Simonson, Lucanus J wrote:
>>> Andreas Fabri wrote:
>>>> Hi Luke,
>>>>
>>>> thank you for your explanations for the 45 degree case. You have a
>>>> nice solution. I guess for the general case I have to read the
>>>> BoostCon paper first.
>>>>
>>>> andreas
>>>
>>> Thank you for saying so.
>>>
>>> As requested, I haved added a test case for which CGAL fails to
>>> subversion
>>>
>>> https://svn.boost.org/svn/boost/sandbox/gtl/forcgal.cpp
>>
>> Hi Luke,
>>
>> Using CGAL with just floating point arithmetic is rather nonsense,
>> especially when you test robustness.
>>
>> I guess I need a recent version of boost, plus sandbox/gtl,
>> in order that it compiles?
>>
>> Best regards,
>>
>> andreas
>
> I did try CGAL with other kernel types and found that the same
> exception was thrown. I probably should have mentioned that. I used
> boost 1.35 with CGAL 3.3.1 and sandbox gtl. I'm working on getting
> the dependency on gmp straightened out to try the other kernels
> again.

I have just re-verified that I get the same exception with the Exact_predicates_inexact_constructions kernel. I should have done that first and uploaded code using a robust kernel to avoid confusion.

//definition I'm currently using for Kernel
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;

The test case was not designed to be numerically difficult, all edges are short and all input coordinates are on the integer grid. I exercised CGAL with floating point arithmetic to report its performance as optimistically as possible. It fails for apparently non-numerical robustness reasons, otherwise I would have happily benchmarked the fastest available kernel which allowed it to succeed.

I have debugged into the issue futher and it appears that the precondition being checked is the winding direction of a hole. My algorithm can't output a hole with the wrong winding direction. Regardless, I added my own check on each hole before submitting them to CGAL and they all pass my check for winding orientation. The algorithm for winding orientation must be incorrect. Specifically I note that the invariant being violated is an assumption made by the winding algorithm about its own state and not about the polygon itself:

--- from check orientation functor ---

           Comparison_result res_from = cmp_y_at_x_right(*from_left_most,
                                                         *tmp_from_left_most,
                                                         left_most_v);
 
           Comparison_result res_to = cmp_y_at_x_right(*into_left_most,
                                                       *tmp_into_left_most,
                                                       left_most_v);
           
---- from cmp_y_at_x_right functor ----

       CGAL_precondition (compare_xy(cv1.right(), p) == LARGER &&
                          compare_xy(cv2.right(), p) == LARGER);
 
The algorithm is taking the two x-monotone curves at the left most point and trying to use their relative angle and ordering to figure out the winding orientation, however apparently they fail the x-monotone invariant check performed in the cmp_y_at_x_right functor. This is hardly the fault of the input polygon and indicates some flaw in the way it was divided into x-monotone curves.

At this point I'd like to hand debugging over to CGAL authors.

Again, sorry for the confusion about robust kernels,
Luke


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk