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

Subject: Re: [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 17:43:32

#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      
Resolution:                    |    Keywords:               
-------------------------------+--------------------------------------------

Comment (by anonymous):

 Mapping the floating point coordinates to integer values does not solve
 the problem either (see the following test program). The intersection
 remains empty.

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

 #include <boost/geometry.hpp>
 #include <boost/geometry/geometries/point_xy.hpp>
 #include <boost/geometry/geometries/polygon.hpp>
 #include <boost/geometry/algorithms/assign.hpp>
 #include <boost/assign/list_of.hpp>
 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
 #include <boost/geometry/views/identity_view.hpp>
 #include <boost/geometry/core/closure.hpp>
 #include <boost/geometry/core/exterior_ring.hpp>

 #include <boost/foreach.hpp>

 #define INF__ (std::numeric_limits<double>::infinity())

 inline
 void mapPointToInt(const double &x, const double &xOffset, const double
 &xSize,
 int &xi)
 {
         xi = ((x - xOffset)/xSize)*INT_MAX;
 }

 inline
 void mapPointToFloatingPoint(int xI, const double &xOffset, const double
 &xSize, double &x)
 {
         x = (double(xI)/double(INT_MAX))*xSize + xOffset;
 }

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

     polygon green, blue;

          double greenPoints[4][2] = {{ 0, 0}, {0.05, 0.04}, {0.05, 0}, {0,
 0}};
          double bluePoints[4][2] = {{ 0.02, -2.77556e-17}, {0.05, 0.02},
 {0.05 -2.77556e-17}, {0.02 -2.77556e-17}};

          // Get the maximum extension
          //
          double min[2] = { INF__, INF__ };
          double max[2] = { -INF__, -INF__ };

          for(int i = 0; i < 3; ++i ) {
                 for(int j = 0; j < 2; ++j) {
                         min[j] = (greenPoints[i][j] < min[j]) ?
 greenPoints[i][j] : min[j];
                         min[j] = (bluePoints[i][j] < min[j]) ?
 bluePoints[i][j] : min[j];

                         max[j] = (greenPoints[i][j] > max[j]) ?
 greenPoints[i][j] : max[j];
                         max[j] = (bluePoints[i][j] > max[j]) ?
 bluePoints[i][j] : max[j];
                 }
         }

         std::cout << "x-range: " << min[0] << " - " << max[0] <<
 std::endl;
         std::cout << "y-range: " << min[1] << " - " << max[1] <<
 std::endl;

         double size[2] = { max[0] - min[0], max[1] - min[1] };

         for(int i = 0; i < 4; ++i) {

                 {
                         int xI, yI;
                         mapPointToInt(greenPoints[i][0], min[0], size[0],
 xI);
                         mapPointToInt(greenPoints[i][1], min[1], size[1],
 yI);

                         boost::geometry::append(green,
 boost::geometry::make<Point>(xI, yI));
                 }

                 {
                         int xI, yI;
                         mapPointToInt(bluePoints[i][0], min[0], size[0],
 xI);
                         mapPointToInt(bluePoints[i][1], min[1], size[1],
 yI);

                         boost::geometry::append(blue,
 boost::geometry::make<Point>(xI, yI));
                 }
         }

         boost::geometry::correct(green);
         boost::geometry::correct(blue);

         std::cout << "green poly: " <<
                 boost::geometry::dsv(green) << std::endl;
         std::cout << "blue poly: " <<
                 boost::geometry::dsv(blue) << std::endl;

     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;
     }
         typedef boost::geometry::identity_view<
                                 typename
 boost::geometry::ring_type<polygon>::type//,
                                 //boost::geometry::open
         > view_type;

         view_type view(boost::geometry::exterior_ring(output[0]));
         for(auto it = boost::begin(view); it != boost::end(view); ++it) {

                 double x, y;

                 mapPointToFloatingPoint(
                                 boost::geometry::get<0>(*it),
                                 min[0],
                                 size[0],
                                 x);
                 mapPointToFloatingPoint(
                                 boost::geometry::get<1>(*it),
                                 min[1],
                                 size[1],
                                 y);
                 std::cout << "   (" << x << ", " << y << ")" << std::endl;
         }
 }

 }}}

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