WL#7225: Geometry Set Operations Depending on Boost Geometry Extensions

Status: Complete

Replace old GIS implementation with calls to Boost.Geometry (BG) for
functions ST_Intersection, ST_Union, ST_Difference, ST_SymDifference
and ST_IsSimple.

The first four functions were partly converted to BG by WL#7221. BG support for the remaining type combinations is implemented, either directly or by exploiting that ST_Intersection, ST_Union and ST_SymDifference are commutative.

Some parameter type combinations of ST_Intersection, ST_Union, ST_Difference and ST_SymDifference (see NF-1) depend on other GIS functions. If the functions depended on don't use BG for the operations needed by these functions, functions covered by this WL will have to resort to the old implementation.

The old implementation of ST_IsSimple will be completely replaced.

Will fix BUG#73850.

Functional requirements:

F-1: The syntax MUST NOT change.

F-2: All functions must return the correct result according to SFA-CA.

F-3: All functions SHOULD raise an exception condition if the input is
     invalid, even if the old implementation didn't.

F-4: All functions SHOULD NOT return NULL if the input is invalid.

Non-functional requirements:

NF-1: Computations MUST use BG instead of the old implementation for

     all type combinations, except those depending on other geometric
     functions covered by WL#7224. The exceptions allowed are:
      ST_Intersection(Point, LineString)
      ST_Intersection(Point, MultiLineString)
      ST_Intersection(LineString, Point)
      ST_Intersection(LineString, MultiPoint)
      ST_Intersection(MultiPoint, LineString)
      ST_Intersection(MultiPoint, MultiLineString)
      ST_Intersection(MultiLineString, Point)
      ST_Intersection(MultiLineString, MultiPoint)
      ST_Intersection(GeometryCollection, *)
      ST_Intersection(*, GeometryCollection)

      ST_Union(Point, LineString)
      ST_Union(Point, MultiLineString)
      ST_Union(LineString, Point)
      ST_Union(LineString, MultiPoint)
      ST_Union(MultiPoint, LineString)
      ST_Union(MultiPoint, MultiLineString)
      ST_Union(MultiLineString, Point)
      ST_Union(MultiLineString, MultiPoint)

      ST_Difference(Point, LineString)
      ST_Difference(Point, MultiLineString)
      ST_Difference(MultiPoint, LineString)
      ST_Difference(MultiPoint, MultiLineString)
      ST_Difference(GeometryCollection, *)
      ST_Difference(*, GeometryCollection)

      ST_SymDifference(Point, LineString)
      ST_SymDifference(Point, MultiLineString)
      ST_SymDifference(LineString, Point)
      ST_SymDifference(LineString, MultiPoint)
      ST_SymDifference(MultiPoint, LineString)
      ST_SymDifference(MultiPoint, MultiLineString)
      ST_SymDifference(MultiLineString, Point)
      ST_SymDifference(MultiLineString, MultiPoint)
      ST_SymDifference(GeometryCollection, *)
      ST_SymDifference(*, GeometryCollection)
Changes to the interface specification:

I-1: No new files.

I-2: No new syntax.

I-3: No new commands.

I-4: No new tools.

I-5: No impact on existing functionality.

I-6: Changes in return values:

     There may be changes in return values. E.g., if the old
     implementation returns a GeometryCollection containing two
     polygons, the BG implementation may return a GeometryCollection
     containing a MultiPolygon containing the same two polygons.

     Polygon rings will always be returned in counterclockwise order.

Use BG directly for new type combinations:

    ST_Intersection(LineString, LineString)
    ST_Intersection(LineString, MultiLineString)
    ST_Intersection(MultiLineString, MultiLineString)

Use the fact that ST_Intersection is commutative and implement by
parameter swapping:

     ST_Intersection(MultiLineString, LineString)

The old implementation can't be removed until WL#7224 has been implemented.


Use BG directly for new type combinations:

    ST_Union(LineString, LineString)
    ST_Union(LineString, Polygon)
    ST_Union(LineString, MultiLineString)
    ST_Union(MultiLineString, MultiLineString)

Use boost::geometry::difference to implement:

    ST_Union(LineString, MultiPolygon)
    ST_Union(Polygon, MultiLineString)
    ST_Union(MultiLineString, MultiPolygon)

Use the fact that ST_Union is commutative and implement by parameter

    ST_Union(Polygon, LineString)
    ST_Union(MultiLineString, LineString)
    ST_Union(MultiLineString, Polygon)
    ST_Union(MultiPolygon, LineString)
    ST_Union(MultiPolygon, MultiLineString)

The implementation of ST_Union(Polygon, Polygon) is currently so that
it uses the old implementation if given invalid polygons (e.g.,
self-crossing or with holes outside outer border) as input. This
happens because the new implementation doesn't separate between
invalid polygons and type combinations that are not supported by
BG. This WL changes that, so that union of invalid polygons results in
an exception condition being raised.

The old implementation can't be removed until WL#7224 has been implemented.


Use BG directly for new type combinations:

    ST_Difference(LineString, LineString)
    ST_Difference(LineString, MultiLineString)
    ST_Difference(MultiLineString, LineString)
    ST_Difference(MultiLineString, MultiLineString)

The old implementation can't be removed until WL#7224 has been implemented.


Use BG directly for new type combinations:

    ST_SymDifference(LineString, LineString)
    ST_SymDifference(LineString, MultiLineString)
    ST_SymDifference(MultiLineString, MultiLineString)

Use the fact that ST_SymDifference in some cases is equivalent to
ST_Union to implement:

    ST_SymDifference(LineString, Polygon)
    ST_SymDifference(LineString, MultiPolygon)
    ST_SymDifference(Polygon, MultiLineString)
    ST_SymDifference(MultiLineString, MultiPolygon)

Use the fact that ST_SymDifference is commutative and implement by
parameter swapping:

    ST_SymDifference(Polygon, LineString)
    ST_SymDifference(MultiLineString, LineString)
    ST_SymDifference(MultiLineString, Polygon)
    ST_SymDifference(MultiPolygon, LineString)
    ST_SymDifference(MultiPolygon, MultiLineString)

The old implementation can't be removed until WL#7224 has been implemented.


Replace everything with calls to BG and remove the old implementation.