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