Bug again in boost::geometry::union_

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

Bug again in boost::geometry::union_

yohann.benedic

Hi again,

 

Still working on some stuff with boost::geometry and stumbled upon another bug-like behavior.

Roughly, build two polygons (one outer ring each) check that they intersect, try to union them and end up with nothing (well, checking that they intersect beforehand is not even relevant).

 

Sample code is below

 

void test()

{

  typedef boost::geometry::model::d2::point_xy<double> boostPoint;

  typedef boost::geometry::model::polygon< boostPoint > boostPolygon;

  typedef boost::geometry::model::multi_polygon< boostPolygon > boostPolygons;

  typedef boostPolygon::ring_type boostRing;

 

  // both polygons have very close to zero values because they are actually the result of some previous work

  // the bug disappears if I round them down to zero, or if I shift everything by 10000 (doesn’t work with a +1 shift though).

  boostPolygon p1;

  boost::geometry::append(p1, boostPoint(7,4));

  boost::geometry::append(p1, boostPoint(7,0));

  boost::geometry::append(p1, boostPoint(5,2));

  boost::geometry::append(p1, boostPoint(3,8.5725275940314722e-16));

  boost::geometry::append(p1, boostPoint(-7,8.8817841970012523e-16));

  boost::geometry::append(p1, boostPoint(-7,10));

  boost::geometry::append(p1, boostPoint(0,17));

  boost::geometry::append(p1, boostPoint(4.2862637970157361e-16,17));

  boost::geometry::append(p1, boostPoint(10,17));

  boost::geometry::append(p1, boostPoint(10,7));

  boost::geometry::correct(p1);

 

  boostPolygon p2;

  boost::geometry::append(p2, boostPoint(10,17));

  boost::geometry::append(p2, boostPoint(17,10));

  boost::geometry::append(p2, boostPoint(7,10));

  boost::geometry::append(p2, boostPoint(4.2862637970157361e-16,17));

  boost::geometry::correct(p2);

 

  assert(boost::geometry::intersects(p1,p2));

 

  boostPolygons p_union;

  boost::geometry::union_(p1,p2,p_union);

 

  assert(1,p_union.size()); // this one fails, p_union is empty

 

  return;

}

 

I am using boost 1.54 and vertices xs and yx are extracted from the debugger. I guess using different compiler options might fix this issue. Unlike the bug with equals, I was not able to track the problem down in boost code. Again, I haven’t seem anything in the 1.55 changelog that indicates it is already fixed.

 

How safe is boost::geometry for use in prod. code ? Anyone knws of a big project that relies on it ?

 

Thanks for your time.

Description : http://www.francetelecom.com/sirius/logos_mail/orange_logo.gif

Yohann Bénédic
Wireless Engineering and Propagation
Research Engineer
tel.
+33 384 544 338
[hidden email]

 

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.

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

Re: Bug again in boost::geometry::union_

Barend
Hi Yohann,

[hidden email] wrote On 30-1-2014 17:56:

Hi again,

 

Still working on some stuff with boost::geometry and stumbled upon another bug-like behavior.

Roughly, build two polygons (one outer ring each) check that they intersect, try to union them and end up with nothing (well, checking that they intersect beforehand is not even relevant).

 

 

I am using boost 1.54 and vertices xs and yx are extracted from the debugger. I guess using different compiler options might fix this issue. Unlike the bug with equals, I was not able to track the problem down in boost code. Again, I haven’t seem anything in the 1.55 changelog that indicates it is already fixed.

 


Your problem is fixed in the meantime in a big effort to fix robustness issues for floating point coordinates. This is in git but not yet merged in the development branch. It will be released in 1.56. Version 1.55 indeed still have this problem, I could reproduce it with help of your testcode.

Thanks for your report.

Regards, Barend


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

Re: Bug again in boost::geometry::union_

Hunk
Hello,

Do know when release date is for 1.56 ? Or it is possible to fix this bug with your branch ?
Thanks for your help and your nice work :)

regards
Reply | Threaded
Open this post in threaded view
|

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel
In reply to this post by yohann.benedic
Hi folks,

