polygons with holes

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

polygons with holes

jeffpoly
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

Barend
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

Bruno Lalande
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

jeffpoly
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.
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

jeffpoly
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

Barend
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

jeffpoly
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

Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

Barend
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
Reply | Threaded
Open this post in threaded view
|

Re: polygons with holes

jeffpoly
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