Subject: CGAL users discussion list
List archive
- From: Tom Bobach <>
- To:
- Subject: Suspect BUG in CGAL Segment_2 / Ray_2 intersection
- Date: Sat, 23 Jun 2007 20:48:33 +0200
- Organization: University of Kaiserslautern
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
- Suspect BUG in CGAL Segment_2 / Ray_2 intersection, Tom Bobach, 06/23/2007
Archive powered by MHonArc 2.6.16.