GEOSEARCH bybox bug fixes and new fuzzy tester by yangbodong22011 · Pull Request #8375 · redis/redis

yangbodong22011 · 2021-01-21T11:23:36Z

[Edit]

Fix GEOSEARCH bybox width and height mismatch
Fix errors of GEOSEARCH bybox search due to projection of the box to a
trapezoid (when the meter box is converted to long / lat it's no longer a box).
Add GEOSEARCH bybox testing to the existing "GEOADD + GEORANGE randomized test"
Add new fuzzy test to stress test the bybox corners and edges
Add some tests for edge cases of the bybox algorithm

This PR add fuzzy test for GEOSEARCH command and fix the wrong order of widht and height parameters. As shown in the document, width is before height.

…gument

src/geo.c

tests/unit/geo.tcl

oranagra · 2021-01-21T21:25:28Z

@yangbodong22011 thank you for this PR.

this is not exactly the test i wanted, but maybe its is enough.
correct me if i'm wrong, this test just checks that the same calculations performed by redis and by the tcl code reach the same conclusion (and it does so with random coordinates.

what i was looking is more of a specific test that tests edge cases in the box code.
IIRC our implementation does something like this (converting a box into a circle):

i would like to test the 4 (or maybe just 2) green dots, and maybe the orange ones too, to see that they are handled correctly.

and i would like to do that on various different box shapes (horizontally wide, and horizontally narrow).
and i would like to places these boxes in various places on the globe (i.e. since our search grid is in a fixed positions, some bugs can reproduce on a certain long/lat position and not on another)

i didn't dig too much into the current test, if you can convince me that it covers the above concern, that would be great.
thank you.

Co-authored-by: Oran Agra <[email protected]>

tests/unit/geo.tcl

yangbodong22011 · 2021-01-27T17:06:48Z

Updated:

Fixed the error in latitude and introduced a trapezoid. To determine whether a point is in the trapezoid, use the ray-crossing Algorithm, reference: geohashGetDistanceIfInTrapezoid()
Add tcl test, in tcl, to judge whether a point is in the trapezoid, use another area Algorithm, reference: pointInBox(), it's different from c code.
Added a test that the point is very close to the box

NOTICE:

shape->bounds now are the 4 coordinates of the trapezoid.
use sqrt((width/2)^2 + (height/2)^2) for radius_meters, because in some case, max(height/2, widht/2) is not enough.

oranagra

@yangbodong22011 thank you!
i assume the improved tests failed quite consistently on the old implementation, right?

considering the equator problem i mentioned and maybe the bent edges, they should still fail from time to time, and we can improve both tests and the code.

tests/unit/geo.tcl

src/geohash_helper.c

src/geohash.h

tests/unit/geo.tcl

yangbodong22011 · 2021-02-02T17:34:54Z

Updated:

Fixed the error in latitude and introduced a trapezoid. To determine whether a point is in the trapezoid, use the ray-crossing Algorithm, reference: geohashGetDistanceIfInTrapezoid()

Add tcl test, in tcl, to judge whether a point is in the trapezoid, use another area Algorithm, reference: pointInBox(), it's different from c code.

Added a test that the point is very close to the box

NOTICE:

shape->bounds now are the 4 coordinates of the trapezoid.

use sqrt((width/2)^2 + (height/2)^2) for radius_meters, because in some case, max(height/2, widht/2) is not enough.

tcl test also use ray-crossing Algorithm, because the area algorithm is not suitable for concave polygons.
update fuzzy test, now 8 points are randomly generated.
When the trapezoid crosses the equator, the equator is selected as the narrowest.
When the box spans -180° or 180°, the searched point + or-360° is required, because 180° + 1° = -179°

@oranagra please have a look when you have time.

src/geohash_helper.c

tests/unit/geo.tcl

oranagra · 2021-02-02T22:08:41Z

tests/unit/geo.tcl

+    set bounds(0) [expr {$search_lon-$long_delta_top}]
+    set bounds(1) [expr {$search_lat+$lat_delta}]
+    set bounds(2) [expr {$search_lon+$long_delta_top}]
+    set bounds(3) [expr {$search_lat+$lat_delta}]
+    set bounds(4) [expr {$search_lon+$long_delta_middle}]
+    set bounds(5) $search_lat
+    set bounds(6) [expr {$search_lon+$long_delta_bottom}]
+    set bounds(7) [expr {$search_lat-$lat_delta}]
+    set bounds(8) [expr {$search_lon-$long_delta_bottom}]
+    set bounds(9) [expr {$search_lat-$lat_delta}]
+    set bounds(10) [expr {$search_lon-$long_delta_middle}]
+    set bounds(11) $search_lat


this test is a bit weak since it uses the same approach as the code it tests.
luckily we have the other new test (one that shifts the box by 1m) that covers for this.
but maybe we can improve this function too.

some wild idea is to try to convert the point that we're matching to the coordinate system of the box (km) rather than converting the box to long/lat.
consider:

the search box center being: lon1,lat1 (search_lon and search_lat right?)

the the point we're to match to the box: lon2,lat2 (lon and lat, right?)

we can create two new points, and measure the horizontal and vertical distance from the box center and match them to width and height.

# on one longitude (the one of the point being searched), # measure the distance between two lats (the lat of the point being search and the one of the center of the box) distance between lon2/lat1 and lon2,lat2 < height/2 ? # on one latitude (the one of the point being searched), # measure the distance between two lons (the lon of the point being search and the one of the center of the box) distance between lon1,lat2 and lon2,lat2 < width/2 ?

is this silly? (it's very late at night here), or could that work?

@yangbodong22011 what do you think of this?
if that algorithm indeed works, maybe instead of using it in the tests we should use it in redis itself?
i initially suggested it just so that we don't use the same algo in the tests as the one in redis (weak test), but if we prove that it's a valid algo, it might be more accurate than the polygon one.

@oranagra Thank you very much for your algorithm, i finished it at: #8445

tests/unit/geo.tcl

src/geohash_helper.c

Co-authored-by: Oran Agra <[email protected]>

yangbodong22011 · 2021-02-03T09:59:31Z

@oranagra Thank you very much for your detailed reply. I have updated the code, please have a look when you have time.

tests/unit/geo.tcl

src/geohash_helper.c

tests/unit/geo.tcl

oranagra · 2021-02-04T14:23:47Z

closed in favor of #8445

Add fuzzy test for GEOSEARCH and fix the order of widht and height ar…

ff4a7ad

…gument

oranagra changed the title ~~Add fuzzy test for GEOSEARCH and fix the order of widht and height argument~~ Fix GEOSEARCH box width and height mismatch and add fuzzy tester Jan 21, 2021

oranagra reviewed Jan 21, 2021

View reviewed changes

Fix GEOSEARCH box width and height mismatch

260dff3

Co-authored-by: Oran Agra <[email protected]>

oranagra reviewed Jan 24, 2021

View reviewed changes

tests/unit/geo.tcl Outdated Show resolved Hide resolved

tests/unit/geo.tcl Outdated Show resolved Hide resolved

yangbodong22011 added 3 commits January 27, 2021 21:58

Add more fuzzy test

6cb46f5

Fix the error of GEOSEARCH boundary search

d139487

Add one point test

4f20560

oranagra reviewed Jan 27, 2021

View reviewed changes

oranagra added the release-notes indication that this issue needs to be mentioned in the release notes label Jan 28, 2021

Fix the problem of trapezoid crossing the equator

56e9dd7

yangbodong22011 force-pushed the feature-geosearch-fuzzy-test branch from 070c045 to 56e9dd7 Compare February 2, 2021 17:18

oranagra reviewed Feb 2, 2021

View reviewed changes

Apply suggestions from Oran

702f3c1

Co-authored-by: Oran Agra <[email protected]>

yangbodong22011 force-pushed the feature-geosearch-fuzzy-test branch from 18529c9 to 702f3c1 Compare February 3, 2021 02:59

Add test and update function name and comments

36a887d

oranagra reviewed Feb 3, 2021

View reviewed changes

tests/unit/geo.tcl Show resolved Hide resolved

tests/unit/geo.tcl Show resolved Hide resolved

tests/unit/geo.tcl Show resolved Hide resolved

tests/unit/geo.tcl Show resolved Hide resolved

oranagra reviewed Feb 3, 2021

View reviewed changes

src/geohash_helper.c Show resolved Hide resolved

tests/unit/geo.tcl Show resolved Hide resolved

oranagra changed the title ~~Fix GEOSEARCH box width and height mismatch and add fuzzy tester~~ GEOSEARCH bybox bug fixes and new fuzzy tester Feb 3, 2021

yangbodong22011 mentioned this pull request Feb 4, 2021

GEOSEARCH bybox bug fixes and new fuzzy tester #8445

Merged

oranagra removed the release-notes indication that this issue needs to be mentioned in the release notes label Feb 4, 2021

oranagra closed this Feb 4, 2021

Conversation

yangbodong22011 commented Jan 21, 2021 • edited by oranagra Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

oranagra commented Jan 21, 2021

Uh oh!

Uh oh!

Uh oh!

yangbodong22011 commented Jan 27, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

yangbodong22011 commented Feb 2, 2021

Uh oh!

Uh oh!

Uh oh!

Uh oh!

oranagra Feb 2, 2021

Choose a reason for hiding this comment

Uh oh!

oranagra Feb 3, 2021

Choose a reason for hiding this comment

Uh oh!

yangbodong22011 Feb 4, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

yangbodong22011 commented Feb 3, 2021

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

oranagra commented Feb 4, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

yangbodong22011 commented Jan 21, 2021 •

edited by oranagra

Loading

yangbodong22011 commented Jan 27, 2021 •

edited

Loading