geo,geoindex: use bounding box for geography coverings that are bad by sumeerbhola · Pull Request #51305 · cockroachdb/cockroach

sumeerbhola · 2020-07-10T19:02:51Z

This change uses a covererInterface implementation for geography
that notices when a covering is using top-level cells of all faces
and in that case uses the bounding box to compute the covering.

Also changed the bounding box calculation for geography shapes to
use only the points and not first construct s2.Regions. The latter
causes marginally bad shapes to continue to have bad coverings since
the bounding box also covers the whole earth.

Release note: None

cockroach-teamcity · 2020-07-10T19:02:59Z

This change is

sumeerbhola

btw, data driven tests that are not datadriven tests, like bbox_test.go are painful to modify.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan)

sumeerbhola

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan)

pkg/geo/parse_test.go, line 395 at r1 (raw file):

					ShapeType: geopb.ShapeType_Point,
					BoundingBox: &geopb.BoundingBox{
						LoX: 0.017453292519943295,

the values in the tests change since we are avoiding the roundtrip to s2.Point which is using X, Y, Z coordinates and not lat-lng.

pkg/geo/geogfn/covers_test.go, line 407 at r1 (raw file):

		{
			"POLYGON covers POINT lying inside latitudinal boundary",
			"POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))",

this "self intersecting" polygon was probably generating an earth size polygon so the buggy test was passing.

otan

Reviewed 1 of 8 files at r1.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan and @sumeerbhola)

pkg/geo/bbox.go, line 166 at r1 (raw file):

		flatCoords := g.FlatCoords()
		for i := 0; i < len(flatCoords); i += g.Stride() {
			rect = rect.AddPoint(s2.LatLngFromDegrees(flatCoords[i+1], flatCoords[i]))

this will not work for bounding boxes crossing lat/lng boundaries. you will need to use s2.RectBounder here.

pkg/geo/geogfn/covers_test.go, line 407 at r1 (raw file):

Previously, sumeerbhola wrote…

this "self intersecting" polygon was probably generating an earth size polygon so the buggy test was passing.

no this was deliberate. this should return true. you have passed the poles and generated an invalid bounding box.

pkg/geo/geogfn/intersects_test.go, line 192 at r1 (raw file):

			"POLYGON intersects POINT lying inside latitudinal boundary",
			"POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))",
			"POINT (150 85)",

same as above. this should be true for 88.

otan · 2020-07-10T19:42:38Z

pkg/geo/geogfn/covers_test.go, line 407 at r1 (raw file):

Previously, otan (Oliver Tan) wrote…

no this was deliberate. this should return true. you have passed the poles and generated an invalid bounding box.

(if you draw this out on a map, this polygon covers the north pole. try drawgeography,Example,,"POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))" on geoviz)

rytaft

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @sumeerbhola)

pkg/geo/bbox.go, line 148 at r1 (raw file):

// results in S2 and the other libraries we use. Therefore, instead of constructing s2.Region(s)
// from the shape, which will expose us to S2's validity checks, we use the points directly to
// compute the bounding box.

[nit] comments should be 80 columns wide

sumeerbhola

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan and @sumeerbhola)

pkg/geo/geogfn/covers_test.go, line 407 at r1 (raw file):

Previously, otan (Oliver Tan) wrote…

(if you draw this out on a map, this polygon covers the north pole. try drawgeography,Example,,"POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))" on geoviz)

ah yes, this bounding box logic change is totally misguided.

otan

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan and @sumeerbhola)

pkg/geo/bbox.go, line 168 at r2 (raw file):

	case *geom.Polygon:
		for i := 0; i < g.NumLinearRings(); i++ {
			rect = rect.Union(lineBBox(g.LinearRing(i), true /* isRing */))

does this have to be forced as CCW? I think the original code was this way to account for that.
(and was one of the reasons i let it be translated to S2 regions first -- s2 does this complex logic for us :P)

pkg/geo/bbox.go, line 206 at r2 (raw file):

}

func lineBBox(g flatGeom, isRing bool) s2.Rect {

can you add comments for and flatBBox and above what what the difference is ?

I'd probalbly rename it to lineS2Rect (and above) to make it a little clearer.

sumeerbhola

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan, @rytaft, and @sumeerbhola)

pkg/geo/bbox.go, line 148 at r1 (raw file):

Previously, rytaft (Rebecca Taft) wrote…

[nit] comments should be 80 columns wide

Done.

pkg/geo/bbox.go, line 166 at r1 (raw file):

Previously, otan (Oliver Tan) wrote…

this will not work for bounding boxes crossing lat/lng boundaries. you will need to use s2.RectBounder here.

Switched to using s2.RectBounder for line segments. I haven't changed the calculation for points.
This seems to work, but I need to think about this more.

pkg/geo/geogfn/covers_test.go, line 407 at r1 (raw file):

Previously, sumeerbhola wrote…

ah yes, this bounding box logic change is totally misguided.

Undid this change.

pkg/geo/geogfn/intersects_test.go, line 192 at r1 (raw file):

Previously, otan (Oliver Tan) wrote…

same as above. this should be true for 88.

Undid this change.

