geo: geospatial builtin meta-issue (many easy issues inside, new 3D/M functions as of 2021-02-22!)

[otan]

Hello friends! We're going geospatial in the upcoming release 🚀 🌏 and I've unleashed a number of issues we need help with implementing!

I've got three tags with issues you could help us implement:

• A-geometry-builtins A-geometry-builtins Builtins which have geometry as args. (builtins related to geometry types)
• A-geometry-creations A-geometry-creation-builtins Builtins which have geometry as a return statement. (builtins related to geometry creation)
• A-geography-builtins A-geography-builtins Builtins which have geography as args. (builtins related to geography types)

The ones marked E-easy are the ones which are easy pickings. (These would be marked good first issue but that would overload the page) But if you felt like a challenge and want to pick a harder one, I'm only happy to egg you on 😛.

You can ping me on the issue itself if you have any questions.

Jira issue: CRDB-4244

[ravindrabhargava]

Hi, @otan
I am a newbie in GO, can I contribute here on this, please let me know Thanks

[otan]

please look at the tags for individual tasks. they contain examples and a general approach of what to change.

[jievince]

Hi, i know google s2 library is used for geography, but which library is used for geometry?

[otan]

@jievince we map the 2D plane onto S2 for indexing*, see https://www.cockroachlabs.com/blog/how-we-built-spatial-indexing/!

[jievince]

@jievince we map the 2D plane onto S2, see https://www.cockroachlabs.com/blog/how-we-built-spatial-indexing/!

Could 2d plane use s2 to build the index?

I have a look at the doc here:
https://www.cockroachlabs.com/docs/v20.2/functions-and-operators#spatial-functions
and many geography functions are commented by using s2, while the geometry version is not

[otan]

ah right, we use GEOS for calculations, but fallback to S2 for indexing.

[jievince]

Hi @otan, I'm still confused.
The document says:

st_covers(geography_a: geography, geography_b: geography) → bool 
- Returns true if no point in geography_b is outside geography_a.
- This function utilizes the S2 library for spherical calculations.
- This function variant will attempt to utilize any available spatial index.


st_covers(geometry_a: geometry, geometry_b: geometry) → bool 
- Returns true if no point in geometry_b is outside geometry_a.
- This function utilizes the GEOS module.
- This function variant will attempt to utilize any available spatial index.

1. Both the geography and geometry version says they could use spatial index. So both geography and geometry are using the google s2 library o build spatial index?
2. Geography version says it use s2 library for spherical calculations while geometry uses GEOS module. Does this statement mean how do they accurately calculate the rough data from index scans to filter out false positives?

[otan]

(1) yes, when we spatial index, we convert geometry into an S2 geography. this can generate false positives. you can look at the code that does this here:

cockroach/pkg/geo/geoindex/s2_geometry_index.go

Lines 177 to 205 in 46cef2c

	func (s *s2GeometryIndex) InvertedIndexKeys(
	c context.Context, g geo.Geometry,
	) ([]Key, geopb.BoundingBox, error) {
	// If the geometry exceeds the bounds, we index the clipped geometry in
	// addition to the special cell, so that queries for geometries that don't
	// exceed the bounds don't need to query the special cell (which would
	// become a hotspot in the key space).
	gt, clipped, err := s.convertToGeomTAndTryClip(g)
	if err != nil {
	return nil, geopb.BoundingBox{}, err
	}
	var keys []Key
	if gt != nil {
	r := s.s2RegionsFromPlanarGeomT(gt)
	keys = invertedIndexKeys(c, geomCovererWithBBoxFallback{s: s, geom: gt}, r)
	}
	if clipped {
	keys = append(keys, Key(exceedsBoundsCellID))
	}
	bbox := geopb.BoundingBox{}
	bboxRef := g.BoundingBoxRef()
	if bboxRef == nil && len(keys) > 0 {
	return keys, bbox, errors.AssertionFailedf("non-empty geometry should have bounding box")
	}
	if bboxRef != nil {
	bbox = *bboxRef
	}
	return keys, bbox, nil
	}

and here:

cockroach/pkg/geo/geoindex/s2_geometry_index.go

