id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
8652,boost::geometry::intersection fails for triangle-triangle intersection,flo@…,Barend Gehrels,"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)",Bugs,closed,Boost 1.55.0,geometry,Boost 1.53.0,Problem,fixed,,