[Boost.Polygon] support for polygons with holes
I'm playing around with Boost.Polygon and I'm wondering what functionality is supported for the polygon_with_holes concept. Specifically the boolean operators. For example, can I create a polygon_set with polygon_with_holes. I would like to punch a hole in a polygon and get a polygon with a hole as supposed to a key holed contour. Similarily, when combining the following rectangles: p += rectangle_data<int>(0, 0, 100, 10); p += rectangle_data<int>(90, 0, 100, 100); p += rectangle_data<int>(0, 90, 100, 100); p += rectangle_data<int>(0, 0, 10, 100); I would like to end up with +-----+ | | | +-+ | | | | | | +-+ | | | +-----+ as opposed to +-----+ | | | +-+ | | | | | | +-+ | | | | +---+-+
Bjorn, All functionality is supported for the polygon_with_holes concept. I consider it to be the normal case. All you need to do is create a list or vector of polygon_with_holes_data<int> and use that instead of polygon_data<int> when you get the result out of polygon_set p. Regards, Luke ________________________________ From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Björn Piltz Sent: Friday, September 02, 2011 1:39 AM To: boost-users@lists.boost.org Subject: [Boost-users] [Boost.Polygon] support for polygons with holes I'm playing around with Boost.Polygon and I'm wondering what functionality is supported for the polygon_with_holes concept. Specifically the boolean operators. For example, can I create a polygon_set with polygon_with_holes. I would like to punch a hole in a polygon and get a polygon with a hole as supposed to a key holed contour. Similarily, when combining the following rectangles: p += rectangle_data<int>(0, 0, 100, 10); p += rectangle_data<int>(90, 0, 100, 100); p += rectangle_data<int>(0, 90, 100, 100); p += rectangle_data<int>(0, 0, 10, 100); I would like to end up with +-----+ | | | +-+ | | | | | | +-+ | | | +-----+ as opposed to +-----+ | | | +-+ | | | | | | +-+ | | | | +---+-+
All functionality is supported for the polygon_with_holes concept. I consider it to be the normal case.
Thanks, that's a relief! I use my own containers and I missed that I had to declare polygon_traits as well as polygon_with_holes_traits for my PolygonsWithHoles class. Now things are working like a charm. I'm very happing being able to map Qt's QPolygon to Boost.Polygon since this gives me full rendering capabilities. I do have a couple of issues and I thought I'd let you know. I'm not sure if they are outside the scope of the library, so I'll let you be the judge of that. 1. Is there an easy(and computationally cheaper) way to check if two simple polygons intersect? other than: !boost::polygon::empty(a & b). If not, is such functionality planned? 2. The simplify() algorithm seems to be a bit greedy. I have a hard time thinking up a small example, but I can see it clearly on some larger GIS-datasets. The algorithm starts chipping away at some corner, removing unneeded vertices, but in some cases it doesn't stop until the whole polygon is gone. It seems to me it should work a bit more like Douglas-Peucker: Everytime a point P is removed, creating a line between A and B, all previously removed points between A and B should be checked against the line, and if any of the points end up to far from the line removal of P is rejected The way it works now, the accumulated error can be great. 3. Are there potentially more ways the user can help the library? Right now the user can override polygon_traits<>::winding(), which is otherwise O(N). Couldn't the same be done for area, bounding box and concavity. The bounding box is of course useful for speeding up all boolean operators and knowing concavity speeds up hit tests ( contains(point_type) ) This could be calculated in one sweep. No boiler plate code needed if there would be polygon_default_traits returning winding_unknown, concavity_unknown, etc. Otherwise, like I said before, it works like a charm. Sincerely Björn 2011/9/2 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Bjorn,
All functionality is supported for the polygon_with_holes concept. I consider it to be the normal case. All you need to do is create a list or vector of polygon_with_holes_data<int> and use that instead of polygon_data<int> when you get the result out of polygon_set p.
Regards, Luke ________________________________
From: boost-users-bounces@lists.boost.org [mailto: boost-users-bounces@lists.boost.org] On Behalf Of Björn Piltz Sent: Friday, September 02, 2011 1:39 AM To: boost-users@lists.boost.org Subject: [Boost-users] [Boost.Polygon] support for polygons with holes
I'm playing around with Boost.Polygon and I'm wondering what functionality is supported for the polygon_with_holes concept. Specifically the boolean operators.
For example, can I create a polygon_set with polygon_with_holes. I would like to punch a hole in a polygon and get a polygon with a hole as supposed to a key holed contour. Similarily, when combining the following rectangles:
p += rectangle_data<int>(0, 0, 100, 10); p += rectangle_data<int>(90, 0, 100, 100); p += rectangle_data<int>(0, 90, 100, 100); p += rectangle_data<int>(0, 0, 10, 100);
I would like to end up with +-----+ | | | +-+ | | | | | | +-+ | | | +-----+ as opposed to +-----+ | | | +-+ | | | | | | +-+ | | | | +---+-+ _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Björn Piltz wrote:
All functionality is supported for the polygon_with_holes concept. I consider it to be the normal case.
Thanks, that's a relief! I use my own containers and I missed that I had to declare polygon_traits as well as polygon_with_holes_traits for my PolygonsWithHoles class. Now things are working like a charm. I'm very happing being able to map Qt's QPolygon to Boost.Polygon since this gives me full rendering capabilities.
I'm glad to hear it. For some reason this email ended up misidentified as spam and went to my Junk E-mail folder, so please excuse the lateness of my response.
I do have a couple of issues and I thought I'd let you know. I'm not sure if they are outside the scope of the library, so I'll let you be the judge of that.
1. Is there an easy(and computationally cheaper) way to check if two simple polygons intersect? other than: !boost::polygon::empty(a & b). If not, is such functionality planned?
You should check if their bounding boxes intersect first and then do the expensive check only if there is intersection between the bounding boxes.
2. The simplify() algorithm seems to be a bit greedy. I have a hard time thinking up a small example, but I can see it clearly on some larger GIS-datasets. The algorithm starts chipping away at some corner, removing unneeded vertices, but in some cases it doesn't stop until the whole polygon is gone. It seems to me it should work a bit more like Douglas-Peucker:
Everytime a point P is removed, creating a line between A and B, all previously removed points between A and B should be checked against the line, and if any of the points end up to far from the line removal of P is rejected
The way it works now, the accumulated error can be great.
Yes, I see your point. In my testing on CAM data that contained a large number of nearly colinear line segments as an artifact of meshing in addition to the sharp angles of man made geometry the operation seemed to be performing well removing the artifact vertices but retaining the ones that were desired features of the figure, however, I can imagine that for GIS data things could turn out much different since all vertices would be qualitatively similar. The way I implemented the simplify operation the threshold is interpreted as a lower bound instead of an upper bound, which makes the result unpredictable.
3. Are there potentially more ways the user can help the library? Right now the user can override polygon_traits<>::winding(), which is otherwise O(N). Couldn't the same be done for area, bounding box and concavity. The bounding box is of course useful for speeding up all boolean operators and knowing concavity speeds up hit tests ( contains(point_type) ) This could be calculated in one sweep. No boiler plate code needed if there would be polygon_default_traits returning winding_unknown, concavity_unknown, etc.
It is easy to imagine a polygon object that caches its area and bounding box. You can override any free function in the library (like area()) by defining your own overload of the function that accepts your type, or partial specialization for your specific type. Frequently the compiler fails to inline the accessor functions for simple data structres like point or rectangle resulting in less-than-zero-cost abstraction. We address this (when benchmarking shows it is a problem) by overloading or partial specialization of the free functions that use the accessors through the traits to instead access the data type directly. I suppose it is possible to define an extended set of traits for many of the free functions that default to the current implementation (similar to winding), but it is hard to know where to draw the line, and it wouldn't be easier for the user than just overloading, but it would be more obvious, but it would be much more work for me. I chose to provide the winding trait because I call winding very frequently, yet it is very common for winding to be a class invariant and known actually at compile time and so have O(0) runtime complexity. Perhaps we can add an example showing how to override free functions for performance.
Otherwise, like I said before, it works like a charm.
I'm very glad to hear it. I made correctness with intuitive and simple to use interfaces my priority. With feedback from the boost community I also cleaned up all the compiler warnings and fixed compatibility issues with the various compilers and versions thereof. Getting the functionality to you was a little like getting a block of cheese through a cheese grater. I had to limit the scope a little and work a lot. Contributions from the community are very welcome, both patches and new features. The simplify algorithm was actually a contributed by a user of the library who had a CAM application. If you would like to contribute a Douglas-Peucker implementation (perhaps you were forced to write your own) I'd be very happy to integrate it, document it and get it into the next release. Thanks, Luke
Ok, here is my D-P implementation: https://bitbucket.org/bjornpiltz/boost_polygon_dp. When I tried to refactor the line-to-point distance calculation from simplify(), I realized it wasn't working correctly. I have replaced it, but I would suggest you have a look at it. All the best Björn 2011/9/8 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Björn Piltz wrote:
All functionality is supported for the polygon_with_holes concept. I consider it to be the normal case.
Thanks, that's a relief! I use my own containers and I missed that I had to declare polygon_traits as well as polygon_with_holes_traits for my PolygonsWithHoles class. Now things are working like a charm. I'm very happing being able to map Qt's QPolygon to Boost.Polygon since this gives me full rendering capabilities.
I'm glad to hear it. For some reason this email ended up misidentified as spam and went to my Junk E-mail folder, so please excuse the lateness of my response.
I do have a couple of issues and I thought I'd let you know. I'm not sure if they are outside the scope of the library, so I'll let you be the judge of that.
1. Is there an easy(and computationally cheaper) way to check if two simple polygons intersect? other than: !boost::polygon::empty(a & b). If not, is such functionality planned?
You should check if their bounding boxes intersect first and then do the expensive check only if there is intersection between the bounding boxes.
2. The simplify() algorithm seems to be a bit greedy. I have a hard time thinking up a small example, but I can see it clearly on some larger GIS-datasets. The algorithm starts chipping away at some corner, removing unneeded vertices, but in some cases it doesn't stop until the whole polygon is gone. It seems to me it should work a bit more like Douglas-Peucker:
Everytime a point P is removed, creating a line between A and B, all previously removed points between A and B should be checked against the line, and if any of the points end up to far from the line removal of P is rejected
The way it works now, the accumulated error can be great.
Yes, I see your point. In my testing on CAM data that contained a large number of nearly colinear line segments as an artifact of meshing in addition to the sharp angles of man made geometry the operation seemed to be performing well removing the artifact vertices but retaining the ones that were desired features of the figure, however, I can imagine that for GIS data things could turn out much different since all vertices would be qualitatively similar. The way I implemented the simplify operation the threshold is interpreted as a lower bound instead of an upper bound, which makes the result unpredictable.
3. Are there potentially more ways the user can help the library? Right now the user can override polygon_traits<>::winding(), which is otherwise O(N). Couldn't the same be done for area, bounding box and concavity. The bounding box is of course useful for speeding up all boolean operators and knowing concavity speeds up hit tests ( contains(point_type) ) This could be calculated in one sweep. No boiler plate code needed if there would be polygon_default_traits returning winding_unknown, concavity_unknown, etc.
It is easy to imagine a polygon object that caches its area and bounding box. You can override any free function in the library (like area()) by defining your own overload of the function that accepts your type, or partial specialization for your specific type. Frequently the compiler fails to inline the accessor functions for simple data structres like point or rectangle resulting in less-than-zero-cost abstraction. We address this (when benchmarking shows it is a problem) by overloading or partial specialization of the free functions that use the accessors through the traits to instead access the data type directly. I suppose it is possible to define an extended set of traits for many of the free functions that default to the current implementation (similar to winding), but it is hard to know where to draw the line, and it wouldn't be easier for the user than just overloading, but it would be more obvious, but it would be much more work for me. I chose to provide the winding trait because I call winding very frequently, yet it is very common for winding to be a class invariant and known actually at compile time and so have O(0) runtime complexity. Perhaps we can add an example showing how to override free functions for performance.
Otherwise, like I said before, it works like a charm.
I'm very glad to hear it. I made correctness with intuitive and simple to use interfaces my priority. With feedback from the boost community I also cleaned up all the compiler warnings and fixed compatibility issues with the various compilers and versions thereof. Getting the functionality to you was a little like getting a block of cheese through a cheese grater. I had to limit the scope a little and work a lot. Contributions from the community are very welcome, both patches and new features. The simplify algorithm was actually a contributed by a user of the library who had a CAM application. If you would like to contribute a Douglas-Peucker implementation (perhaps you were forced to write your own) I'd be very happy to integrate it, document it and get it into the next release.
Thanks, Luke _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 2011-09-13 at 12:29 +0300, Björn Piltz wrote:
2011/9/8 Simonson, Lucanus J <lucanus.j.simonson@intel.com>
Björn Piltz wrote: > > 1. > Is there an easy(and computationally cheaper) way to check if two > simple polygons intersect? > other than: !boost::polygon::empty(a & b). If not, is such > functionality planned?
You should check if their bounding boxes intersect first and then do the expensive check only if there is intersection between the bounding boxes.
Personally I would expect a good polygon library to provide a function named intersects, which would implement an optimization like the one mentioned above, plus specialized code which would interrupt polygon intersection calculations as soon as one has been found. Regards, Mika Heiskanen
Mika Heiskanen wrote:
Björn Piltz wrote: > > 1. > Is there an easy(and computationally cheaper) way to check if two > simple polygons intersect? > other than: !boost::polygon::empty(a & b). If not, is such > functionality planned?
You should check if their bounding boxes intersect first and then do the expensive check only if there is intersection between the bounding boxes.
Personally I would expect a good polygon library to provide a function named intersects, which would implement an optimization like the one mentioned above, plus specialized code which would interrupt polygon intersection calculations as soon as one has been found.
It is the application programmer who is in the best position to know whether the bounding box check is a net win. Usually it is, but if they are, for example, checking the results of a spatial query that already ensures that the bounding box check would return true then they obviously don't want to pay runtime for the redundant check. You are, of course, correct that a faster intersects check than !boost::polygon::empty(a & b) could be implemented, however, my focus has been toward general algorithms that solve broad classes of problems. Even a&b is just an instantiation of a much more general algorithm that solves also connectivity extraction and map overlay. Given a library that already does !boost::polygon::empty(a & b) would you rather get an alternative method of accomplishing the same thing that is a constant factor faster or something like voronoi diagram of line segments that solves a broad set of problems that the library currently does not address at all? Regards, Luke
Björn Piltz wrote:
here is my D-P implementation: https://bitbucket.org/bjornpiltz/boost_polygon_dp. When I tried to refactor the line-to-point distance calculation from simplify(), I realized it wasn't working correctly. I have replaced it, but I would suggest you have a look at it.
Thanks! Luke
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-h... Sent from the Boost - Users mailing list archive at Nabble.com.
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@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of paul delamusica Sent: Sunday, September 04, 2011 10:40 PM To: boost-users@lists.boost.org 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-h... Sent from the Boost - Users mailing list archive at Nabble.com. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Björn Piltz -
Mika Heiskanen -
paul delamusica -
Simonson, Lucanus J