vschoech@… — Mon, 21 Sep 2015 15:02:30 GMT

Sorry for "anonymous". I filed this ticket.

vschoech@… — Mon, 21 Sep 2015 15:14:24 GMT

Here is another example:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((2974 352,2940 336,2907 334,2907 317,2974 317,2974 352)),((2940 354,2957 361,2907 361,2907 353,2940 354)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true
tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((576 330,576 312,777 348,576 330)),((2968 349,2940 342,2902 334,2940 336,2968 349)),((3612 516,3276 498,2968 349,3276 432,3612 444,3612 516)),((2902 334,2598 324,2262 438,1926 414,1590 384,1248 354,1590 372,1926 384,2262 402,2598 276,2902 334)),((1248 354,912 372,777 348,912 360,1248 354)))", polygonB); // does not throw
boost::geometry::is_valid(polygonB); // returns true
tc::geo::polygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((2940 354,2957 361,2907 361,2907 353,2940 354)),((2974 352,2968 349,2940 336,2907 334,2907 317,2974 317,2974 351,2968 349,2974 352)))
boost::geometry::is_valid(polygonC); // returns false!

Barend Gehrels — Sun, 01 Nov 2015 16:06:17 GMT

Still a problem in beta for 1.60.
It generates spikes.
Added test case to unit test suite

jean.sebastien.carrier@… — Tue, 09 Feb 2016 23:28:10 GMT

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

version changed

Thu, 04 Jan 2018 15:12:50 GMT

version Boost 1.59.0 → Boost 1.66.0

Still present in boost 1.66.0.

Mon, 25 Jun 2018 07:32:33 GMT

No longer reproducible in 1.67.0.

status, milestone changed; resolution set

Barend Gehrels — Mon, 25 Jun 2018 18:32:32 GMT

status new → closed
resolution → fixed
milestone To Be Determined → Boost 1.67.0

Thanks for verifying!

Boost C++ Libraries: Ticket #11676: difference algorithm returning invalid geometry

version changed

status, milestone changed; resolution set