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

Tue Jul 21 10:08:35 EDT 2009

Yes, the bbox test is classic and helps narrowing down the candidates for point-in-polygon.

Unfortunately it doesn't help with nested loops. The current algorithm has also a 'sort by area' step in this regard.

I think the weakness of the current algorithm is the fact it is doing a brute force rings association, i.e. it is assuming the set of rings are totally unrelated. This is not true since regardless the orientation (which can be any) the input rings are grouped {exterior, interior, interior, exterior, ...}. I intend to take advantage of these heuristics.

-----Original Message-----
From: fdo-internals-bounces at lists.osgeo.org [mailto:fdo-internals-bounces at lists.osgeo.org] On Behalf Of Konstantin Baumann
Sent: Tuesday, July 21, 2009 3:44 AM
To: FDO Internals Mail List
Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

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

_______________________________________________
fdo-internals mailing list
fdo-internals at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/fdo-internals