Lines 428 to 488 in 46cef2c

	// TODO(sumeer): this is similar to S2RegionsFromGeomT() but needs to do
	// a different point conversion. If these functions do not diverge further,
	// and turn out not to be performance critical, merge the two implementations.
	func (s *s2GeometryIndex) s2RegionsFromPlanarGeomT(geomRepr geom.T) []s2.Region {
	if geomRepr.Empty() {
	return nil
	}
	var regions []s2.Region
	switch repr := geomRepr.(type) {
	case *geom.Point:
	regions = []s2.Region{
	s.planarPointToS2Point(repr.X(), repr.Y()),
	}
	case *geom.LineString:
	points := make([]s2.Point, repr.NumCoords())
	for i := 0; i < repr.NumCoords(); i++ {
	p := repr.Coord(i)
	points[i] = s.planarPointToS2Point(p.X(), p.Y())
	}
	pl := s2.Polyline(points)
	regions = []s2.Region{&pl}
	case *geom.Polygon:
	loops := make([]*s2.Loop, repr.NumLinearRings())
	// The first ring is a "shell". Following rings are "holes".
	// All loops must be oriented CCW for S2.
	for ringIdx := 0; ringIdx < repr.NumLinearRings(); ringIdx++ {
	linearRing := repr.LinearRing(ringIdx)
	points := make([]s2.Point, linearRing.NumCoords())
	isCCW := geo.IsLinearRingCCW(linearRing)
	for pointIdx := 0; pointIdx < linearRing.NumCoords(); pointIdx++ {
	p := linearRing.Coord(pointIdx)
	pt := s.planarPointToS2Point(p.X(), p.Y())
	if isCCW {
	points[pointIdx] = pt
	} else {
	points[len(points)-pointIdx-1] = pt
	}
	}
	loops[ringIdx] = s2.LoopFromPoints(points)
	}
	regions = []s2.Region{
	s2.PolygonFromLoops(loops),
	}
	case *geom.GeometryCollection:
	for _, geom := range repr.Geoms() {
	regions = append(regions, s.s2RegionsFromPlanarGeomT(geom)...)
	}
	case *geom.MultiPoint:
	for i := 0; i < repr.NumPoints(); i++ {
	regions = append(regions, s.s2RegionsFromPlanarGeomT(repr.Point(i))...)
	}
	case *geom.MultiLineString:
	for i := 0; i < repr.NumLineStrings(); i++ {
	regions = append(regions, s.s2RegionsFromPlanarGeomT(repr.LineString(i))...)
	}
	case *geom.MultiPolygon:
	for i := 0; i < repr.NumPolygons(); i++ {
	regions = append(regions, s.s2RegionsFromPlanarGeomT(repr.Polygon(i))...)
	}
	}
	return regions

(2) when we filter out false positives, we use GEOS to do the final filter, as you say.

[czpmango]

yes, when we spatial index, we convert geometry into an S2 geography.

@otan Why need to convert geometry to S2 geography?
I found the implementation code for Covers(geometry, geometry), which seems to just call CartesianBoundingBox.Covers() and geos.Covers().

cockroach/pkg/geo/geomfn/binary_predicates.go

Lines 21 to 43 in 4d987b3

	// Covers returns whether geometry A covers geometry B.
	func Covers(a geo.Geometry, b geo.Geometry) (bool, error) {
	if a.SRID() != b.SRID() {
	return false, geo.NewMismatchingSRIDsError(a.SpatialObject(), b.SpatialObject())
	}
	if !a.CartesianBoundingBox().Covers(b.CartesianBoundingBox()) {
	return false, nil
	}
	// Optimization for point in polygon calculations.
	pointPolygonPair, pointKind, polygonKind := PointKindAndPolygonKind(a, b)
	switch pointPolygonPair {
	case PointAndPolygon:
	// A point cannot cover a polygon.
	return false, nil
	case PolygonAndPoint:
	// Computing whether a polygon covers a point is equivalent
	// to computing whether the point is covered by the polygon.
	return PointKindCoveredByPolygonKind(pointKind, polygonKind)
	}
	return geos.Covers(a.EWKB(), b.EWKB())
	}

So my question is, what scenarios is S2 suitable for and why is it used?
And what do you mean by "use GEOS to do the final filter"?

[otan]

@otan Why need to convert geometry to S2 geography?

see the blog post: https://www.cockroachlabs.com/blog/how-we-built-spatial-indexing/ - we need this for divide the space.

I found the implementation code for Covers(geometry, geometry), which seems to just call CartesianBoundingBox.Covers() and geos.Covers().

this is for the implementation of ST_Covers, not for the index accelerated search. if you're interested in 100% correct results, use GEOS or a similar library.

we use S2 for divide the space indexing so we can quickly answer queries such as "which shape1 s2 coverings overlap shape2's s2 coverings". this can generate imprecise results, so there are false positives. but as the s2 indexing gets rids of a large number of negatives, we can then further filter using GEOS for precise queries. if you will, it's kind of a similar mechanism to a bloom filter.

if you want to talk more about this, use the #spatial channel on our community slack - this issue is meant to track something else.

[czpmango]

@otan Why need to convert geometry to S2 geography?

see the blog post: https://www.cockroachlabs.com/blog/how-we-built-spatial-indexing/ - we need this for divide the space.

I found the implementation code for Covers(geometry, geometry), which seems to just call CartesianBoundingBox.Covers() and geos.Covers().

this is for the implementation of ST_Covers, not for the index accelerated search. if you're interested in 100% correct results, use GEOS or a similar library.

we use S2 for divide the space indexing so we can quickly answer queries such as "which shape1 s2 coverings overlap shape2's s2 coverings". this can generate imprecise results, so there are false positives. but as the s2 indexing gets rids of a large number of negatives, we can then further filter using GEOS for precise queries. if you will, it's kind of a bloom filter.

if you want to talk more about this, use the #spatial channel on our community slack - this issue is meant to track something else.

I got that, really thanks.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
10 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!