This is my first post to this mailing list. I've just started to try out Boost::Geometry. My goal is to replace CGAL (slow but robust) with something faster. I'm trying to calculate the boundary polygon of the projection of a triangulated mesh onto the ground plane (see http://stuvel.eu/files/publication/2013-stuvel-occupancy_spaces-poster_mig2013.pdf). For this I need to be able to calculate the union of several thousand triangles in 2D.

My code mostly works, except that sometimes all of a sudden the result of a union_() call is empty, even though the two input-multi-polygons are not, as described in http://boost-geometry.203548.n3.nabble.com/Bug-again-in-boost-geometry-union-td4025831.html

My question is this: what would be the quickest way to get the fixes mentioned in that thread? I have a deadline for a paper this wednesday. If I could get a workaround for this issue before that time that would be awesome, as (when it runs) my Boost::Geometry code is about 6x faster than when I use CGAL!

Kind regards,

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

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,

Sybren A. Stüvel wrote On 8-2-2014 0:11:

> Hi folks,
>
> This is my first post to this mailing list. I've just started to try
> out Boost::Geometry. My goal is to replace CGAL (slow but robust) with
> something faster. I'm trying to calculate the boundary polygon of the
> projection of a triangulated mesh onto the ground plane (see
> http://stuvel.eu/files/publication/2013-stuvel-occupancy_spaces-poster_mig2013.pdf).
> For this I need to be able to calculate the union of several thousand
> triangles in 2D.
>
> My code mostly works, except that sometimes all of a sudden the result
> of a union_() call is empty, even though the two input-multi-polygons
> are not, as described in
> http://boost-geometry.203548.n3.nabble.com/Bug-again-in-boost-geometry-union-td4025831.html
>
> My question is this: what would be the quickest way to get the fixes
> mentioned in that thread? I have a deadline for a paper this
> wednesday. If I could get a workaround for this issue before that time
> that would be awesome, as (when it runs) my Boost::Geometry code is
> about 6x faster than when I use CGAL!


That is very good news! Thanks for your info and welcome to the list.

If you need it that soon, you need to use my git-branch where these
problems have been fixed. It is not completely ready so I hope
everything will work for you. If not, please report it such that I can
at least have a quick look (though Wednesday is soon of course).

This is the branch:
https://github.com/boostorg/geometry/tree/rescale_to_integer

I hope to merge it to the development-branch soon.

Regards, Barend

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

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel
On 8 February 2014 13:39, Barend Gehrels <[hidden email]> wrote:
welcome to the list.

Thanks!
 
If you need it that soon, you need to use my git-branch where these problems have been fixed. It is not completely ready so I hope everything will work for you. If not, please report it such that I can at least have a quick look (though Wednesday is soon of course).

I've cloned your branch, but hit a snag. First, handle_tangencies.hpp needed a little change. I removed this line:

#include <boost/geometry/policies/robustness/rescale.hpp>

as in your last commit you split that file into three other files, which are (indirectly) included anyway on the next line, as it includes zoom_to_robust.hpp.
Now I get this error:

c:\workspace\geometry\include\boost/geometry/policies/robustness/zoom_to_robust.hpp(425): error C2338: boost::is_same < typename geometry::tag<Point>::type, geometry::point_tag >::type::value
          c:\workspace\geometry\include\boost/geometry/policies/robustness/zoom_to_robust.hpp(433) : see reference to class template instantiation 'boost::geometry::rescale_policy_type<Point>' being compiled

I get this error as soon as I #include something from Boost::Geometry; my test code consisted of the single line:

#include <boost/geometry/algorithms/union.hpp>

To make sure I'm using the code in your branch, I've renamed my .../dependencies/boost_1_55_0/boost/geometry directory to "geometry-moved-out-of-the-way", and added your branch at "c:/workspace/geometry/include" to the include file search paths.

Thanks for any help you can give me.

PS: I see you live in Amsterdam, so do I, so perhaps there are easier ways to communicate than this list ;-)

Best,

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

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,


Sybren A. Stüvel wrote On 12-2-2014 11:32:
On 8 February 2014 13:39, Barend Gehrels <[hidden email]> wrote:
welcome to the list.

Thanks!
 
If you need it that soon, you need to use my git-branch where these problems have been fixed. It is not completely ready so I hope everything will work for you. If not, please report it such that I can at least have a quick look (though Wednesday is soon of course).

I've cloned your branch, but hit a snag. First, handle_tangencies.hpp needed a little change. I removed this line:

#include <boost/geometry/policies/robustness/rescale.hpp>

as in your last commit you split that file into three other files, which are (indirectly) included anyway on the next line, as it includes zoom_to_robust.hpp.


Sure - I did that yesterday evening. Indeed the handle_tangencies issue was not yet solved and not submitted, sorry for the inconvenience. It is fixed now.
Please check - I use gcc, I did not check yet on MSVC

Now I get this error:

c:\workspace\geometry\include\boost/geometry/policies/robustness/zoom_to_robust.hpp(425): error C2338: boost::is_same < typename geometry::tag<Point>::type, geometry::point_tag >::type::value
          c:\workspace\geometry\include\boost/geometry/policies/robustness/zoom_to_robust.hpp(433) : see reference to class template instantiation 'boost::geometry::rescale_policy_type<Point>' being compiled

I get this error as soon as I #include something from Boost::Geometry; my test code consisted of the single line:

#include <boost/geometry/algorithms/union.hpp>

To make sure I'm using the code in your branch, I've renamed my .../dependencies/boost_1_55_0/boost/geometry directory to "geometry-moved-out-of-the-way", and added your branch at "c:/workspace/geometry/include" to the include file search paths.

Thanks for any help you can give me.

So please update.



PS: I see you live in Amsterdam, so do I, so perhaps there are easier ways to communicate than this list ;-)

