[gdal-dev] shapefile polygon/multipolygon ordering

[Michael Katz - NOAA Affiliate]

I am working on an application that uses shapefiles as its native data
type. The application supports polygons with holes (for the purpose of
drawing, computing area, finding inside/outside, etc.), but not polygons
with holes with islands, or deeper levels of nesting. This convention of
one-deep holes corresponds to the topology model in GEOS, which my
application uses for a lot of geometry computations.

Shapefiles do not indicate inside outside topology. The just allow a
polygon to have multiple parts (multiple rings), some of which may lie
inside of others. My experience in using shapefiles from many sources is
that many data sets out there do include polygons with holes, but there is
no reliable convention for knowing that, say, the order of the rings will
be an outer ring followed by all its holes, and then another outer ring
followed by all its holes, etc.

So, my code keeps a separate "inside/outside" record for each shapefile
polygon object, which might look something like:

1
-1
1
1
-1
5

This says, for each ring index, which ring it's inside of. For instance
this list means that rings 0, 2, and 3 are inside (i.e., are a hole in)
ring 1 (which itself is not inside any ring, indicated by -1), and ring 6
is inside (i.e., is a hole in) ring 5 (which itself is not inside any ring,
indicated by -1).

So I figure out that relationship when I first see the polygon, and
whenever its points change. And then for any other operation I have those
inside/outside relationships cached and ready to go.

I figure the relationships using GEOS inside polygon check. This code is a
little subtle because it's not enough to check, for instance, that a single
point of one ring is inside another ring, because typically it's allowed
(e.g., it's allowed by GEOS) for one point to be shared between a "shell"
and its "hole". So you need to check that a point in the inner ring which
is *not* shared with the outer ring is inside the outer ring.

Also, I have had some data sets where there *are* instances of a ring
inside a ring inside a ring. In this case, it's necessary to recognize this
and make that innermost ring a shell, not a hole.


On Fri, Nov 14, 2014 at 5:47 PM, David Strip <gdal at stripfamily.net> wrote:

> On 11/14/2014 9:26 AM, mccorb wrote:
> > Two questions:
> > 1. Is it within the shapefile specification to have polygons that have
> holes
> > that have polygons?
> > 2. Does GDAL provide any options to coerce it to not re-order the
> polygons?
> >
> > thanks
> >
>
> Yes, polygons can have holes.
> I have no idea about question 2, but in fact this raises a different
> question:
> Does the shapefile spec say anything about rendering order?
>
> My quick read of the ESRI whitepaper suggests the answer is no.
>
> In general, I would suggest the solution is to have one shapefile for
> land masses, one for lakes, and one for islands. Rendering order can
> then be controlled by application. The one drawback of this approach is
> islands with lakes on them, which is a bit pathological, but does occur.
> In his book "Maphead", Ken Jennings (yes, the Jeopardy guy) cites some
> place where the nesting of water/island/water... goes three layers deep.
> _______________________________________________
> gdal-dev mailing list
> gdal-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/gdal-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/gdal-dev/attachments/20141114/7505d1cf/attachment.html>