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

Subject: [ggl] Difference / xor for multi polygons
From: Javier Gonzalez (xaviergonz)
Date: 2011-02-28 15:55:34

On Mon, Feb 28, 2011 at 7:15 PM, Simonson, Lucanus J <
lucanus.j.simonson_at_[hidden]> wrote:

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

Well, I use manhattan and non manhattan polygons really, any shape. Just
that I thought boxes would be a simpler example and test.
The polygons are not used on layout but on "vision and occlusion" I'm afraid
:)
Actually it is working already with GPC (
http://www.cs.man.ac.uk/~toby/alan/software/gpc.html) and Clipper (
http://angusj.com/delphi/clipper.php
>),
but I thought I'd give boost geometry a go to see how well it performed.

>
> 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]> 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 Gehrelshttp://about.me/barendgehrels
>>
>>
>> _______________________________________________
>> ggl mailing list
>> ggl_at_[hidden]
>> http://lists.osgeo.org/mailman/listinfo/ggl
>>
>>
>
> _______________________________________________
> ggl mailing list
> 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/8544d4ab/attachment-0001.html