OK - nice, that can be convenient indeed.

Success with your presentation.

Regards, Barend


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

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel
On 12 February 2014 12:04, Barend Gehrels <[hidden email]> wrote:
Sure - I did that yesterday evening. Indeed the handle_tangencies issue was not yet solved and not submitted, sorry for the inconvenience. It is fixed now.

I've updated & checked, but the is_same static assert still fails with the same error I mailed earlier.
 
Please check - I use gcc, I did not check yet on MSVC

Unfortunately at this moment I can't use anything but MSVC 2010 :(

--

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

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,

Sybren A. Stüvel wrote On 12-2-2014 12:19:
On 12 February 2014 12:04, Barend Gehrels <[hidden email]> wrote:
Sure - I did that yesterday evening. Indeed the handle_tangencies issue was not yet solved and not submitted, sorry for the inconvenience. It is fixed now.

I've updated & checked, but the is_same static assert still fails with the same error I mailed earlier.
 
Please check - I use gcc, I did not check yet on MSVC

Unfortunately at this moment I can't use anything but MSVC 2010 :(


OK - I checked that compiler too, and fortunately there were only 2 small issues. Should be fixed now. (Note, I disabled that static assertion for MSVC, I will find out later why that causes problems now for MSVC only)

Can you try again?

Regards, Barend


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

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel

On 12 February 2014 12:57, Barend Gehrels <[hidden email]> wrote:
OK - I checked that compiler too, and fortunately there were only 2 small issues. Should be fixed now. (Note, I disabled that static assertion for MSVC, I will find out later why that causes problems now for MSVC only)

Can you try again?

There we go, now it compiles. Still gives problems, though, with the union_() function. It prints "Warning: d=0" to stdout/err. I've attached a SVG file that contains the two input multi-polygons (in red & green) and the resulting output (in blue). You can clearly see that the blue polygon has a vertex too many, in its interior.

Best,

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

