difference algorithm returning invalid geometry

[anonymous]

My "tc::geo::polygon" type is actually a multi-polygon, using a polygon type that is based on int, oriented counter-clockwise and open (not closed). Please consider the following example:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((1920 1660,1920 1462,3720 1462,3720 3262,1920 3262,1920 1959,2218 2189,1920 1660),(3718 1561,3360 2233,3718 1957,3718 1561),(2818 2653,2218 2189,2818 3253,3360 2233,2818 2653)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true

tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((1918 2155,1918 1957,2818 2653,3718 1957,3718 2154,2818 3055,1918 2155)))", 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(((2218 2189,1920 1660,1920 1462,3720 1462,3720 3262,1920 3262,1920 2157,2562 2799,2818 3253,3043 2829,3718 2154,3718 1957,3718 1561,3360 2233,3718 1957,3360 2234,3360 2233,2818 2653,2218 2189)))
boost::geometry::is_valid(polygonC); // returns false!

The difference of two valid multi-polygons yields an invalid multi-polygon.

May be related to Ticket #10661 and Ticket #11674.

[vschoech@…]

Sorry for "anonymous". I filed this ticket.

[vschoech@…]

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]

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

[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

[Volker Schöch <vschoech@…>]

Still present in boost 1.66.0.

[Volker Schöch <vschoech@…>]

No longer reproducible in 1.67.0.

[Barend Gehrels]

Thanks for verifying!