[fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

Tue Jul 21 03:43:36 EDT 2009

If you first use bbox tests, that could speed up
the decision process:

Doing this pairwise for the polygons:
1) two bboxes overlap, but are not contained by the
   other one, or do not overlap at all => no polygon
   can be a hole of the other polygon
2) one bbox contains the other bbox => do the point-
   in-polygon test for one vertex of polygon
   corresponding to the contained bbox

Kosta

> -----Original Message-----
> From: Traian Stanev [mailto:traian.stanev at autodesk.com]
> Sent: Thursday, July 16, 2009 6:05 PM
> To: FDO Internals Mail List
> Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
> 
> 
> It can be optimized but the cost will never be zero, like it is now...
> I guess we will have to find some sample data to compare the
> performance before and after, but from what I remember last time we had
> this check, it made rendering intolerably slow for some data sets (if
> you compared SHP to the equivalent SDF).
> 
> Another thing to consider is that there are other providers which don't
> validate geometry like that -- SDF, SQLite for example -- so client
> code will still have to compensate for polygons whose rings are
> disjoint so should be treated as multipolygons, regardless of whether
> the SHP provider fixes the geometry.
> 
> So I'd argue that the fixing of the geometry should be done by code
> that requires it to be fixed -- i.e. take the performance hit only when
> necessary. This way rendering would not have to suffer the performance
> hit.
> 
> Traian
> 
> 
> 
> -----Original Message-----
> From: fdo-internals-bounces at lists.osgeo.org [mailto:fdo-internals-
> bounces at lists.osgeo.org] On Behalf Of Dan Stoica
> Sent: Thursday, July 16, 2009 11:59 AM
> To: FDO Internals Mail List
> Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
> 
> The performance depends on how fast is point-in-polygon test. This can
> be optimized. More, time permitting, I'll try to promote my new mini
> spatial index, designed for this purpose.
> 
> I'm not saying that will be no performance loss. But having correct
> results for spatial queries fully compensates, I believe.
> 
> Dan.
> 
> 
> -----Original Message-----
> From: fdo-internals-bounces at lists.osgeo.org [mailto:fdo-internals-
> bounces at lists.osgeo.org] On Behalf Of Traian Stanev
> Sent: Thursday, July 16, 2009 11:28 AM
> To: FDO Internals Mail List
> Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
> 
> 
> 
> It depends -- for display purposes it doesn't matter if it's a polygon
> with lots of rings or multipolygon, so in the most common case (every
> repaint in Map or MapGuide), it will be a net performance loss.
> 
> Traian
> 
> 
> -----Original Message-----
> From: fdo-internals-bounces at lists.osgeo.org [mailto:fdo-internals-
> bounces at lists.osgeo.org] On Behalf Of Dan Stoica
> Sent: Thursday, July 16, 2009 11:19 AM
> To: FDO Internals Mail List
> Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
> 
> Hi Frank,
> 
> > I do feel the RFC is a bit optimistic about the performance impact.
> 
> I'll try to optimize if the case. Indeed, the implementation does not
> rely on the loops orientation.
> 
> However, this has to be done because the previous approach "speed over
> correctness" proved to have serious consequences, worse than a
> performance penalty on loading (aren't the machines faster and
> faster?).
> 
> Regards,
> Dan.
> 
> -----Original Message-----
> From: fdo-internals-bounces at lists.osgeo.org [mailto:fdo-internals-
> bounces at lists.osgeo.org] On Behalf Of Frank Warmerdam
> Sent: Thursday, July 16, 2009 10:09 AM
> To: FDO Internals Mail List
> Subject: Re: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
> 
> Orest Halustchak wrote:
> > Hi,
> >
> >
> >
> > We've run into issues where SHP multi-polygons are not being returned
> as
> > FDO multi-polygons by the FDO SHP provider. The issue stems from the
> SHP
> > specification having only a polygon type defined, but that definition
> > includes polygons with any number of outer rings which encompasses
> both
> > simple polygons and multi-polygons.
> >
> >
> >
> > RFC 38, drafted by Dan Stoica, proposes to fix the problem by adding
> the
> > capability to the FDO SHP provider.
> >
> > See http://trac.osgeo.org/fdo/wiki/FDORfc38 .
> >
> > Have a look at the RFC and provide your comments.
> 
> Dan / Orest,
> 
> I'm in support of this change.  I had to do the same thing in the OGR
> shape
> driver a few years ago.  I do feel the RFC is a bit optimistic about
> the
> performance impact.  I find it is common to have polygons with holes in
> shapefile format, and they will all require fairly expensive processing
> to
> determine if the extra rings are interior or exterior.
> 
> In theory I believe you are supposed to be able to tell from the ring
> winding direction whether additional rings are interior or exterior.
> However,
> many shapefiles produced by crappy libraries (like my shapelib!) did
> not
> set the winding direction properly so it is unwise to depend on this.
> 
> Best regards,
> --
> ---------------------------------------+-------------------------------
> -------
> I set the clouds in motion - turn up   | Frank Warmerdam,
> warmerdam at pobox.com
> light and sound - activate the windows | http://pobox.com/~warmerdam
> and watch the world go round - Rush    | Geospatial Programmer for Rent
> 
> _______________________________________________
> fdo-internals mailing list
> fdo-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> fdo-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> fdo-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> fdo-internals at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/fdo-internals