Fixed precision for ST_Intersection, ST_Union, etc.

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Fixed precision for ST_Intersection, ST_Union, etc.

Daniel Baston
I've set up a branch to allow the use of a fixed precision model with ST_Intersection, ST_Difference, ST_SymmetricDifference, and ST_Union (all variants), on the GEOS backend.  There are some broader design implications to introducing a precision parameter, so I wanted to see if the group sees any problems with this approach, which is:

* The precision is not encoded in the geometry; the user must specify the precision when invoking the function, like ST_Intersection(a.geom, b.geom, 1e-4).  I think it's best to avoid encoding the precision into the geometry (like we do for SRID) for the time being, mostly because the precision we're specifying for these overlay functions refers to a GEOS feature rather than any global concept of precision.  Since a geometry's encoded precision would be ignored by ST_Intersects or ST_ApproximateMedialAxis, I think it's best left as an explicit argument where it is supported for now.

* GEOS provides the ability to reduce a geometry's precision, cleaning up topological collapses that may result from coordinate movement.  These functions don't take advantage of this behavior; they assume that the user is providing geometry whose coordinates are in fact precise at the level specified.  I do think there should be a separate ST_ReducePrecision to allow a user to take advantage of this feature.


Any thoughts?

Dan

_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Mike Taves
On 10 March 2016 at 13:20, Daniel Baston <[hidden email]> wrote:
> I do think there should be a separate ST_ReducePrecision to
> allow a user to take advantage of this feature.

Hi Dan,

This last idea sounds very much like ST_SnapToGrid, which also
considers to remove (or not) coordinates within the precision of the
grid based on the geometry type, e.g.:

SELECT ST_AsText(ST_SnapToGrid(ls, 1.0)),
ST_AsText(ST_SnapToGrid(ST_Points(ls), 1.0))
FROM ST_GeomFromText('LINESTRING(0 0, 0.1 0.1, 1 1)') ls;
-[ RECORD 1 ]----------------------
st_astext | LINESTRING(0 0,1 1)
st_astext | MULTIPOINT(0 0,0 0,1 1)

-Mike
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Sandro Santilli-2
In reply to this post by Daniel Baston
On Wed, Mar 09, 2016 at 07:20:57PM -0500, Daniel Baston wrote:

> Branch is at https://github.com/postgis/postgis/pull/100

> * GEOS provides the ability to reduce a geometry's precision, cleaning up
> topological collapses that may result from coordinate movement.  These
> functions don't take advantage of this behavior; they assume that the user
> is providing geometry whose coordinates are in fact precise at the level
> specified.  I do think there should be a separate ST_ReducePrecision to
> allow a user to take advantage of this feature.

As far as I know the only way to request use of fixed-precision
through the GEOS C-API is by invoking the function that does
encode the precision into the GEOS version of the geometry and at
the same time rounds its coordinates to it, so there should be
no way to report a precision assumption to GEOS (as of GEOS
trunk C-API).

How else did you implement the precision support, if not using
those functions (GEOSGeom_setPrecision_r) ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Daniel Baston
You're right, I didn't describe that well.  I should say instead that these functions aren't using GEOS' behavior of cleaning up topological collapses (GEOS_PREC_NO_TOPO and GEOS_PREC_KEEP_COLLAPSED in the CAPI).  GEOS is indeed doing a pointwise precision reduction, which should be a no-op in my use case but may not be in others.

Dan

On Thu, Mar 10, 2016 at 4:53 AM, Sandro Santilli <[hidden email]> wrote:
On Wed, Mar 09, 2016 at 07:20:57PM -0500, Daniel Baston wrote:

> Branch is at https://github.com/postgis/postgis/pull/100

> * GEOS provides the ability to reduce a geometry's precision, cleaning up
> topological collapses that may result from coordinate movement.  These
> functions don't take advantage of this behavior; they assume that the user
> is providing geometry whose coordinates are in fact precise at the level
> specified.  I do think there should be a separate ST_ReducePrecision to
> allow a user to take advantage of this feature.

As far as I know the only way to request use of fixed-precision
through the GEOS C-API is by invoking the function that does
encode the precision into the GEOS version of the geometry and at
the same time rounds its coordinates to it, so there should be
no way to report a precision assumption to GEOS (as of GEOS
trunk C-API).

How else did you implement the precision support, if not using
those functions (GEOSGeom_setPrecision_r) ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Sandro Santilli-2
On Thu, Mar 10, 2016 at 07:47:49AM -0500, Daniel Baston wrote:
> You're right, I didn't describe that well.  I should say instead that these
> functions aren't using GEOS' behavior of cleaning up topological collapses
> (GEOS_PREC_NO_TOPO and GEOS_PREC_KEEP_COLLAPSED in the CAPI).  GEOS is
> indeed doing a pointwise precision reduction, which should be a no-op in my
> use case but may not be in others.