sumeerbhola

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan and @rytaft)

pkg/geo/bbox.go, line 168 at r2 (raw file):

Previously, otan (Oliver Tan) wrote…

does this have to be forced as CCW? I think the original code was this way to account for that.
(and was one of the reasons i let it be translated to S2 regions first -- s2 does this complex logic for us :P)

I added some test cases to bbox_test.go and it doesn't change the result. But I can't interpret a couple of results (same question as in covers_test.go)

pkg/geo/bbox.go, line 206 at r2 (raw file):

Previously, otan (Oliver Tan) wrote…

can you add comments for and flatBBox and above what what the difference is ?

I'd probalbly rename it to lineS2Rect (and above) to make it a little clearer.

Done

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

			"POLYGON does not cover POINT lying outside latitudinal boundary",
			"POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))",
			"POINT (170 88)",

Can you remind me why this returns false? It seems that this polygon covers the north pole and includes every latitude >= 85.
Hmm, this doesn't look like a correct polygon since it is going east from the prime meridian due to longitudes 150, 160, then after it loops around from 160 to -20, it then turns around to go back to -30. Am I missing something?

otan · 2020-07-31T22:57:14Z

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

Previously, sumeerbhola wrote…

Can you remind me why this returns false? It seems that this polygon covers the north pole and includes every latitude >= 85.
Hmm, this doesn't look like a correct polygon since it is going east from the prime meridian due to longitudes 150, 160, then after it loops around from 160 to -20, it then turns around to go back to -30. Am I missing something?

The point lies outside the box: https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxQb2x5Z29uLCwiUE9MWUdPTigoMTUwIDg1LCAxNjAgODUsIC0yMCA4NSwgLTMwIDg1LCAxNTAgODUpKSIKZHJhd2dlb2dyYXBoeSxQb2ludCwsIlBPSU5UICgxNzAgODgpIgo=

otan · 2020-07-31T22:58:15Z

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

Previously, otan (Oliver Tan) wrote…

The point lies outside the box: https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxQb2x5Z29uLCwiUE9MWUdPTigoMTUwIDg1LCAxNjAgODUsIC0yMCA4NSwgLTMwIDg1LCAxNTAgODUpKSIKZHJhd2dlb2dyYXBoeSxQb2ludCwsIlBPSU5UICgxNzAgODgpIgo=

Exaggerating the latitudes a little here -- https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxQb2x5Z29uLCwiUE9MWUdPTigoMTUwIDc1LCAxNjAgNzUsIC0yMCA3NSwgLTMwIDc1LCAxNTAgNzUpKSIKZHJhd2dlb2dyYXBoeSxQb2ludCwsIlBPSU5UICgxNzAgODApIgo=

160 -> -20 just goes to the other side of the pole.

sumeerbhola

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan and @rytaft)

pkg/geo/bbox_test.go, line 58 at r3 (raw file):

			&geopb.BoundingBox{LoX: 0.017453292519943292, LoY: 0.01745329251994285, HiX: 0.03490658503988659, HiY: 0.03490791314678354}},
		{geopb.SpatialObjectType_GeographyType, geom.NewPolygonFlat(geom.XY, []float64{150, 85, 160, 85, -20, 85, -30, 85, 150, 85}, []int{10}),
			&geopb.BoundingBox{LoX: -3.141592653589793, LoY: 1.4835298641951797, HiX: 3.141592653589793, HiY: 1.5707963267948966}},

I've changed this test to use the same polygon as in covers_test.go and in both orientations.

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

Previously, otan (Oliver Tan) wrote…

Exaggerating the latitudes a little here -- https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxQb2x5Z29uLCwiUE9MWUdPTigoMTUwIDc1LCAxNjAgNzUsIC0yMCA3NSwgLTMwIDc1LCAxNTAgNzUpKSIKZHJhd2dlb2dyYXBoeSxQb2ludCwsIlBPSU5UICgxNzAgODApIgo=

160 -> -20 just goes to the other side of the pole.

Duh, I forgot that the line connecting two points on the same latitude is a great circle and not a constant latitude line.
But is this a valid geography polygon? Don't the lines (160 85, -20 85) and (-30 85, 150 85) intersect? Is there a validity function for geography analogous to ST_IsValid for geometry?

otan

Reviewed 1 of 4 files at r2.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan, @rytaft, and @sumeerbhola)

pkg/geo/bbox.go, line 199 at r4 (raw file):

