Problems performing boolean operations on polygons with shared edges

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

Problems performing boolean operations on polygons with shared edges

Oleg Evseev
Hello,

I'm trying to use boost geometry to build vehicle ongoing path of constant width with self intersections calculations.
Faced problems with result of boolean operations on polygons (multipolygons).

Here my path polygon on some step (more precisely multipolygon in boost geometry):
https://pp.vk.me/c631319/v631319687/1effe/gQOBvWUNJRM.jpg

On every step I use two points x,y (floats) - left and right offseted by half of constant width from current vehicle location. Let's call x-y line a segment.

When location of vehicle is updated, I construct appended mpolygon using old x,y point and new ones and firstly intersect it with path mpolygon, and then union_ them (so path mpolygon gets longer).

Sometimes (especially for large enough width values) there can be intersection of new segment with previous. In that cases I construct appended mpolygon as two polygons using calculated intersection point with bg::intersection of two segments.
See the picture: https://pp.vk.me/c631319/v631319687/1f03a/elt4y5KSfSM.jpg

And when I union_ it with path mpolygon there is first sign of a problem:
https://pp.vk.me/c631319/v631319687/1f012/2e1MycdOkB8.jpg
result is a two polygons within mpolygon, not the one as I expected. It appears not always, but quite often.

Next step, and again intersection of new segment with previous, and again two polygons in appended mpolygon
This almost zero areas can be part of outer ring of one polygon, or can be a separate polygon in mpolygon within another biggest one (which brakes mpolygon model's rule).

I suppose this is in the end cause this overlay invalid input exceptions when performing intersection or union_ with such mpolygon.

Thinking that problem is in the floating point inaccuracy (that maybe calculates slightly different intersection point of polygons with shared edge when performing union_ ), I even trying to solve this by inserting intersection point of segments in outer ring of current path polygon before doing union_. It slightly reduces overlay invalid input exceptions when perform intersection or union_, but not solve problem completely.

If there any solutions of such problems?

Thank you very much in advance for help.

Kind regards,
Oleg Evseev

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

Re: Problems performing boolean operations on polygons with shared edges

Barend
Hi Oleg,

Op 10-4-2016 om 11:13 schreef Oleg Evseev:
Hello,

I'm trying to use boost geometry to build vehicle ongoing path of constant width with self intersections calculations.
Faced problems with result of boolean operations on polygons (multipolygons).

Here my path polygon on some step (more precisely multipolygon in boost geometry):
https://pp.vk.me/c631319/v631319687/1effe/gQOBvWUNJRM.jpg

On every step I use two points x,y (floats) - left and right offseted by half of constant width from current vehicle location. Let's call x-y line a segment.

When location of vehicle is updated, I construct appended mpolygon using old x,y point and new ones and firstly intersect it with path mpolygon, and then union_ them (so path mpolygon gets longer).

Sometimes (especially for large enough width values) there can be intersection of new segment with previous. In that cases I construct appended mpolygon as two polygons using calculated intersection point with bg::intersection of two segments.
See the picture: https://pp.vk.me/c631319/v631319687/1f03a/elt4y5KSfSM.jpg

And when I union_ it with path mpolygon there is first sign of a problem:
https://pp.vk.me/c631319/v631319687/1f012/2e1MycdOkB8.jpg
result is a two polygons within mpolygon, not the one as I expected. It appears not always, but quite often.

Next step, and again intersection of new segment with previous, and again two polygons in appended mpolygon
This almost zero areas can be part of outer ring of one polygon, or can be a separate polygon in mpolygon within another biggest one (which brakes mpolygon model's rule).

I suppose this is in the end cause this overlay invalid input exceptions when performing intersection or union_ with such mpolygon.

Thinking that problem is in the floating point inaccuracy (that maybe calculates slightly different intersection point of polygons with shared edge when performing union_ ), I even trying to solve this by inserting intersection point of segments in outer ring of current path polygon before doing union_. It slightly reduces overlay invalid input exceptions when perform intersection or union_, but not solve problem completely.

If there any solutions of such problems?

First, the upcoming 1.61 release will have changes in overlay. Please check there if the problem still appears.

Second, the JPG's are illustrative, but hard to reproduce the problem. Could you file a ticket with the WKT representations of two polygons where the union fails? Tickets can be created here:
https://svn.boost.org/trac/boost/newticket

WKT can easily be generated with the library using std::cout << boost::geometry::wkt(input1), etc

Thanks, Barend



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

Re: Problems performing boolean operations on polygons with shared edges

Oleg Evseev
> First, the upcoming 1.61 release will have changes in overlay. Please check there if the problem still appears.

Ok, I will try it, thank you! (Forgot to mention, but I think you had understand that I'm using 1.60.0 release)

> Second, the JPG's are illustrative, but hard to reproduce the problem. Could you file a ticket with the WKT representations of two polygons where the union fails?

I create ticket https://svn.boost.org/trac/boost/ticket/12118

> WKT can easily be generated with the library using std::cout << boost::geometry::wkt(input1), etc

I used boost::geometry::dsv before, WKT return floats with more decimals, but not enough, points that enclose those "almost zero areas" are the same, so that area is totally empty, not "almost" (it is just an edge).
Is there any way to print floats in WKT representation with more precision?

I wrote in the ticket, but want to repeat here:
I forgot to mention that despite the fact that I use same initial data (vehicle path) every program restart, boost geometry union_ makes described problems not in same places.
So WKT representation in the ticket different from pictures in previous post.

https://pp.vk.me/c631319/v631319687/1f012/2e1MycdOkB8.jpg now in last program run is what it should to be - only one polygon: https://pp.vk.me/c633617/v633617687/1cacb/mI45Se8H4OI.jpg

Appended mpolygon is https://pp.vk.me/c633617/v633617687/1cab7/r_7Ep30w_jc.jpg
And union result now is https://pp.vk.me/c633617/v633617687/1cac1/bc2qTKY-8Bs.jpg

Thanks, Oleg


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

Re: Problems performing boolean operations on polygons with shared edges

Barend
Hi Oleg,

Op 10-4-2016 om 22:48 schreef Oleg Evseev:

> > First, the upcoming 1.61 release will have changes in overlay.
> Please check there if the problem still appears.
>
> Ok, I will try it, thank you! (Forgot to mention, but I think you had
> understand that I'm using 1.60.0 release)
>
> > Second, the JPG's are illustrative, but hard to reproduce the
> problem. Could you file a ticket with the WKT representations of two
> polygons where the union fails?
>
> I create ticket https://svn.boost.org/trac/boost/ticket/12118

Thanks

>
> > WKT can easily be generated with the library using std::cout <<
> boost::geometry::wkt(input1), etc
>
> I used boost::geometry::dsv before, WKT return floats with more
> decimals, but not enough, points that enclose those "almost zero
> areas" are the same, so that area is totally empty, not "almost" (it
> is just an edge).
> Is there any way to print floats in WKT representation with more
> precision?

Sure, you can use the normal way, std::setprecision(20) for example,
followed by the wkt.


>
> I wrote in the ticket, but want to repeat here:
> I forgot to mention that despite the fact that I use same initial data
> (vehicle path) every program restart, boost geometry union_ makes
> described problems not in same places.
> So WKT representation in the ticket different from pictures in
> previous post.
>
> https://pp.vk.me/c631319/v631319687/1f012/2e1MycdOkB8.jpg now in last
> program run is what it should to be - only one polygon:
> https://pp.vk.me/c633617/v633617687/1cacb/mI45Se8H4OI.jpg
>
> Appended mpolygon is
> https://pp.vk.me/c633617/v633617687/1cab7/r_7Ep30w_jc.jpg
> And union result now is
> https://pp.vk.me/c633617/v633617687/1cac1/bc2qTKY-8Bs.jpg

OK, I will look at the ticket later

Regards, Barend


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

Re: Problems performing boolean operations on polygons with shared edges

Adam Wulkiewicz
Barend Gehrels wrote:

>
>>
>> > WKT can easily be generated with the library using std::cout <<
>> boost::geometry::wkt(input1), etc
>>
>> I used boost::geometry::dsv before, WKT return floats with more
>> decimals, but not enough, points that enclose those "almost zero
>> areas" are the same, so that area is totally empty, not "almost" (it
>> is just an edge).
>> Is there any way to print floats in WKT representation with more
>> precision?
>
> Sure, you can use the normal way, std::setprecision(20) for example,
> followed by the wkt.

and std::fixed if needed, so:

std::cout << std::setprecision(20) << std::fixed << bg::wkt(g) << std::endl;

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

Re: Problems performing boolean operations on polygons with shared edges

Oleg Evseev
> and std::fixed if needed, so:
> std::cout << std::setprecision(20) << std::fixed << bg::wkt(g) << std::endl;

Thank you, Barend and Adam!

Barend, I've added WKT representation with greater precision to my ticket https://svn.boost.org/trac/boost/ticket/12118

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

Re: Problems performing boolean operations on polygons with shared edges

Oleg Evseev
Hi, Barend!

I've tried to use boost 1.61.0 beta for my case. And instead of getting problems with zero areas, I'm getting really wrong result - union ignore one of the mpolygons (without exceptions). I created ticket with WKT https://svn.boost.org/trac/boost/ticket/12125

Illustration: https://s16.postimg.org/9wcp31ik5/union+1.61.0+bug.png
appended mpolygon (the red one - two trinangles) is ignored. union result is equal to current path (the yellow one - two trinangles)

Maybe this is caused by the shared point of two trinangels in one multipolygon?


2016-04-11 1:25 GMT+03:00 Oleg Evseev <[hidden email]>:
> and std::fixed if needed, so:
> std::cout << std::setprecision(20) << std::fixed << bg::wkt(g) << std::endl;

Thank you, Barend and Adam!

Barend, I've added WKT representation with greater precision to my ticket https://svn.boost.org/trac/boost/ticket/12118



--
С Уважением,
Евсеев Олег.

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

Re: Problems performing boolean operations on polygons with shared edges

Barend
Hi Oleg,

Op 14-4-2016 om 0:54 schreef Oleg Evseev:

> Hi, Barend!
>
> I've tried to use boost 1.61.0 beta for my case. And instead of
> getting problems with zero areas, I'm getting really wrong result -
> union ignore one of the mpolygons (without exceptions). I created
> ticket with WKT https://svn.boost.org/trac/boost/ticket/12125
>
> Illustration: https://s16.postimg.org/9wcp31ik5/union+1.61.0+bug.png
> appended mpolygon (the red one - two trinangles) is ignored. union
> result is equal to current path (the yellow one - two trinangles)
>
> Maybe this is caused by the shared point of two trinangels in one
> multipolygon?
>

Thanks for the reports. It is indeed not solved yet. I updated the
tickets. It is caused somehow by the precision and need some further
study. We plan to change the details of the implementation w.r.t.
precision/rescaling for one of the coming versions. Hopefully asap of
course, but these things take a longer time.

Regards, Barend

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

Re: Problems performing boolean operations on polygons with shared edges

Oleg Evseev
Hi, Barend

Glad to hear that! I'll be waiting for changes.
Thank you very much for all your efforts in creating excelent library

Best regards, Oleg

2016-04-20 18:26 GMT+03:00 Barend Gehrels <[hidden email]>:
Hi Oleg,

Op 14-4-2016 om 0:54 schreef Oleg Evseev:
Hi, Barend!

I've tried to use boost 1.61.0 beta for my case. And instead of getting problems with zero areas, I'm getting really wrong result - union ignore one of the mpolygons (without exceptions). I created ticket with WKT https://svn.boost.org/trac/boost/ticket/12125

Illustration: https://s16.postimg.org/9wcp31ik5/union+1.61.0+bug.png
appended mpolygon (the red one - two trinangles) is ignored. union result is equal to current path (the yellow one - two trinangles)

Maybe this is caused by the shared point of two trinangels in one multipolygon?


Thanks for the reports. It is indeed not solved yet. I updated the tickets. It is caused somehow by the precision and need some further study. We plan to change the details of the implementation w.r.t. precision/rescaling for one of the coming versions. Hopefully asap of course, but these things take a longer time.

Regards, Barend


_______________________________________________
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: Problems performing boolean operations on polygons with shared edges

Oleg Evseev
Hi, Barend!

Is there a chance that those issues with performing boolean operations on polygons with shared edges will be fixed in 1.63?

Thanks!

Best regards, Oleg.

2016-04-21 14:38 GMT+03:00 Oleg Evseev <[hidden email]>:
Hi, Barend

Glad to hear that! I'll be waiting for changes.
Thank you very much for all your efforts in creating excelent library

Best regards, Oleg

2016-04-20 18:26 GMT+03:00 Barend Gehrels <[hidden email]>:
Hi Oleg,

Op 14-4-2016 om 0:54 schreef Oleg Evseev:
Hi, Barend!

I've tried to use boost 1.61.0 beta for my case. And instead of getting problems with zero areas, I'm getting really wrong result - union ignore one of the mpolygons (without exceptions). I created ticket with WKT https://svn.boost.org/trac/boost/ticket/12125

Illustration: https://s16.postimg.org/9wcp31ik5/union+1.61.0+bug.png
appended mpolygon (the red one - two trinangles) is ignored. union result is equal to current path (the yellow one - two trinangles)

Maybe this is caused by the shared point of two trinangels in one multipolygon?


Thanks for the reports. It is indeed not solved yet. I updated the tickets. It is caused somehow by the precision and need some further study. We plan to change the details of the implementation w.r.t. precision/rescaling for one of the coming versions. Hopefully asap of course, but these things take a longer time.

Regards, Barend


_______________________________________________
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