What's the rationale for NOT handling the collapsing ?
Theoretically, feeding invalid geometries to GEOS overlay operations
should result in an exception being thrown or some other undesired
result, so why taking the risk at all ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Daniel Baston
My rationale here is that it's not the job of ST_Intersection to clean up its inputs before computing the intersection, much like the current overlay functions don't call ST_MakeValid on their inputs.  I think there is a place for a ST_ReducePrecision / ST_SnapToGrid that reduces precision and cleans up collapsed geometries, etc., but I don't think it's something that should be automatically run on the inputs of all overlay functions.

Dan

On Sun, Mar 13, 2016 at 4:42 AM, Sandro Santilli <[hidden email]> wrote:
On Thu, Mar 10, 2016 at 07:47:49AM -0500, Daniel Baston wrote:
> You're right, I didn't describe that well.  I should say instead that these
> functions aren't using GEOS' behavior of cleaning up topological collapses
> (GEOS_PREC_NO_TOPO and GEOS_PREC_KEEP_COLLAPSED in the CAPI).  GEOS is
> indeed doing a pointwise precision reduction, which should be a no-op in my
> use case but may not be in others.

What's the rationale for NOT handling the collapsing ?
Theoretically, feeding invalid geometries to GEOS overlay operations
should result in an exception being thrown or some other undesired
result, so why taking the risk at all ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Sandro Santilli-2
On Sun, Mar 13, 2016 at 06:14:44PM -0400, Daniel Baston wrote:
> My rationale here is that it's not the job of ST_Intersection to clean up
> its inputs before computing the intersection, much like the current overlay
> functions don't call ST_MakeValid on their inputs.  I think there is a
> place for a ST_ReducePrecision / ST_SnapToGrid that reduces precision and
> cleans up collapsed geometries, etc., but I don't think it's something that
> should be automatically run on the inputs of all overlay functions.

But in this case (specifying a precision model) you're also basically
asking ST_Intersection to change the inputs, and it is known that such
changing might introduce invalidities that would be "fatal" for the overlay
operation.

The only case in which you'd want to avoid fixing invalidities is by knowing
in advance that the reduction would be a no-op (as in your case) and thus
willing to avoid the checking cost. Did you evaluate the cost of checking ?
Could that cost be reduced by determining a "no-op" case directly within GEOS ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Daniel Baston
Ideally, specifying a precision model would not imply any sort of precision reduction.  The fact that it does, in this case, is artifact of the GEOS CAPI implementation.  I think these functions are best kept separate, so that precision reduction can be explicitly performed in a way that the user has both control over the "autocleanup" options, and some means of viewing the output of the precision reduction operation.  Many data large data sets, such as TIGER, are already at fixed-precision and only need some way of making GEOS aware of the precision model.

The cost of the checking is the same as ST_IsValid, which is significant or not depending on the usage pattern.  I'd be less bothered by the cost, than by the idea of PostGIS silently and non-optionally performing "magic" on the inputs in the hope of avoiding what may be a legitimate error downstream, especially since there's no way to know that the invalidity, if found, had anything to do with the precision reduction.

Here's a query that I think illustrates the problem:

-- No preicsion model
postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0, 1 0, 0 1, 1 1, 0 0))'));
ERROR:  Error performing intersection: TopologyException: Input geom 1 is invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5
CONTEXT:  SQL function "st_intersection" statement 1

-- With precision model, GEOSGeom_setPrecision flags GEOS_PREC_NO_TOPO | GEOS_PREC_KEEP_COLLAPSED
postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0, 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
ERROR:  Error performing intersection: TopologyException: Input geom 1 is invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5

-- WIth precision model, no flags to GEOSGeom_setPrecision
postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0, 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
        st_astext         
--------------------------
 GEOMETRYCOLLECTION EMPTY



On Tue, Mar 15, 2016 at 4:41 AM, Sandro Santilli <[hidden email]> wrote:
On Sun, Mar 13, 2016 at 06:14:44PM -0400, Daniel Baston wrote:
> My rationale here is that it's not the job of ST_Intersection to clean up
> its inputs before computing the intersection, much like the current overlay
> functions don't call ST_MakeValid on their inputs.  I think there is a
> place for a ST_ReducePrecision / ST_SnapToGrid that reduces precision and
> cleans up collapsed geometries, etc., but I don't think it's something that
> should be automatically run on the inputs of all overlay functions.

But in this case (specifying a precision model) you're also basically
asking ST_Intersection to change the inputs, and it is known that such
changing might introduce invalidities that would be "fatal" for the overlay
operation.

The only case in which you'd want to avoid fixing invalidities is by knowing
in advance that the reduction would be a no-op (as in your case) and thus
willing to avoid the checking cost. Did you evaluate the cost of checking ?
Could that cost be reduced by determining a "no-op" case directly within GEOS ?

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Sandro Santilli-2
On Tue, Mar 15, 2016 at 05:52:10AM -0400, Daniel Baston wrote:

> The cost of the checking is the same as ST_IsValid,

Are you sure ? Do you have numbers to show ?
Had you considered improving GEOS to make it irrelevant if
none of the coordinates were really changed ?
(as that would be your use case).

