OSGeo.org › OSGeo Software and Data Projects › Feature Data Objects (FDO) › FDO Internals

Please review FDO RFC 38 - Multi-polygon support for SHP

14 messages

Orest Halustchak

Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

Some javascript/style in this post has been disabled (why?)

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.

Thanks,

Orest.

_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Frank Warmerdam

Re: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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 Stoica

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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: [hidden email] [mailto:[hidden email]] 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.

Traian Stanev

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

Dan Stoica

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

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, [hidden email]
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
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals
_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals
_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals
_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Traian Stanev

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

Orest Halustchak

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

We had users complain that they were losing their multi-polygons in some cases and we also have code in various places that does special case checking for SHP and this case. We need to generalize this so that client code doesn't keep having to do special checking and users get the correct fdo type back. This isn't really validating the geometry but determining the correct type to call it on read.

An alternative might be to add a capability that says that a provider is returning multi-polygons as polygons and provide an external function that checks if a polygon is really a multi-polygon. The client would still have to do extra work to check this and use the function when necessary. It doesn't completely remove special case handling.

Thanks,
Orest.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Traian Stanev
Sent: Thursday, July 16, 2009 12: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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

Dan Stoica

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

> an external function that checks if a polygon is really a multi-polygon.

Orest, we already have such function:

// Might return a Polygon or a MultiPolygon
geometry = FdoSpatialUtility::CreateGeometryFromRings (rings, RELATE_RINGS);

As for the extra capability, I guess the fact SHP doesn't advertize multi-polygons can suffice. But this not clean since we'll just move the processing on the client, assuming that the client sometimes doesn't care about correctness. I would prefer to work on performance instead.

Traian, I assume you'll like to see some performance benchmarks before voting?

Thanks,
Dan.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Orest Halustchak
Sent: Thursday, July 16, 2009 12:17 PM
To: FDO Internals Mail List
Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

We had users complain that they were losing their multi-polygons in some cases and we also have code in various places that does special case checking for SHP and this case. We need to generalize this so that client code doesn't keep having to do special checking and users get the correct fdo type back. This isn't really validating the geometry but determining the correct type to call it on read.

An alternative might be to add a capability that says that a provider is returning multi-polygons as polygons and provide an external function that checks if a polygon is really a multi-polygon. The client would still have to do extra work to check this and use the function when necessary. It doesn't completely remove special case handling.

Thanks,
Orest.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Traian Stanev
Sent: Thursday, July 16, 2009 12: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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

Traian Stanev

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

No, I'll vote for this without conditions, I'll of course do my own benchmark later.

I was just raising the issues that have been associated with this before so that people know the implications of this RFC.

Traian

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Dan Stoica
Sent: Thursday, July 16, 2009 12:38 PM
To: FDO Internals Mail List
Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

> an external function that checks if a polygon is really a multi-polygon.

Orest, we already have such function:

// Might return a Polygon or a MultiPolygon
geometry = FdoSpatialUtility::CreateGeometryFromRings (rings, RELATE_RINGS);

As for the extra capability, I guess the fact SHP doesn't advertize multi-polygons can suffice. But this not clean since we'll just move the processing on the client, assuming that the client sometimes doesn't care about correctness. I would prefer to work on performance instead.

Traian, I assume you'll like to see some performance benchmarks before voting?

Thanks,
Dan.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Orest Halustchak
Sent: Thursday, July 16, 2009 12:17 PM
To: FDO Internals Mail List
Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

We had users complain that they were losing their multi-polygons in some cases and we also have code in various places that does special case checking for SHP and this case. We need to generalize this so that client code doesn't keep having to do special checking and users get the correct fdo type back. This isn't really validating the geometry but determining the correct type to call it on read.

An alternative might be to add a capability that says that a provider is returning multi-polygons as polygons and provide an external function that checks if a polygon is really a multi-polygon. The client would still have to do extra work to check this and use the function when necessary. It doesn't completely remove special case handling.

Thanks,
Orest.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Traian Stanev
Sent: Thursday, July 16, 2009 12: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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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: [hidden email] [mailto:[hidden email]] 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:

Frank Warmerdam

Re: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

In reply to this post by Traian Stanev

Traian Stanev wrote:

> 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.

Traian,

I believe that SDF and SQLite already have a proper representation for
multipolygons. It's possible they contain invalid data of course, but in
general use there is not reason to doubt them.

> 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.

I would argue that a connection parameter for the shape provider indicating
whether to emphasize correctness or speed would be useful.

Best regards,
--
---------------------------------------+--------------------------------------
I set the clouds in motion - turn up | Frank Warmerdam, [hidden email]
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
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Traian Stanev

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

> -----Original Message-----
> From: [hidden email] [mailto:fdo-internals-
> [hidden email]] On Behalf Of Frank Warmerdam
> Sent: Thursday, July 16, 2009 3:19 PM
> To: FDO Internals Mail List
> Subject: Re: [fdo-internals] Please review FDO RFC 38 - Multi-polygon
> support for SHP
>
> Traian Stanev wrote:
> > 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.
>
> Traian,
>
> I believe that SDF and SQLite already have a proper representation for
> multipolygons. It's possible they contain invalid data of course, but in
> general use there is not reason to doubt them.
>

Unless someone used a tool like a current version Map3D to export from SHP
to SDF via FDO. But in general yes, I agree that it's a different
situation since they can represent multi-polygons natively.

> > 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.
>
> I would argue that a connection parameter for the shape provider indicating
> whether to emphasize correctness or speed would be useful.
>

Will there be a setting for "Both". :)

> Best regards,
> --
> ---------------------------------------+------------------------------------
> --
> I set the clouds in motion - turn up | Frank Warmerdam,
> [hidden email]
> 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
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/fdo-internals

_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Dan Stoica

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

> indicating whether to emphasize correctness or speed would be useful.

What if the geometry is cached? E.g. initially fetched for speed and later used for spatial queries?

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Traian Stanev
Sent: Thursday, July 16, 2009 3:28 PM
To: FDO Internals Mail List
Subject: RE: [fdo-internals] Please review FDO RFC 38 - Multi-polygon support for SHP

_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals
_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Konstantin Baumann

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

In reply to this post by Traian Stanev

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:[hidden email]]
> 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: [hidden email] [mailto:fdo-internals-
> [hidden email]] 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: [hidden email] [mailto:fdo-internals-
> [hidden email]] 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: [hidden email] [mailto:fdo-internals-
> [hidden email]] 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: [hidden email] [mailto:fdo-internals-
> [hidden email]] 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,
> [hidden email]
> 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
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/fdo-internals
> _______________________________________________
> fdo-internals mailing list
> [hidden email]
> http://lists.osgeo.org/mailman/listinfo/fdo-internals

_______________________________________________
fdo-internals mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/fdo-internals

Dan Stoica

RE: Please review FDO RFC 38 - Multi-polygon support for SHP

Reply Threaded

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: [hidden email] [mailto:[hidden email]] 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