[Boost-bugs] [Boost C++ Libraries] #8652: boost::geometry::intersection fails for triangle-triangle intersection

Subject: [Boost-bugs] [Boost C++ Libraries] #8652: boost::geometry::intersection fails for triangle-triangle intersection
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-06-05 11:09:36

#8652: boost::geometry::intersection fails for triangle-triangle intersection
------------------------------+---------------------------------------------
 Reporter:  flo@…             |       Owner:  barendgehrels
     Type:  Bugs              |      Status:  new          
Milestone:  To Be Determined  |   Component:  geometry     
  Version:  Boost 1.53.0      |    Severity:  Problem      
 Keywords:                    |  
------------------------------+---------------------------------------------
 The following example fails. The computed intersection polygon is supposed
 to be identical to the smaller of the two triangles.
 However, the computed intersection polygon is more or less the outline of
 the larger of the two triangles with an extra collinear point.


 {{{
 #include <iostream>
 #include <deque>

 #include <boost/geometry.hpp>
 #include <boost/geometry/geometries/point_xy.hpp>
 #include <boost/geometry/geometries/polygon.hpp>

 #include <boost/foreach.hpp>


 int main()
 {
     typedef
 boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double>
 >
 polygon;

     polygon green, blue;

          #define SMALL_VAL "1e-8"

     boost::geometry::read_wkt( "POLYGON((0 0, 0.05 0.04, 0.05 0, 0 0))",
 green);

     boost::geometry::read_wkt( "POLYGON((0.02 -2.77556e-17, 0.05 0.02,
 0.05 -2.77556e-17, 0.02 -2.77556e-17))", blue);

          //#define SMALL_VAL "1e-8"
          //boost::geometry::read_wkt( "POLYGON((0.02 " SMALL_VAL ", 0.05
 0.02, 0.05 " SMALL_VAL ", 0.02 " SMALL_VAL "))", blue);

     std::deque<polygon> output;
     boost::geometry::intersection(green, blue, output);

     int i = 0;
     std::cout << "The computed difference is:" << std::endl;
     BOOST_FOREACH(polygon const& p, output)
     {
                 std::cout << boost::geometry::dsv(p) << std::endl;
     }

          std::cout << std::endl;
          std::cout << "The expected output would be: " << std::endl;
          std::cout << "(((0.05, 0.02), (0.05, 0), (0.02, 0), (0.05,
 0.02)))" << std::endl;

     return 0;
 }
 }}}

 The output (compiled with gcc version 4.7.2 (Debian 4.7.2-5) on a 64bit
 debian wheezy system) is:

 ''The computed difference is:
 (((0.05, 0.02), (0.05, -2.77556e-17), (0, 0), (0.05, 0.04), (0.05, 0.02)))

 The expected output would be:
 (((0.05, 0.02), (0.05, 0), (0.02, 0), (0.05, 0.02)))''

 > g++ -v
 Using built-in specs.
 COLLECT_GCC=g++
 COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper
 Target: x86_64-linux-gnu
 Configured with: ../src/configure -v --with-pkgversion='Debian 4.7.2-5'
 --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-
 languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-
 suffix=-4.7 --enable-shared --enable-linker-build-id --with-system-zlib
 --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
 --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls
 --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-
 libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --enable-
 objc-gc --with-arch-32=i586 --with-tune=generic --enable-checking=release
 --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
 Thread model: posix
 gcc version 4.7.2 (Debian 4.7.2-5)

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/8652>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.