Strange behavior at difference algorithm

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Strange behavior at difference algorithm

Franz Alt
Hi,

I've written a simple test program using the difference algorithm of geometry. I want to build the difference of two simple rectangle polygons (see attachment input.png).

Regardless of whether I subtract polygon A from B or I subtract B from A I got very strange output polygons (see attachments output1.png and output2.png).

I've tested with Boost 1.56, 1.57 and the beta of 1.58. All versions lead to the same results.

Does someone know what is wrong here?

Thanks

Franz

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

output1.png (34K) Download Attachment
output2.png (30K) Download Attachment
input.png (32K) Download Attachment
difference.cpp (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior at difference algorithm

Adam Wulkiewicz
Hi,

Franz Alt wrote:

> Hi,
>
> I've written a simple test program using the difference algorithm of
> geometry. I want to build the difference of two simple rectangle
> polygons (see attachment input.png).
>
> Regardless of whether I subtract polygon A from B or I subtract B from
> A I got very strange output polygons (see attachments output1.png and
> output2.png).
>
> I've tested with Boost 1.56, 1.57 and the beta of 1.58. All versions
> lead to the same results.
>
> Does someone know what is wrong here?
Which compiler exactly are you using and on which platform?
What flags were passed into the compiler?
In particular, was optimization enabled?

I get the correct results (attached) on windows msvc12, mingw4.9.1 and
linux gcc 4.8.2.
Using latest develop and 1.57 (though I tested the latter only on msvc12).

The attached svg files were generated with bg::svg_mapper
(http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/io/svg/svg_mapper.html).
In the file green_output2.svg there is green and output2[0] from your
code so (blue \ green). In the output1_blue.svg output1[0] (green \
blue) and blue.

What's the output of your program? For me it's:

polygon #0: (15802,253.976) (15943,254) (15943,-1485) (15802,-1485)
(15802,253.976)
polygon #1: (-7901,250.024) (-7901,-1485) (-8042,-1485) (-8042,250)
(-7901,250.024)
----
polygon #0: (-7901,250.024) (-7901,529) (15802,544) (15802,253.976)
(-7901,250.024)

<tldr>

Btw, you can use bg::wkt(), there is no need to manually print
coordinates (see:
http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/io/wkt/wkt.html).
E.g. this:

   namespace bg = boost::geometry;
   std::cout << "green: " << bg::wkt(green) << std::endl;
   std::cout << "blue: " << bg::wkt(blue) << std::endl;
   std::cout << "output1: " << bg::wkt(output1[0]) << std::endl;
   std::cout << "output2: " << bg::wkt(output2[0]) << std::endl;

prints:

green: POLYGON((-8042 -1485,-8042 250,-8042 250,15943 254,15943
-1485,-8042 -1485))
blue: POLYGON((-7901 -1485,-7901 529,-7901 529,15802 544,15802
-1485,-7901 -1485))
output1: POLYGON((15802 253.976,15943 254,15943 -1485,15802 -1485,15802
253.976))
output2: POLYGON((-7901 250.024,-7901 529,15802 544,15802 253.976,-7901
250.024))

Instead of std::vector<polygon> you could use
bg::multi_polygon<polygon>. Then it'd be handled by wkt() or svg_mapper
automatically.

</tldr>

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

green_blue.svg (862 bytes) Download Attachment
green_output2.svg (854 bytes) Download Attachment
output1_blue.svg (862 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior at difference algorithm

Franz Alt
Hi Adam,

I think I've found a little bug in my test program. My polygon type using double types. With double polygon all results are fine. The problems I've had was with polygons of integer types.

  typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<int> > polygon;

I've tested again on linux with gcc 4.8.1, gcc 4.9.2 and clang 3.5.0 with and without optimization (-O2) in c++11 and c++14 mode. With polygons of integer type the outputs looking strange like in my original mail.

BTW: Thanks for your information about bg::wkt(..) and bg::svg_mapper(..).

Thanks

Franz


2015-03-17 15:38 GMT+01:00 Adam Wulkiewicz <[hidden email]>:
Hi,


Franz Alt wrote:
Hi,

I've written a simple test program using the difference algorithm of geometry. I want to build the difference of two simple rectangle polygons (see attachment input.png).

Regardless of whether I subtract polygon A from B or I subtract B from A I got very strange output polygons (see attachments output1.png and output2.png).

I've tested with Boost 1.56, 1.57 and the beta of 1.58. All versions lead to the same results.

Does someone know what is wrong here?

Which compiler exactly are you using and on which platform?
What flags were passed into the compiler?
In particular, was optimization enabled?

I get the correct results (attached) on windows msvc12, mingw4.9.1 and linux gcc 4.8.2.
Using latest develop and 1.57 (though I tested the latter only on msvc12).

The attached svg files were generated with bg::svg_mapper (http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/io/svg/svg_mapper.html).
In the file green_output2.svg there is green and output2[0] from your code so (blue \ green). In the output1_blue.svg output1[0] (green \ blue) and blue.

What's the output of your program? For me it's:

polygon #0: (15802,253.976) (15943,254) (15943,-1485) (15802,-1485) (15802,253.976)
polygon #1: (-7901,250.024) (-7901,-1485) (-8042,-1485) (-8042,250) (-7901,250.024)
----
polygon #0: (-7901,250.024) (-7901,529) (15802,544) (15802,253.976) (-7901,250.024)

<tldr>

Btw, you can use bg::wkt(), there is no need to manually print coordinates (see: http://www.boost.org/doc/libs/1_57_0/libs/geometry/doc/html/geometry/reference/io/wkt/wkt.html).
E.g. this:

  namespace bg = boost::geometry;
  std::cout << "green: " << bg::wkt(green) << std::endl;
  std::cout << "blue: " << bg::wkt(blue) << std::endl;
  std::cout << "output1: " << bg::wkt(output1[0]) << std::endl;
  std::cout << "output2: " << bg::wkt(output2[0]) << std::endl;

prints:

green: POLYGON((-8042 -1485,-8042 250,-8042 250,15943 254,15943 -1485,-8042 -1485))
blue: POLYGON((-7901 -1485,-7901 529,-7901 529,15802 544,15802 -1485,-7901 -1485))
output1: POLYGON((15802 253.976,15943 254,15943 -1485,15802 -1485,15802 253.976))
output2: POLYGON((-7901 250.024,-7901 529,15802 544,15802 253.976,-7901 250.024))

Instead of std::vector<polygon> you could use bg::multi_polygon<polygon>. Then it'd be handled by wkt() or svg_mapper automatically.

</tldr>

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior at difference algorithm

Adam Wulkiewicz
Hi Franz,

Franz Alt wrote:

> Hi Adam,
>
> I think I've found a little bug in my test program. My polygon type
> using double types. With double polygon all results are fine. The
> problems I've had was with polygons of integer types.
>
>   typedef
> boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<int>
> > polygon;
>
> I've tested again on linux with gcc 4.8.1, gcc 4.9.2 and clang 3.5.0
> with and without optimization (-O2) in c++11 and c++14 mode. With
> polygons of integer type the outputs looking strange like in my
> original mail.
>
> BTW: Thanks for your information about bg::wkt(..) and bg::svg_mapper(..).

I can reproduce the problem using int coordinate type.
This is not a bug in your program, the library should work with integral
coordinate types. Though indeed switching e.g. to double could be a
workaround.
I created a ticket: https://svn.boost.org/trac/boost/ticket/11121
Thanks for testing and the info about the problem!

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry