Re: [Boost-users] [Boost.Polygon] support for polygons with holes

Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-09-05 14:04:51

Paul,

In the  polygon_90_set_concept documentation I have these two functions:

template <typename T>
T& self_intersect(T& polygon_set) Given an object that models polygon_90_set that has self overlapping regions, modifies the argument to contain only the regions of overlap.  O( n log n) runtime complexity and O(n) memory wrt vertices + intersections.  

template <typename T>
T& self_xor(T& polygon_set) Given an object that models polygon_90_set that has self overlapping regions, modifies the argument to contain only the regions that do not overlap.  O( n log n) runtime complexity and O(n) memory wrt vertices + intersections.  

Self intersect gives you all polygon regions with winding number greater than 1.  Self_xor is the gives you the regions with odd winding rule.  You want odd winding rule.  If all you need is manhattan geometry then you just call self-xor.  I don't provide these two functions for arbitrary angle geometry, but it would be reletively easy for me to do so.  It is tricky for you to try to compose what you want out of my documented library interfaces because you need to handle holes within solids within holes (bulls-eye).  If you push all the polygons through property merge

http://www.boost.org/doc/libs/1_47_0/libs/polygon/doc/gtl_property_merge.htm

the result will be a map of sets of polygon ID to polygon set.  Give eah polygon a unique id.  All of the polygon sets in the result of property merge that have an odd number of properties are solid.  The ones with an even number of properties are your holes.  If you want polygons with holes just get the polygon_with_holes out of each polygon set with an odd number of properties in the property merge result.

In the little drawing below we have a bullseye with three concentric rings.  If we give them polygon ids 1, 2 and 3 (from outer to inner), then the result of the property merge is a map with three elements, one with key 1; one with key 1,2 and one with key 1,2,3.  If you get polygons with holes out of sets 1 and 1,2,3 then the one from set 1 will have a hole in it already.  

----------------
|  --------- 1 |
|  | ----- |   |
|  | |1,2| |   |
|  | | ,3| |   |
|  | ----- |   |
|  |       |   |
|  | 1,2   |   |
|  ---------   |
----------------

Note, this method won't give you the odd-winding rule for self intersecting polygons, only if your input polygons are non-self intersecting will it do what you want.  If your polygons are in partial overlap relationships rather than containment relationship then you have unrecoverably lost the information about which is hole and which is solid and odd winding rule will give you garbage results.

Eventually I'd like to add functions for doing the self intersect, self xor and also one that evaluates the non-zero winding rule.  

Regards,
Luke

-----Original Message-----
From: boost-users-bounces_at_[hidden] [mailto:boost-users-bounces_at_[hidden]] On Behalf Of paul delamusica
Sent: Sunday, September 04, 2011 10:40 PM
To: boost-users_at_[hidden]
Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes

In my application, I don't know before hand whether or not holes exist, so I
read everything in as polygon_data. After that, I tried to use view_as<> in
order to convert between these two types of polygons. It doesn't seem to
work. What is the proper way to convert  polygon_data to
polygon_with_holes_data?

Thanks

--
View this message in context: http://boost.2283326.n4.nabble.com/Boost-Polygon-support-for-polygons-with-holes-tp3786010p3790466.html
Sent from the Boost - Users mailing list archive at Nabble.com.
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users