Re: [Boost-bugs] [Boost C++ Libraries] #11676: difference algorithm returning invalid geometry

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11676: difference algorithm returning invalid geometry
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2016-02-09 23:28:10

#11676: difference algorithm returning invalid geometry
--------------------------+------------------------------------------------
  Reporter:  anonymous    |      Owner:  barendgehrels
      Type:  Bugs         |     Status:  new
 Milestone:  To Be        |  Component:  geometry
  Determined              |   Severity:  Problem
   Version:  Boost        |   Keywords:  difference, multi-polygon, polygon
  1.59.0                  |
Resolution:               |
--------------------------+------------------------------------------------

Comment (by jean.sebastien.carrier@…):

 I'm experiencing what I think is the same problem, here's a little "main"
 i wrote to isolate the problem:

 {{{
 #include <assert.h>
 #include <iostream>

 #include "boost\geometry.hpp"
 #include "boost\geometry\geometries\multi_polygon.hpp"
 #include "boost\geometry\geometries\polygon.hpp"
 #include "boost\geometry\geometries\point_xy.hpp"

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

    Polygon polygon{ {
       { -31940.00000, 49568.00000 },
       { -31791.00000, 50320.00000 },
       { -31365.00000, 50957.00000 },
       { -30728.00000, 51382.00000 },
       { -29977.00000, 51532.00000 },
       { -29226.00000, 51382.00000 },
       { -28589.00000, 50957.00000 },
       { -28163.00000, 50320.00000 },
       { -28014.00000, 49568.00000 },
       { -28163.00000, 48817.00000 },
       { -28589.00000, 48180.00000 },
       { -29226.00000, 47754.00000 },
       { -29977.00000, 47605.00000 },
       { -30728.00000, 47754.00000 },
       { -31365.00000, 48180.00000 },
       { -31791.00000, 48817.00000 },
       { -31940.00000, 49568.00000 }
       } };

    Polygon sub_polygon1{ {
       { -31828.21364, 50132.18345 },
       { -31685.69226, 50477.46721 },
       { -31631.88116, 50557.93122 },
       { -31472.98554, 50795.52838 },
       { -31207.24135, 51062.25499 },
       { -30977.20725, 51215.73143 },
       { -30889.27342, 51274.39992 },
       { -30538.91495, 51419.76665 },
       { -30167.25333, 51494.00000 },
       { -29786.74667, 51494.00000 },
       { -29414.19290, 51419.58830 },
       { -29066.95575, 51275.88706 },
       { -28748.24902, 51063.24902 },
       { -28481.99526, 50796.99526 },
       { -28273.91392, 50485.85015 },
       { -28124.51774, 50125.78004 },
       { -28059.00324, 49795.13046 },
       { -28052.00000, 49759.78523 },
       { -28052.00000, 49376.46984 },
       { -28059.40950, 49339.12391 },
       { -28124.70576, 49010.01326 },
       { -28273.64210, 48651.55630 },
       { -28328.47188, 48569.56904 },
       { -28481.99526, 48340.00474 },
       { -28749.00474, 48072.99526 },
       { -29064.01150, 47862.33140 },
       { -29417.67150, 47715.97211 },
       { -29785.46984, 47643.00000 },
       { -30168.53016, 47643.00000 },
       { -30535.45994, 47715.79983 },
       { -30892.21570, 47863.82086 },
       { -31207.25107, 48074.50386 },
       { -31471.48590, 48339.22892 },
       { -31601.49671, 48533.63475 },
       { -31684.48242, 48657.72380 },
       { -31828.20433, 49004.52035 },
       { -31886.93066, 49300.51629 },
       { -31903.00000, 49381.51007 },
       { -31903.00000, 49754.73810 },
       { -31828.21364, 50132.18345 }
       } };

    boost::geometry::validity_failure_type failure;

    if (!boost::geometry::is_valid(polygon, failure))
    {
       std::cout << "polygon is invalid; reason : " << failure <<
 std::endl;
       assert(false); //ok
    }

    MultiPolygon multiPolygon;
    multiPolygon.push_back(sub_polygon1);
    if (!boost::geometry::is_valid(multiPolygon))
    {
       std::cout << "multi_polygon is invalid; reason : " << failure <<
 std::endl;
       assert(false); //ok
    }

    MultiPolygon result;

    boost::geometry::difference(polygon, multiPolygon, result);
    for (int i = 0; i < result.size(); ++i)
    {
       if (!boost::geometry::is_valid(result[i], failure))
       {
          std::cout << "#" << i << " is invalid; reason : " << failure <<
 std::endl;
          boost::geometry::correct(result[i]);

          if (!boost::geometry::is_valid(result[i], failure))
             std::cout << "#" << i << " is STILL invalid! reason : " <<
 failure << std::endl;
       }
    }
    if (!boost::geometry::is_valid(result, failure))
    {
       std::cout << "difference is invalid; reason : " << failure <<
 std::endl;
       assert(false); //fails
    }

    std::cout << "Hello World!" << std::endl;
    return 0;
 }
 }}}

 which yields the following output:


 {{{
 #0 is invalid; reason : 21
 #0 is STILL invalid! reason : 21
 #2 is invalid; reason : 21
 #2 is STILL invalid! reason : 21
 #4 is invalid; reason : 21
 #4 is STILL invalid! reason : 21
 #7 is invalid; reason : 21
 #7 is STILL invalid! reason : 21
 #8 is invalid; reason : 21
 #8 is STILL invalid! reason : 21
 difference is invalid; reason : 21
 Assertion failed: false
 }}}

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