// geogPointsBBox constructs a bounding box, represented as a s2.Rect, for the set
// of points contained in g.
func geogPointsBBox(g flatGeom) s2.Rect {

probably just take geom.T and take the interface?

pkg/geo/bbox.go, line 213 at r4 (raw file):

	bounder := s2.NewRectBounder()
	flatCoords := g.FlatCoords()
	for i := 0; i < len(flatCoords); i += g.Stride() {

for linear rings, we always include the last point as the first point so i don't think you need the isRing condition. unless we deleted it somewhere.

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

Previously, sumeerbhola wrote…

Duh, I forgot that the line connecting two points on the same latitude is a great circle and not a constant latitude line.
But is this a valid geography polygon? Don't the lines (160 85, -20 85) and (-30 85, 150 85) intersect? Is there a validity function for geography analogous to ST_IsValid for geometry?

They look parallel to me: https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxMaW5lIEEsLCJMSU5FU1RSSU5HKDE2MCA4NSwgLTIwIDg1KSIKZHJhd2dlb2dyYXBoeSxMaW5lIEIsLCJMSU5FU1RSSU5HICgtMzAgODUsIDE1MCA4NSkgIgo=

There's no analogous ST_IsValid for Geography in PostGIS. We could do our own.

otan

Reviewed 1 of 8 files at r1, 1 of 4 files at r2, 3 of 4 files at r3, 1 of 1 files at r4.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan, @rytaft, and @sumeerbhola)

This change uses a covererInterface implementation for geography that notices when a covering is using top-level cells of all faces and in that case uses the bounding box to compute the covering. Also changed the bounding box calculation for geography shapes to use only the points and lines that are part of the shape instead of constructing s2.Regions. The latter causes bad shapes to continue to have bad coverings since the bounding box also covers the whole earth. Release note: None

sumeerbhola

TFTR!

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @otan, @rytaft, and @sumeerbhola)

pkg/geo/bbox.go, line 199 at r4 (raw file):

Previously, otan (Oliver Tan) wrote…

probably just take geom.T and take the interface?

Done.

pkg/geo/bbox.go, line 213 at r4 (raw file):

Previously, otan (Oliver Tan) wrote…

for linear rings, we always include the last point as the first point so i don't think you need the isRing condition. unless we deleted it somewhere.

Done.

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

Previously, otan (Oliver Tan) wrote…

They look parallel to me: https://geoviz.crdb.dev/#ZHJhd2dlb2dyYXBoeSxMaW5lIEEsLCJMSU5FU1RSSU5HKDE2MCA4NSwgLTIwIDg1KSIKZHJhd2dlb2dyYXBoeSxMaW5lIEIsLCJMSU5FU1RSSU5HICgtMzAgODUsIDE1MCA4NSkgIgo=

There's no analogous ST_IsValid for Geography in PostGIS. We could do our own.

Hmm -- I think they look parallel since it isn't showing the effect of the sphere wrapping around.

sumeerbhola · 2020-08-04T17:31:21Z

bors r+

otan · 2020-08-04T17:32:58Z

pkg/geo/geogfn/covers_test.go, line 414 at r2 (raw file):

POLYGON((150 85, 160 85, -20 85, -30 85, 150 85))

I think -30 is on the opposite side to 150, and 160 is opposite of -20 (both is an addition/subtraction of 180 degrees), hence forming a rectangle.

craig · 2020-08-04T18:27:29Z

Build succeeded:

GitHub CI (Cockroach)

sumeerbhola requested review from a team and otan July 10, 2020 19:02

sumeerbhola commented Jul 10, 2020

View reviewed changes

otan suggested changes Jul 10, 2020

View reviewed changes

rytaft reviewed Jul 10, 2020

View reviewed changes

sumeerbhola commented Jul 10, 2020

View reviewed changes

sumeerbhola force-pushed the badtestshape branch from ab7edc3 to 333bbb3 Compare July 10, 2020 22:11

blathers-crl bot requested a review from otan July 10, 2020 22:11

sumeerbhola force-pushed the badtestshape branch from 333bbb3 to 596476d Compare July 10, 2020 22:12

otan reviewed Jul 10, 2020

View reviewed changes

sumeerbhola commented Jul 10, 2020

View reviewed changes

sumeerbhola force-pushed the badtestshape branch from 596476d to 2afdb51 Compare July 28, 2020 14:39

blathers-crl bot requested a review from otan July 28, 2020 14:39

sumeerbhola commented Jul 28, 2020

View reviewed changes

sumeerbhola force-pushed the badtestshape branch from 2afdb51 to 7b3bbc8 Compare July 28, 2020 16:27

sumeerbhola force-pushed the badtestshape branch 2 times, most recently from e17dd00 to 1ae325e Compare August 3, 2020 14:24

sumeerbhola commented Aug 3, 2020

View reviewed changes

otan approved these changes Aug 3, 2020

View reviewed changes

otan reviewed Aug 3, 2020

View reviewed changes

sumeerbhola force-pushed the badtestshape branch from 1ae325e to ddff188 Compare August 4, 2020 16:41

sumeerbhola commented Aug 4, 2020

View reviewed changes

craig bot merged commit b380060 into cockroachdb:master Aug 4, 2020

Conversation

sumeerbhola commented Jul 10, 2020

Uh oh!

cockroach-teamcity commented Jul 10, 2020

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

otan left a comment

Choose a reason for hiding this comment

Uh oh!

otan commented Jul 10, 2020

Uh oh!

rytaft left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

otan left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

otan commented Jul 31, 2020

Uh oh!

otan commented Jul 31, 2020

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

otan left a comment

Choose a reason for hiding this comment

Uh oh!

otan left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola left a comment

Choose a reason for hiding this comment

Uh oh!

sumeerbhola commented Aug 4, 2020

Uh oh!

otan commented Aug 4, 2020

Uh oh!

craig bot commented Aug 4, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants