WL#7220: Spatial Relation Check Functions

Status: Complete

Implement MySQL GIS relation check functions using boost geometry. 
Gis features are more and more powerful, important and pervasive in  
RDBMS products, and MySQL GIS needs extensive improvements 
in terms of functionality, reliablity and performance. 
We want to achive this by replacing the home grown gis computation core 
with boost geometry, just like PostGIS is using GEOS, so that
we have all features boost geometry can provide. Boost geometry
is more powerful and robust and keeps growing, we will grow with it. 
F-1: Usage or data format shall not change, existing user
code shall need no change at all.
F-2: Some type combinations which were not supported before
will be supported, specifically these are supported now:
within(point, point)
within(point, multipoint)
within(multipoint, point)
within(multipoint, multipoint)
within(multipoint, polygon)
within(multipoint, multipolygon)

intersects(point, multipoint)
intersects(multipoint, point)
intersects(multipoint, multipoint)
intersects(multipoint, polygon)
intersects(multipoint, multipolygon)
intersects(linestring, multilinestring)
intersects(multilinestring, linestring)
intersects(multilinestring, multilinestring)
intersects(polygon, multipoint)
intersects(multipolygon, multipoint)

equals(point, multipoint)
equals(multipoint, multipoint)
equals(multipoint, point)

disjoint(point, multipoint)
disjoint(multipoint, point)
disjoint(multipoint, multipoint)
disjoint(multipoint, polygon)
disjoint(multipoint, multipolygon)
disjoint(linestring, multilinestring)
disjoint(multilinestring, multilinestring)
disjoint(polygon, multipoint)
disjoint(multipolygon, multipoint)

cross(multipoint, linestring) 
cross(multipoint, multilinestring) 
cross(multipoint, polygon)
cross(multipoint, multipolygon)

overlaps(multipoint, multipoint)

F-3: Calling a relationship checking functions with an unsupported type
combination will return NULL result.
Unsupported geometries: cross/overlaps/touches with one or both geometry
collection argument isn't supported.

F-3: Calling a relationship checking functions with an undefined/unapplicable
type combination will return false result.
Undefined/unapplicable (as defined by OGC) type combinations for each function: 
overlap: any combination of two argument types of different dimensions.
touches: any of the two argument types is point or multipoint.
crosses: the 1st argument is polygon or multipolygon, AND/OR the 2nd argument is
point or multipoint

F-4: Relation checks of two geometries of different srids is always not
supported, and client will get error ER_GIS_DIFFERENT_SRIDS, and the error will
cause the entire query to fail without producing any result even if only one row
has this error.

F-5: Max SRID number is 4294967295 (0xFFFFFFFF), if given srid larger than this,
the value's lower 4 bytes are used as the srid value (4 bytes unsigned integer).

F-6: If input polygon(in the form of WKT or WKB) has unclosed rings, the rings
are stored as closed ones by appending the 1st point into the ring's point
sequence. Historical data isn't affected or modified because MySQL didn't allow
open rings before.

F-7: Enable parsing input WKT of an empty geometry collection of this form:
GEOMETRYCOLLECTION(),which is also the output WKT of such an empty geometry
collection result of a GIS operation.
F-8: Enable using empty geometry collection as operand in GIS computations.
Don't simply regard empty geometry collection as a NULL value as before --- in
string terms an empty string is different from a NULL string value --- otherwise
a tree of nested GIS operations couldn't proceed if one intermediate value is an
empty collection, which should have been absolutely OK.

F-9: Enable parsing and using nested geometry collections of both WKB and WKT,
such a collection will be flattened and its basic components will be used in
various GIS operations to compute result.
I-1: New files: 
        Need boost library, need to download it in build system, and 
        add it to include directory lists in sql and libmysqld in build system.

I-2: No new syntax
I-3: No new commands
I-4: No new tools.
I-5: No impact on existing functionality.
It's notstraight forward to use boost geometry in mysql gis, because
 1) it doesn't support geometry collection(OGC defined),

 2) Not all 8 standard check functions are fully supported. Currently
boost::geometry::overlaps and boost::geometry::crosses is defined but doesn't
support any OGC geometry types. Other functions also don't support some type
combinations that we need.

 3) All the geometry types are separate and independent class templates, no
inheritance or polymorphism, and all the algorithm functions are function
templates requring geometry type parameters.

What we can and will do in this worklog is to reimplement the relation check
functions by using boost geometry as much as we can, and fall back to old gis
implementation if we can't implement a feature using boost geometry directly or
indirectly. And in the future when boost geometry support start to support more
type combinations we can easily use it instead.

