Geometry Boost List: [ggl] Difference / xor for multi polygons

Subject: [ggl] Difference / xor for multi polygons
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-02-28 13:16:37

Javier,

These are manhattan polygons.  Are you by chance working with layout data in your application?

Barend,

I would strongly suggest that the Boost.Polygon library be used as a means to facilitate testing of the Boost.Geometry boolean operations.  The way to do this is quite simple:

write a random multi polygon generator that creates small manhattan rectangles at random locations with integer coordinates and then perform operations such as intersection and union on them using both Boost.Polygon manhattan algorithm and Boost.Geometry then use Boost.Polygon to XOR the results and compare for equivalence.

Any difference can safely be assume to be a bug in the Boost.Geometry algorithm.  It would be best to do this type of testing and fix any issues before the release of the library.

Regards,
Luke

________________________________
From: ggl-bounces_at_[hidden] [mailto:ggl-bounces_at_[hidden]] On Behalf Of Javier Gonzalez
Sent: Sunday, February 27, 2011 10:58 AM
To: Generic Geometry Library Discussion
Subject: Re: [ggl] Difference / xor for multi polygons

Ok thanks, that worked.

However now I'm facing another problem with the difference combination.

Given (in cartesian coords)

poly1:
ext ring = -2, 2   2002, 2   2002, -2002   -2, -2002   -2, 2 (clockwise)
inner ring = 0, 0    0, -2000   2000,-2000   2000, 0   0, 0  (counter clockwise)

poly2:
ext ring = 560, -360   600, -360   600, -400   560, -400   560, -360 (clockwise)

The difference between them is
exterior ring = -2, 2   2002, 2   2002, -2002   -2, -2002   -2, 2 (clockwise)
with no interior ring

Isn't this obviously wrong?

Actually always I try to make a difference between a holed box and a box within it I get the whole external unholed box as result :-S

PS: I'm using the difference_inserter to do the combination, both the new version for multi polygons and the old version for polygons give the same result.
Ah, and latest dev version of boost geometry.

On Sun, Feb 27, 2011 at 11:48 AM, Barend Gehrels <barend_at_[hidden]<mailto:barend_at_[hidden]>> wrote:
Hi Javier,

On 27-2-2011 1:58, Javier Gonzalez wrote:

Unfortunately now upon compilation of the same code (VS2010), even if I only leave the union inserterer, I get this:

1>  BoostGeometry.cpp
1>Programming\C++ Libraries\boost_1_46_0\boost/geometry/core/point_type.hpp(42): error C2664: 'boost::mpl::assertion_failed' : cannot convert parameter 1 from 'boost::mpl::failed ************(__cdecl boost::geometry::traits::point_type<Geometry>::NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE::* ***********)(boost::mpl::assert_::types<T1>)' to 'boost::mpl::assert<false>::type'

I see. This is not caused by the change of yesterday, but by an earlier (and correct) change.

The problematic lines are:
(...) typedef vector<polygon_2d> polygon_2d_list;
(...) static polygon_2d_list Combine(polygon_2d_list const& subjectPoly, polygon_2d_list const& clipPoly, clip_type clipType)
(...)  intersection_inserter<polygon_2d>(subjectPoly, clipPoly, back_inserter(outputPoly));

First a polygonlist is declared but it is not a multi-polygon. For output, using it with the back_inserter, this is OK.

But for input, it should conform to the multi-polygon concept. A vector<polygon> does conform to most of it, but it still needs the tag to note the library "I'm a multi-polygon".

So in the last line it expects a multi-polygon and gets a vector of polygons, and therefore the MPL assertion of point_type goes off.

That MPL assertion is relatively new, but I'm surprised that the code earlier compiled because it needs to assure the multi-polygon concept on several places.

So three solutions possible:
1) change typedef vector<polygon_2d> to multi_polygon<polygon_2d>
2) change Combine from poylgon_2d_list to polygon_2d (but I don't know if that is what you want)
3) add a traits class to register your polygon_2d_list:

namespace boost { namespace geometry { namespace traits
{

template <> struct tag<polygon_2d_list>
{
    typedef multi_polygon_tag type;

};

}}}

I'm using the version from

Subversion repository with source code of Boost Geometry is hosted in the Boost Trunk available at

svn co http://svn.boost.org/svn/boost/trunk/boost/geometry boost-geometry

though I only got the geometry part and used it over the release version of boost 1.46

That should be no problem.

Regards, Barend

--
Barend Gehrels
http://about.me/barendgehrels
_______________________________________________
ggl mailing list
ggl_at_[hidden]<mailto:ggl_at_[hidden]>
http://lists.osgeo.org/mailman/listinfo/ggl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110228/18990d38/attachment.html