Bug in Selection polygon from PostGiS (PostgreSql)

[maciej.skorczewski@…]

The problem is;

When layer are stored in PostGis database (Postgres) and i want select polygon i get bad results...i can't select smaller polygon.

SO it is problem whit concavo polygon.

take a look on screen... ​http://img340.imageshack.us/img340/4928/bugpostgisey2.jpg

This problem comes only with layers who are stored in PostGIS. This same solution whit layer from shp files are corect.

[anonymous]

screen whit problem

[maciek]

...secont screen whit this error

[tomfukushima]

We've seen this behavior in other providers as well. I think it is because the "point in polygon" fails for the provider. It returns the larger polygon because "point in bounding rectangle for feature" is done.

[mloskot]

Tom,

I think I know what may be the problem with OGR provider, actually with OGR (GDAL). Maciej forwarded to me reply he got from Traian Stanev and Traian is writing:

In the AJAX viewer, selection is done by doing an Intersects
spatial query against the provider.

The OGR provider delegates intersection test to the OGR. Here, OGR can behave in two ways:

1. If built without ​GEOS support, OGR assumes envelopes overlapping as intersection.

2. If GEOS support is available, then the intersection test is forwarded to GEOS library. Obviously, GEOS tests for intersections very accurately, not only checking if envelopes overlap.

Now, I suppose Maciej uses OGR provider with GDAL built without GEOS support.

Maciej, could you confirm it?

[ksgeograf]

I have been examining the problem, using a custom build of the OGR provider. It is true that without GEOS support in OGR, the Intersect only does a BBOX check.

However, merely enabling GEOS will not work, as the viewer sends a square that is orthogonal to the axes (like a BBOX). The GEOS library will interpret this as another BBOX, and only perform the BBOX check anyway.

When I change the polgyon sent from the viewer to a triangle, it takes 22 seconds to calculate the Intersects result with a polygon with 8000 linesegments. I have a 2+ GHz machine.

It seems that GEOS always builds a full intersection matrix, before returning the result. This is obviously not optimal for a simple hit test. Even with this knowledge, I still don't see how it can take 22 seconds to calculate 8000 * 3 intersections.

Can someone explain this, or how to fix it?

[mloskot]

Yes, this issue you're describing is possible in GEOS. I haven't had any chance to dig into this issue deeper and to profile GEOS so I can't explainwhy.

Are you sure if your benchmark counts time spent on translations of geometries between formats:

OGR -> GEOS and GEOS -> OGR and OGR -> FDO

Usually, these translations are detected as performance bottleneck.

[ksgeograf]

You are right. I have traced it for a few hours.

OGR sends WKT data to GEOS.

Spending some time, I've found the source of the problem... The GEOS WKT reader works by using the StringTokenizer, which is issuing statements like: str=str.substr(1);

Which, of course, will make a copy of the entire string, minus the first character. Then the unused memory will be release. It should of use a pointer to the current character instead. It is easy to fix, but there may be other parts of GEOS that depend on this functionality. If GEOS is patched, then the OGR provider will be depending on a patched version of GEOS.

A better fix would be to modify GDAL/OGR to use WKB (assuming that the WKB Reader is better implemented in GEOS). The OGR provider will then depend on a patched GDAL/OGR.

Still, this does not change the fact that GDAL/OGR assumes that a rectangular spatial filter should perform BBOX overlap tests.

What is the prefered way of solving this?

[ksgeograf]

An improved StringTokenizer

[ksgeograf]

I modified the GEOS StringTokenizer and now it performs very well. I have attached the modified file, in case someone want's it. To use this change, you must also modify io.h, line 69, and add a private member variable to the StringTokenizer class: string::size_type pos;

If you want to fix the original problem, you must ensure that your OGR/GDAL is compiled with GEOS support. (Enable it in nmake.opts). The you must replace the string tokenizer file with the one attached + add the line mentioned above.

Then you must either change OGRLayer.c, to not use BBOX shortcut if the box is rectangular, or modify the polygon that the viewer sends.

Then build GEOS, build GDAL/OGR, build OGR FDO Provider.

[maciek]

ksgeograf

Can you build your provider after changes? and put it somewhere on www.

btw i found (i think) another problem whit OGR Provider. ​http://www.nabble.com/SetSelectionXML-on-layer-from-database-%28PostgreSQL-%3EPostgGIS%29-tf3900386s16610.html

should i add it to trac?

[mloskot]

ksgeograf,

Big thanks for your fantastic work, on behalf of GEOS and OGR team! Today, I'll review your findings in the bigger picture and if everything works, I'll patch GEOS and OGR.

Thank you again! Mat

[ksgeograf]

Thank you for the thanks :D.

If you modify OGR, the OGRLayer makes the check in installFilter, line 768, and sets the variable m_bFilterIsEnvelope. This should not be done, but I can't see if it has any negative implications to remove it. The variable is used in FilterGeometry.

The FDO OGR Provider calls the wrapper function SetSpatialFilterRect, and perhaps the m_bFilterIsEnvelope should be set here, so map zoom and display works with BBOX test only? Still, that is not an inituitive handling, and may be usefull only with the FDO provider.

Maciek, I can post it, but it doesn't have PostGIS support (haven't got a Postgres database to test on), so you won't get anything usefull from my build.

I think you should post a new trac for the selection bug.

[traianstanev]

I have checked in a temporary fix for this. OGR was assuming a BBOX query if the intersection polygon is axis aligned. I simply warped the input rectangle by a tiny bit to make it non-aligned. This is enough to make OGR do real intersection.

I think OGR should be fixed to only resort to BBOX query in case SetSpatialFilterRect is called. If SetSpatialFilter is called instead, and GEOS is available, OGR should not try to be smart about reducing the accuracy of the query by doing a BBOX check only.

[ksgeograf]

The new tokenizer I made, was already fixed in 3.0.0rc4 of GEOS. The improvement suggestion I made about using WKB instead of WKT was implemented in OGR 1.4.0.

So, both the original problem has been fixed, and so has the follow up problem. Traians way of fixing the BBOX issue, also means that both OGR and GEOS can remain unmodified, when being used with the FDO Provider.

[ksgeograf]

You can download a build from ​this link. I can't submit the file, it is too big.

It is built with GDAL 1.4.1, GEOS 3.0.0rc4, PostGIS, MySQL and SQLite support. Hope it works on PostGIS, haven't tested it.

[traianstanev]

Kenneth (ksgeograf) has submitted a better fix for the intersection problem. He added a call to OGR to perform real intersection in the ReadNext call of the OGR FeatureReader. This lets the underlying database do a simple BBOX query, and then checking the features that match the bbox for actual intersection. This can result in more features being pulled in, but effectively fixes the problem for all data sources, which the previous fix did not.