WL#8685: Ellipsoidal relational operations

Affects: Server-8.0   —   Status: Complete   —   Priority: Medium

The spatial relational operations (ST_Contains, ST_Crosses, ST_Disjoint, ST_Equals, ST_Intersects, ST_Overlaps, ST_Touches, ST_Within, MBRContains, MBRCoveredBy(*), MBRCovers(*), MBRDisjoint, MBREquals, MBRIntersects, MBROverlaps, MBRTouches, MBRWithin) and InnoDB R-trees currently only support computations in Cartesian spatial reference systems (SRSs). This WL extends those functions to detect that their parameters are in a geographical (ellipsoidal) SRS and to compute their results on the ellipsoid.

The behavior of each ST function will be as defined in SQL/MM Part 3 Spatial. MBR functions are not defined in any standard, but will have a similar implementation.

NOTE: The ellipsoidal computations must be enabled in R-trees and spatial relational operations at the same time to assure consistent results regardless of whether the optimizer chooses to use an index or not. Therefore, geographic computations stay disabled until this is also implemented.

(*) Will never be optimized by use of R-trees, so not strictly required for R-tree vs. relational operations consistency.

ST_ and MBR functions

F-1.1 a)
The functions MUST return NULL if at least one of its parameters is NULL or an empty geometry. The latter does not apply to ST_Equals and MBREquals.
F-1.1 b)
ST_Crosses MUST return NULL if the second parameter is of dimension 0 (point/multipoint) or if the first parameter is of dimension 2 (polygon/multipolygon).
F-1.1 c)
ST_Overlaps MUST return NULL if the dimensions of the input geometries are not equal.
F-1.1 d)
ST_Touches MUST return NULL if both input geometries are of dimension 0 (point/multipoint).
F-1.2
The functions MUST NOT return NULL except in the cases specified in F-1.1.
F-1.3
If one or more geometry arguments are not syntactically well-formed geometries, the functions MUST raise ER_GIS_INVALID_DATA during function evaluation.
F-1.4
If the geometry arguments are not in the same SRID, the functions MUST raise ER_GIS_DIFFERENT_SRIDS.
F-1.5
If the geometry arguments are in an undefined SRS, the functions MUST raise ER_SRS_NOT_FOUND during function evaluation.
F-1.6
If one or more geometry arguments are geometrically invalid, the functions MUST either return a boolean result or raise an error. If a result is returned, the value is undefined, i.e., it may be either true or false.
F-1.7
If both parameters are valid geometries, the functions MUST return the result of the computation.
F-1.8
Deleted.
F-1.9
Deleted.
F-1.10
If any of the parameters are geometry collections, the interior, boundary and exterior of those parameters are those of the union of all elements in the collection.
F-1.11
For the purpose of MBR functions, the bounding box of a point is interpreted as a point that is both boundary and interior.
F1.12
For the purpose of MBR functions, the bounding box of a straight horizontal or vertical line is interpreted as a line where the interior of the line is also boundary. The endpoints are boundary points.
I-1
No new files.
I-2
No new syntax.
I-3
No new commands.
I-4
No new tools.
I-5
Impact on existing functionality: (1) Relational operations on geographical data will still be computed using Cartesian computations (no change). (2) Functions will return NULL instead of 0 when at least one parameter is an empty geometrycollection (except ST_Equals/MBREquals), and in some cases for particular combinations of input parameter dimensions (see F-1.1). (3) Functions will return different results in some cases (bugfixes).

Contents


ST_ functions

Functors and gis::func_name

Implement each function following the pattern of ST_Distance: For each function, create a functor class and a function implementation. The functor can be used by other functors to implement other operations. Items should never use the functors directly since they may throw exceptions.

Disjoint, equals and overlaps can be implemented from BG primitives. Intersects, within, crosses and touches build on the other operations. However, all operations, except disjoint and intersects, depend on set operations to handle geometry collections.

Contains(g1, g2) is implemented as within(g2, g1).

digraph G {

 compound=true;
 subgraph cluster_0 {
   style=filled;
   color=white;
   node [style=filled];
   Crosses -> Within;
   Touches -> Within;
   Within -> Intersects;
   Within -> Crosses;
   Intersects -> Disjoint;
   Equals;
   Overlaps;
   label = "Relational operations";
 }
 subgraph cluster_1 {
   style=filled;
   color=lightgrey;
   node [style=filled, color=white];
   Difference;
   Union;
   label = "Set operations";
 }
 Difference -> Disjoint;
 Equals -> Union [lhead=cluster_1, style=dashed];
 Overlaps -> Union [lhead=cluster_1, style=dashed];
 Within -> Union [lhead=cluster_1, style=dashed];
 Crosses -> Union [lhead=cluster_1, style=dashed];
 Touches -> Union [lhead=cluster_1, style=dashed];

}

For each functor there is a sql/gis/func_name_functor.h that declares the interface. The interface to Item classes is in sql/gis/relops.h and contains all relational functions. The implementation of the functors and functions is in sql/gis/func_name.cc.

The code is structured like this for several reasons:

  • The functors throw exceptions and can be used to implement other functors. BG pulls in a lot of headers and template definitions, so the implementation is in separate source files to make small compile units.
  • The gis::func_name() functions constitute the interface to the rest of MySQL. These functions catch all exceptions, convert them to MySQL errors and hide all BG specific code from the rest of the server. The use of throwing functors and a try-catch around everything makes it easy to return error messages with the correct function name, something we failed to do earlier.

Utility functions for splitting up and simplifying geometry collections are put in sql/gis/gc_utils.[h,cc]. These functions should not be used outside sql/gis/.

Items

A new class Item_func_spatial_relation is created to serve as the base class of all relational operations. The old Item_func_spatial_rel class is still used by set operations and some geometry collection code and has to be around until those usages are removed.

Item_func_spatial_relation contains a common val_int() function for all operations.

MBR functions

MBR functions are simpler than ST_ functions. Basically, the approach is to compute the envelope (MBR) of each argument and to perform the specified operation on those MBRs. This means that there's only one combination of parameter types in BG calls (box, box).

The bounding box computation is done by function gis::box_envelope() in sql/gis/mbr_utils.[h,cc]. Since these are internal to the implementation of MBR functions, they are coordinate system specific and return a BG compatible box type. These functions should not be used by code outside sql/gis/.

The external interface is gis::mbr_funcname(), declared in sql/gis/relops.h.