CGAL users discussion list

[Tom Bobach <>]

Hi all,

it took me some time to track this weird behaviour down. I guess you agree 
that the following should not intersect, even counting numerical 
instabilities:

seg = Segment_2(
        Point_2( 0.460330023660802112317469436675,
                 0.215139308133430989800061183814 ),
        Point_2( 0.5,
                 0.214285714285714246063463406244 ) );
ray = Ray_2(
        Point_2( 0.483333333333333281522925517493,
                 0.232142857142857095276156087493 ),
        Point_2( 0.483333333333333337034076748751,
                 0.26547619047619047671915382125) );


but CGAL::intersection(seg, ray) finds an intersection.

If I repeat that with fewer decimal digits,

seg = Segment_2(
        Point_2( 0.4, 0.2 ),
        Point_2( 0.5, 0.2 ) );
ray = Ray_2(
        Point_2( 0.48, 0.23 ),
        Point_2( 0.48, 0.26) );


no intersection is found as expected. I checked the above with CGAL 3.3 (also 
with 3.2.1) with GCC-4.1.2 and GCC-4.1.1.

Attached you find program that should reproduce the bug. Below you find some 
test runs on different systems I did.

Besides that it is an impressive system you built there.


Best regards
        
        Tom



== test 1 ==

g++ -v 
Using built-in specs.
Target: i686-pc-linux-gnu
Configured 
with: /var/tmp/portage/sys-devel/gcc-4.1.2/work/gcc-4.1.2/configure 
--prefix=/usr --bindir=/usr/i686-pc-linux-gnu/gcc-bin/4.1.2 
--includedir=/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/include 
--datadir=/usr/share/gcc-data/i686-pc-linux-gnu/4.1.2 
--mandir=/usr/share/gcc-data/i686-pc-linux-gnu/4.1.2/man 
--infodir=/usr/share/gcc-data/i686-pc-linux-gnu/4.1.2/info 
--with-gxx-include-dir=/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/include/g++-v4 
--host=i686-pc-linux-gnu --build=i686-pc-linux-gnu --disable-altivec 
--enable-nls --without-included-gettext --with-system-zlib --disable-checking 
--disable-werror --enable-secureplt --disable-libunwind-exceptions 
--disable-multilib --enable-libmudflap --disable-libssp --disable-libgcj 
--enable-languages=c,c++,fortran --enable-shared --enable-threads=posix 
--enable-__cxa_atexit --enable-clocale=gnu
Thread model: posix
gcc version 4.1.2 (Gentoo 4.1.2)

calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.4 0.2 0.5 0.2 ) and ray( 0.48 0.23 
0.48 0.26 )
no intersection found -> CGAL works

calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
no intersection found -> CGAL works

== test 2 ==

g++ -v
Using built-in specs.
Target: x86_64-suse-linux
Configured 
with: ../configure --enable-threads=posix --prefix=/usr 
--with-local-prefix=/usr/local --infodir=/usr/share/info 
--mandir=/usr/share/man --libdir=/usr/lib64 --libexecdir=/usr/lib64 
--enable-languages=c,c++,objc,fortran,obj-c++,java,ada 
--enable-checking=release --with-gxx-include-dir=/usr/include/c++/4.1.2 
--enable-ssp --disable-libssp --disable-libgcj --with-slibdir=/lib64 
--with-system-zlib --enable-shared --enable-__cxa_atexit 
--enable-libstdcxx-allocator=new --program-suffix=-4.1 
--enable-version-specific-runtime-libs --without-system-libunwind 
--with-cpu=generic --host=x86_64-suse-linux
Thread model: posix
gcc version 4.1.2 20061115 (prerelease) (SUSE Linux)

calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.4 0.2 0.5 0.2 ) and ray( 0.48 0.23 
0.48 0.26 )
no intersection found -> CGAL works
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644


== test 3 ==

g++ -v
Using built-in specs.
Target: i486-linux-gnu
Configured 
with: ../src/configure -v --enable-languages=c,c++,java,f95,objc,ada,treelang 
--prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib 
--without-included-gettext --enable-threads=posix --enable-nls 
--program-suffix=-4.0 --enable-__cxa_atexit --enable-clocale=gnu 
--enable-libstdcxx-debug --enable-java-awt=gtk-default --enable-gtk-cairo 
--with-java-home=/usr/lib/jvm/java-1.4.2-gcj-4.0-1.4.2.0/jre --enable-mpfr 
--disable-werror --enable-checking=release 
i486-linux-gnu
Thread model: posix
gcc version 4.0.3 20051201 (prerelease) (Debian 4.0.2-5)

calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.4 0.2 0.5 0.2 ) and ray( 0.48 0.23 
0.48 0.26 )
no intersection found -> CGAL works
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
no intersection found -> CGAL works


== test 4 ==

CGAL 3.2.1

D:\Apps\msvc8\vc\bin>cl /?
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 
80x86

calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.4 0.2 0.5 0.2 ) and ray( 0.48 0.23 
0.48 0.26 )
no intersection found -> CGAL works
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644
calling CGAL::intersection for segment( 0.46033 0.215139 0.5 0.214286 ) and 
ray( 0.483333 0.232143 0.483333 0.265476 )
impossible intersection found: 0.483333 0.214644





-- 
Dipl. Inform Tom Bobach, University of Kaiserslautern
AG Geometrische Algorithmen
P.O. Box 3049
D-67653 Kaiserslautern
Germany
Phone: 0631-205 3800
Fax: 0631-205 3270

Attachment: cgal_bug.tar.bz2
Description: application/tbz