All relation check functions have two parameters, given a pair of argument g1
and g2, for a relation check function, if the type combination is directly
supported by boost geometry, simply call the corresponding boost geometry
function template instantiated with g1's and g2's geometry types; This is static
dispatching --- we have to enumerate all the possible type combinations of g1
and g2, which are supported by each boost geometry relation check function
template, and instantiate the function template with the types, and construct
the boost geometry objects bg1 and bg2 from g1 and g2, and then call the
function with the arguments bg1 and bg2.

For the unsupported type combinations, try to indirectly use supported geometry
types of boost geometry to do further computing to get the result. Some type
combinations can be computed using the supported type combinations, e.g.
multipoint INTERSECTS polygon isn't directly supported by
boost::geometry::intersects, but we can use point INTERSECTS polygon to compute
the result, that is to say, call boost::geometry::intersects to
do the computation.

In order to work with existing gis code, we need to keep and use the existing
Geometry class and its children classes in existing mysql gis, and
use these classes in new implementation, and keep the geometry internal format
unchanged, also keep the sql functions GeomFromText/GeomFromWkb's internal 
format unchanged.

Construct boost geometry objects and call boost geometry algo functions in mysql
gis algo functions like Item_func_spatial_rel::val_int and
Item_func_spatial_operation::val_str, etc. 

Following is a complete list of type combinations for each relation check 
function that are implemented using boost geometry directly or indirectly 
via further computation:

1. Implemented by direct boost geometry calls

within point polygon
within point multipolygon
intersects point point
intersects point polygon
intersects point multipolygon
intersects linestring linestring
intersects polygon point
intersects polygon polygon
intersects polygon multipolygon
intersects multipolygon point
intersects multipolygon polygon
intersects multipolygon multipolygon
touches polygon polygon
touches polygon multipolygon
touches multipolygon polygon
touches multipolygon multipolygon
disjoint point point
disjoint point polygon
disjoint point multipolygon
disjoint linestring linestring
disjoint polygon point
disjoint polygon polygon
disjoint polygon multipolygon
disjoint multipolygon point
disjoint multipolygon polygon
disjoint multipolygon multipolygon
equals point point
equals linestring linestring
equals polygon polygon
equals polygon multipolygon
equals multipolygon polygon
equals multipolygon multipolygon

2. Computed type combinations
Following is a list of computed type combinations, which are NOT directly
supported by boost geometry, but can be computed using the type combinations
that boost geometry directly supports. 

For the symetric functions(intersects, equals, disjoint), code is written
without redundancy --- simply swap the two parameters and call the same function
again. some functions are of opposite meaning (intersects VS disjoint, and
contains VS within), we can achieve by parameter swap too. 

Geometry collection support is achieved indirectly for
within/contains/equals/intersects/disjoint, I won't list the types involving
geometry collection here, although they are supported.

2.1 within
	within(point, point),
	within(point, multipoint),
	within(multipoint, point),
	within(multipoint, multipoint),
	within(multipoint, polygon),
	within(multipoint, multipolygon)

2.2 intersects
many of these are achived by calling disjoint and negate the return value.
	intersects(point, multipoint),
	intersects(multipoint, point),
	intersects(multipoint, multipoint),
	intersects(multipoint, polygon),
	intersects(multipoint, multipolygon),
	intersects(linestring, multilinestring),
	intersects(multilinestring, linestring),
	intersects(multilinestring, multilinestring),
	intersects(polygon, multipoint),
	intersects(multipolygon, multipoint)

2.3 touches

2.4 equals
	equals(point, multipoint),
	equals(multipoint, multipoint),
	equals(multipoint, point)

2.5 disjoint
disjoint(point, multipoint),
disjoint(multipoint, point),
disjoint(multipoint, multipoint),
disjoint(multipoint, polygon),
disjoint(multipoint, multipolygon),
disjoint(linestring, multilinestring),
disjoint(multilinestring, multilinestring),
disjoint(polygon, multipoint),
disjoint(multipolygon, multipoint)

2.6 contains
simply call within with swapped arguments, no need for independent
implementation. supports the swapped type combinations of all those supported by

2.7 crosses
cross(multipoint, linestring) 
cross(multipoint, multilinestring) 
cross(multipoint, polygon), 
cross(multipoint, multipolygon), 

according to the definitions of 'crosses' by OGC, implement above 4 combinations
using "point within geometry" relation cheks, other combinations can't be
computed, although some of them seem so. 

Additionally, crosses always simply return false if given any point argument, or
both arguments are multipoint.

2.8 overlaps 
overlaps(multipoint, multipoint), 

Additionally, always simply returns false if given any point argument or given
two geometries of different dimensions.