Hello,
I am new to Boost Geometry, and I have a question to ask if I could use it or not. I have several non-ordered polygons, it is not known that which polygon are external, and which polygon are internal holes. Is there any way to classify which polyogns are holes to what polygons, and get the ordered polygons so that I know which are holes and which are external polygons? Thanks |
Hi,
On 26-1-2012 17:31, jeffpoly wrote: > > I am new to Boost Geometry Welcome to the list > > I have several non-ordered polygons, it is not known that which polygon are > external, and which polygon are internal holes. Is there any way to classify > which polyogns are holes to what polygons, and get the ordered polygons so > that I know which are holes and which are external polygons? Good question. Yes and no. Yes, because you can build with Boost.Geometry primitives. No because it is not available as a standard function and it is not trivial to build yourself. I'll have a look, have done this at least twice before, if one of them was with (a predecessor of) Boost.Geometry it might be of help. Regards, Barend _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi,
Are you trying to simply display your polygons, or you really need to do more operations once constructed? I'm asking because there exist tricks to have the GPU display a polygon and its holes in whatever order, without any analysis. Regards Bruno _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Thanks for your quick response.
>Are you trying to simply display your polygons, or you really need to do more operations once >constructed? I'm asking because there exist tricks to have the GPU display a polygon and its holes in >whatever order, without any analysis. I do not need to display the polygons, once constructed, I need to do some operations on each polygon with holes. Speaking about exist tricks to have the GPU display a ploygon and its holes in whatever order, actually one thing I want to do is to sort the holes within the polygon, so that the travel distance from holes to holes is minimum, do you have any pointer about this also? Thanks very much for your helps. |
In reply to this post by Barend
>Good question. Yes and no. Yes, because you can build with
>Boost.Geometry primitives. No because it is not available as a standard >function and it is not trivial to build yourself. >I'll have a look, have done this at least twice before, if one of them >was with (a predecessor of) Boost.Geometry it might be of help. Thanks, could you please pointer me how could I use this functionality? Jeff |
Hi Jeff,
On 29-1-2012 23:58, jeffpoly wrote: >> Good question. Yes and no. Yes, because you can build with >> Boost.Geometry primitives. No because it is not available as a standard >> function and it is not trivial to build yourself. >> I'll have a look, have done this at least twice before, if one of them >> was with (a predecessor of) Boost.Geometry it might be of help. > Thanks, could you please pointer me how could I use this functionality? > Hmm, yes and no, I already looked and there is a version within Boost.Geometry, assign_parents. But that is (besides in detail) specific for the results of the overlay, and is based on two input geometries. You will need something like that but not exactly that. For the rest you could look at: https://svn.boost.org/svn/boost/trunk/boost/geometry/extensions/gis/io/shapelib/shp_read_object.hpp which is reading a shapefile (where rings are unorganized), sorts them on area, and assigns the parent. This assumes that: - clockwise rings are outer rings (area is positive) - counterclockwise rings are inner rings (area is negative) If you can assume that, you can use something like this. It is just on size, and figuring out which inner ring (negative area) is within which outer ring (positive area). Then you're there. However for a large number of polygons, both positive and negative, this will be less performant. In that case better is to use partition, which is in Boost.Geometry, but that makes it more complex to implement. In the sample (shp_read_object) it assumes one exterior ring, but it (or something similar) will work for a multi-polygon as well. Regards, Barend _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
This post was updated on .
Hello Barend,
Thanks for your help. Unfortunately I do not have the shapefil.h file and I am new to Boost Geometry, so I am not sure that I if I understand your answers fully. >This assumes that: >- clockwise rings are outer rings (area is positive) >- counterclockwise rings are inner rings (area is negative) I do not know rings area before construct, actaully I need to make sure that CW rings are outer rings with positive area, and CCW rings are inner rings with negative area. Also I do have open rings, could I use similar algorithm? >In the sample (shp_read_object) it assumes one exterior ring, but it (or >something similar) will work for a multi-polygon as well. Sorry that I can not figure out how to make this happen, could you please give a little more details or examples? Thanks in advance, Jeff |
Hi Jeff,
On 30-1-2012 23:39, jeffpoly wrote: > > Thanks for your help. Unfortunately I do not have the shapefil.h file and I > am new to Boost Geometry, so I am not sure that I if I understand your > answers fully. Well, shapefil.h is not necessary (in that file it is, but for the algorithm it is not). This is just the place where I coded it. > This assumes that: > - clockwise rings are outer rings (area is positive) > - counterclockwise rings are inner rings (area is negative) > I do not know rings area before construct, actaully I need to make sure that > CW rings are outer rings with positive area, and CCW rings are inner rings > with negative area. Also I do have open rings, could I use similar > algorithm? OK - that is also possible. Are all your rings open? If all are, you can use the polygon type for that (with "true" for the open template parameter). If some are, that is inconvenient, you better all close them then (you can use geometry::correct for that, which works on a ring, will close it and will turn it in clockwise order). If you don't know the orientation before, (maybe) no problem. You sort all rings on abs(area). (If you called correct they are all clockwise now). Sorting is just a convenience, because a larger ring can never be within a smaller ring. Then you check (with the "within") function for all rings if they are inside a larger ring. If they are, you add them to the polygon. Possible problem: it can be more complex if you have more nesting, so polygon A contains B and B contains C and C contains D. If that is the case - you have to use multi-polygons. If you don't know before, yes, to be sure you have to use a multi-polygon and implement the complex case... Another possible problem: do your rings (the boundaries) intersect each other? If yes you cannot build a correct (multi)polygon of it. > >> In the sample (shp_read_object) it assumes one exterior ring, but it (or >> something similar) will work for a multi-polygon as well. > Sorry that I can not figure out how to make this happen, could you please a > little more details or examples? > Yeah, this explanation might be still too short for your needs. I'll recheck this weekend if I happen to have a better example or create a bit more thorough explanation... Regards, Barend _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hello Barend,
Thanks for your quick response. >OK - that is also possible. Are all your rings open? If all are, you can >use the polygon type for that (with "true" for the open template >parameter). If some are, that is inconvenient, you better all close them >then (you can use geometry::correct for that, which works on a ring, >will close it and will turn it in clockwise order). >Another possible problem: do your rings (the boundaries) intersect each >other? If yes you cannot build a correct (multi)polygon of it. Some of the ring are open, and some are close. For the open ring, it is not easy to close, since the self-intersection may happen, also some open ring do contact with some close ring. >Yeah, this explanation might be still too short for your needs. I'll >recheck this weekend if I happen to have a better example or create a >bit more thorough explanation... I do have other projects which may use this in the future, when you have time, please give a detail example or explanation. Thanks, jeff |
Free forum by Nabble | Edit this page |