> Here's a query that I think illustrates the problem:
>
> -- No preicsion model
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))'));
> ERROR:  Error performing intersection: TopologyException: Input geom 1 is
> invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5
> CONTEXT:  SQL function "st_intersection" statement 1
>
> -- With precision model, GEOSGeom_setPrecision flags GEOS_PREC_NO_TOPO |
> GEOS_PREC_KEEP_COLLAPSED
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
> ERROR:  Error performing intersection: TopologyException: Input geom 1 is
> invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5
>
> -- WIth precision model, no flags to GEOSGeom_setPrecision
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
>         st_astext
> --------------------------
>  GEOMETRYCOLLECTION EMPTY

The final result is unexpected, how was the polygon changed ?
Reduction should have not moved any vertex, right ?

I guess I just don't like how the handling is performed by
GEOS. Ideally, it should only fix what was broken by precision
reduction, not what was broken in the input.

Remember the GEOS side of this is recent, so might need to
still be tweaked.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Daniel Baston
The relevant code is in GeometryPrecisionReducer.cpp, around line 72.  It can be paraphrased as:

geom_reduced = reduce_coordinate_precision(geom)
if (!geom_reduced.isValid())
   geom_reduced = geom_reduced.buffer(0)
return geom_reduced

The reason I chose to bypass everything after the first line is that (a) an isValid() check is always performed, and (b) if that fails, our geometry gets the bazooka of .buffer(0).  There's no algorithm available to surgically remove only degeneracies caused by the precision reduction.  It's very easy to imagine a case (and I've seen them) where:

- user has a large polygon at full double-precision
- coordinates are snapped or truncated to 1e-6, producing a tiny bow-tie effect along an edge somewhere
- in an attempt to fix the problem, user performs a .buffer(0), causing 99.9% of the original polygon to disappear, and keeping only the tiny part of the bowtie

This is not the kind of thing I'd want to have silently and automatically in every overlay function.  I really don't see the problem with having overlay functions fail on invalid inputs, even if the input is invalid only because the user supplied an incorrect precision argument.

The only change I can see making to GEOS is in the C API, renaming the existing GEOSGeom_setPrecision to GEOSGeom_reducePrecision, and adding a new GEOSGeom_setPrecision that does nothing more than set the PrecisionModel.  The PostGIS overlays could then use the new GEOSGeom_setPrecision, while a PostGIS ST_ReducePrecision could use GEOSGeom_reducePrecision.

Dan


On Tue, Mar 15, 2016 at 7:22 AM, Sandro Santilli <[hidden email]> wrote:
On Tue, Mar 15, 2016 at 05:52:10AM -0400, Daniel Baston wrote:

> The cost of the checking is the same as ST_IsValid,

Are you sure ? Do you have numbers to show ?
Had you considered improving GEOS to make it irrelevant if
none of the coordinates were really changed ?
(as that would be your use case).

> Here's a query that I think illustrates the problem:
>
> -- No preicsion model
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))'));
> ERROR:  Error performing intersection: TopologyException: Input geom 1 is
> invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5
> CONTEXT:  SQL function "st_intersection" statement 1
>
> -- With precision model, GEOSGeom_setPrecision flags GEOS_PREC_NO_TOPO |
> GEOS_PREC_KEEP_COLLAPSED
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
> ERROR:  Error performing intersection: TopologyException: Input geom 1 is
> invalid: Self-intersection at or near point 0.5 0.5 at 0.5 0.5
>
> -- WIth precision model, no flags to GEOSGeom_setPrecision
> postgres=# SELECT ST_AsText(ST_Intersection('POINT (0 0)', 'POLYGON ((0 0,
> 1 0, 0 1, 1 1, 0 0))', op_precision := 1e-12));
>         st_astext
> --------------------------
>  GEOMETRYCOLLECTION EMPTY

The final result is unexpected, how was the polygon changed ?
Reduction should have not moved any vertex, right ?

I guess I just don't like how the handling is performed by
GEOS. Ideally, it should only fix what was broken by precision
reduction, not what was broken in the input.

Remember the GEOS side of this is recent, so might need to
still be tweaked.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: Fixed precision for ST_Intersection, ST_Union, etc.

Sandro Santilli-2
On Tue, Mar 15, 2016 at 09:24:41AM -0400, Daniel Baston wrote:
> The relevant code is in GeometryPrecisionReducer.cpp, around line 72.  It
> can be paraphrased as:
>
> geom_reduced = reduce_coordinate_precision(geom)
> if (!geom_reduced.isValid())
>    geom_reduced = geom_reduced.buffer(0)
> return geom_reduced

Ouch, that's really bad indeed.

> The only change I can see making to GEOS is in the C API, renaming the
> existing GEOSGeom_setPrecision to GEOSGeom_reducePrecision, and adding a
> new GEOSGeom_setPrecision that does nothing more than set the
> PrecisionModel.  The PostGIS overlays could then use the new
> GEOSGeom_setPrecision, while a PostGIS ST_ReducePrecision could use
> GEOSGeom_reducePrecision.

Sounds good to me, 3.6.0 isn't out yet so changing the signature
is still possible.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/postgis-devel