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
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