self-intersections.svg (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,

Sybren A. Stüvel wrote On 12-2-2014 13:28:

On 12 February 2014 12:57, Barend Gehrels <[hidden email]> wrote:
OK - I checked that compiler too, and fortunately there were only 2 small issues. Should be fixed now. (Note, I disabled that static assertion for MSVC, I will find out later why that causes problems now for MSVC only)

Can you try again?

There we go, now it compiles. Still gives problems, though, with the union_() function. It prints "Warning: d=0" to stdout/err.

Good. That warning can be ignored. It's a (more or less personal) development branch. Please comment it in cart_intersect.hpp if you want to get rid of it. I will fix this but it is, for me, diagnostic information

I've attached a SVG file that contains the two input multi-polygons (in red & green) and the resulting output (in blue). You can clearly see that the blue polygon has a vertex too many, in its interior.

Ah, that is a known problematic side-effect. That has to be fixed too but of course, if you need it today, or even somewhere this week, I cannot do that.

You can try one more thing: please define BOOST_GEOMETRY_NO_ROBUSTNESS. It will than skip all rescaling-to-integer-for-robustness code. That sounds a bit weird, because this thread was to fix that. But besides the rescaling more enhancements have been made, so it might be that your code then runs OK. However, I cannot predict that, there are also cases which really need this rescaling. So you can try how it looks.

Besides that, maybe even better, you can try to call the function "geometry::remove_spikes" on your output. It hopefully will remove all spikes which are generated.

Finally, could you also send me the WKT's of your input, for me to check that generated internal spike (as we call it)?

Thanks, Barend




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

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel
Hi Barend,

On 12 February 2014 13:46, Barend Gehrels <[hidden email]> wrote:
Good. That warning can be ignored. It's a (more or less personal) development branch. Please comment it in cart_intersect.hpp if you want to get rid of it. I will fix this but it is, for me, diagnostic information

I suspected as much. Didn't want to keep any diagnostic info to myself ;-)
 
Ah, that is a known problematic side-effect. That has to be fixed too but of course, if you need it today, or even somewhere this week, I cannot do that.

Alas, then I'll have to wait a bit more.
 
You can try one more thing: please define BOOST_GEOMETRY_NO_ROBUSTNESS. It will than skip all rescaling-to-integer-for-robustness code. That sounds a bit weird, because this thread was to fix that. But besides the rescaling more enhancements have been made, so it might be that your code then runs OK. However, I cannot predict that, there are also cases which really need this rescaling. So you can try how it looks.

Unfortunately, that doesn't help. Then I get an empty result at some point - see the attached "exception.svg" file.
 
Besides that, maybe even better, you can try to call the function "geometry::remove_spikes" on your output. It hopefully will remove all spikes which are generated.

It appears that it doesn't, the spike is still there. I tried this without defining BOOST_GEOMETRY_NO_ROBUSTNESS, as the empty result I described occurs sooner than the generation of any spike.
 
Finally, could you also send me the WKT's of your input, for me to check that generated internal spike (as we call it)?

I have attached the two inputs (poly0/1) and the result that I get from the union.

--

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

exception.svg (1K) Download Attachment
spike-poly1.wkt (316 bytes) Download Attachment
spike-output.wkt (500 bytes) Download Attachment
spike-poly0.wkt (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,

Sybren A. Stüvel wrote On 12-2-2014 15:10:
Hi Barend,

On 12 February 2014 13:46, Barend Gehrels <[hidden email]> wrote:
Good. That warning can be ignored. It's a (more or less personal) development branch. Please comment it in cart_intersect.hpp if you want to get rid of it. I will fix this but it is, for me, diagnostic information

I suspected as much. Didn't want to keep any diagnostic info to myself ;-)
 
Ah, that is a known problematic side-effect. That has to be fixed too but of course, if you need it today, or even somewhere this week, I cannot do that.

Alas, then I'll have to wait a bit more.
 
You can try one more thing: please define BOOST_GEOMETRY_NO_ROBUSTNESS. It will than skip all rescaling-to-integer-for-robustness code. That sounds a bit weird, because this thread was to fix that. But besides the rescaling more enhancements have been made, so it might be that your code then runs OK. However, I cannot predict that, there are also cases which really need this rescaling. So you can try how it looks.

Unfortunately, that doesn't help. Then I get an empty result at some point - see the attached "exception.svg" file.
 
Besides that, maybe even better, you can try to call the function "geometry::remove_spikes" on your output. It hopefully will remove all spikes which are generated.

It appears that it doesn't, the spike is still there. I tried this without defining BOOST_GEOMETRY_NO_ROBUSTNESS, as the empty result I described occurs sooner than the generation of any spike.

That is right.

 
Finally, could you also send me the WKT's of your input, for me to check that generated internal spike (as we call it)?

I have attached the two inputs (poly0/1) and the result that I get from the union.

Thanks for the info and files. OK, so alas that spike is there for some time, sorry for the inconvenience.  I will mail if this is fixed.

Regards, Barend


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

Re: Bug again in boost::geometry::union_

Sybren A. Stüvel
Hi Berend,

On 12 February 2014 16:09, Barend Gehrels <[hidden email]> wrote:
OK, so alas that spike is there for some time, sorry for the inconvenience.  I will mail if this is fixed.

Thanks for all your help so far.


Best,

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

Re: Bug again in boost::geometry::union_

Barend
Hi Sybren,

Sybren A. Stüvel wrote On 12-2-2014 16:16:
Hi Berend,

On 12 February 2014 16:09, Barend Gehrels <[hidden email]> wrote:
OK, so alas that spike is there for some time, sorry for the inconvenience.  I will mail if this is fixed.

Thanks for all your help so far.

You are welcome.

About the WKT's you mailed, I cannot reproduce the problem with this. Are you sure you have mailed two input's (0/1) because one of them (or actually both) seems already output (with spikey features), and one of them is completely inside the other one...

Maybe you can also generate more decimals because that might be another reason.

Regards, Barend




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