CGAL users discussion list

[Martin Uhrin <>]

I've investigated further and narrowed down the source of the problem
somewhat.

The problem manifests with the following simplified input:

2
4 43/20 59/40 2439449798159019/1125899906842624
3321404725185741/2251799813685248 4897664594765415/2251799813685248
6605279453476727/4503599627370496 2448832297382707/1125899906842624
6530219459687219/4503599627370496
4 2448832297382707/1125899906842624 6530219459687219/4503599627370496
2448832297382707/1125899906842624 3227579732948855/2251799813685248
4878899596318037/2251799813685248 1604407367250739/1125899906842624
4841369599423283/2251799813685248 1604407367250739/1125899906842624

(2.15 1.475 -> 2.175 1.45)
(2.175 1.45 -> 2.15 1.425)

tested with CGAL 4.3 compiled with g++ 4.4.7, 4.6.3 and 4.8.2.

The two curves roughly form a half circle, the first from noon to 3 o'clock,
the second from 3 to 6 o'clock.  The first curve must protrude slightly
right of its endpoint as CGAL splits it into two x-monotone curves if added
on its own.  The second is x-monotone.

When inserting the curves one by one the point at which the logic goes wrong
happens in Arrangement_zone_2::_zone_in_face in the following section
(around lines 1119-1230 in 4.3):


If I understand this function correctly the right endpoint of my second
curve should have found the intersection point that corresponds to the
endpoint of the first curve (specifically the left most end of its second
x-monotone subcurve) at 3 o'clock.  If true this would have caused one of
the first two conditionals to be true.

Instead, the final else is invoked causing the code to incorrectly search
for an interception point somewhere in the curve associated with
intersect_he.

I presume the error lies somewhere before this points.  Either when
splitting the first curve into two or when searching the arrangement for the
interception point but I can't seem to find it.

Swapping the order of the two edges in the input file allows the program to
complete successfully and arr.is_valid() passes, the final arrangement has V
= 5,  E = 5,  F = 2.

Is anyone familiar with this code able to advise?



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/Precondition-violation-in-Bezier-x-monoton-2-h-using-Bezier-arrangement-tp4659201p4659212.html
Sent from the cgal-discuss mailing list archive at Nabble.com.