
Boost Users : 
Subject: Re: [Boostusers] [Boost.Polygon] support for polygons with holes
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 20110905 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 selfxor. 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 (bullseye). 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 oddwinding rule for self intersecting polygons, only if your input polygons are nonself 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 nonzero winding rule.
Regards,
Luke
Original Message
From: boostusersbounces_at_[hidden] [mailto:boostusersbounces_at_[hidden]] On Behalf Of paul delamusica
Sent: Sunday, September 04, 2011 10:40 PM
To: boostusers_at_[hidden]
Subject: Re: [Boostusers] [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/BoostPolygonsupportforpolygonswithholestp3786010p3790466.html Sent from the Boost  Users mailing list archive at Nabble.com. _______________________________________________ Boostusers mailing list Boostusers_at_[hidden] http://lists.boost.org/mailman/listinfo.cgi/boostusers
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net