Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

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