Support BYPOLYGON option for GEOSEARCH #1809
Conversation
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…ords Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…s of GEOSEARCH Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…centroid Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…roid of polygon. We can choose to not support WITHDIST, COUNT, ASC/DESC for polygon if we want to. With this commit, we do support it Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…lean up Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## unstable #1809 +/- ##
============================================
- Coverage 71.05% 71.01% -0.04%
============================================
Files 123 123
Lines 66106 66201 +95
============================================
+ Hits 46971 47014 +43
- Misses 19135 19187 +52
🚀 New features to boost your workflow:
|
src/geohash_helper.c
Outdated
| @@ -280,3 +365,21 @@ int geohashGetDistanceIfInRectangle(double width_m, | 8000|||
| *distance = geohashGetDistance(x1, y1, x2, y2); | |||
| return 1; | |||
| } | |||
|
|
|||
| /* Check if a point is in a polygon using ray casting. */ | |||
| int geohashGetDistanceIfInPolygon(double x1, double y1, double *xy, double (*vertices)[2], int num_vertices, double *distance) { | |||
There was a problem hiding this comment.
Do we need to distinguish whether the point is on the edge?
There was a problem hiding this comment.
Thank you , this is a good question. I thought about this during implementation.
It is unlikely that a point will be on the an edge of a polygon to the exact precision (except for the very clear cases) - so the BYPOLYGON search might not return any results even if we handle the "is a point on the edge" check.
You can let me know what you think based on your experience with GIS applications
There was a problem hiding this comment.
Refer ray cast algorithm by W. Randolph Franklin https://github.com/tair-opensource/TairGis/blob/main/src/spatial/polyraycast.c#L157
There was a problem hiding this comment.
I will look into the linked algorithm and will get back to you here in the next day or two
There was a problem hiding this comment.
The current code in this PR is based on PNPOLY - Point Inclusion in Polygon Test by W. Randolph Franklin (WRF). See: https://wrfranklin.org/Research/Short_Notes/pnpoly.html
I read through the link you suggested (https://github.com/tair-opensource/TairGis/blob/main/src/spatial/polyraycast.c#L157).
- From reading the code, the algorithm looks exactly the same as this PR with two additional cases handled: (1) it uses cross product to check if a point is on the line & segment (2) checks if a point is on the vertex.
- It seems more computationally expensive to handle these two edge cases which will not be caught because it compares to the exact floating point precision since it using
==(instead of eplison)
Specifically the linked code has edge case handling using == which will very rarely be true unless the point is exactly on the vertex or segment/line.
This seems unlikely to occur unless we are using test data or a geographically very small polygon and set of coordinates
if (a.x == b.x && a.y == b.y) {
if (p.x == a.x && p.y == a.y) {
return RAY_ON;
}
return RAY_OUT;
}
// try to check if p is on line ab and p is on segment ab.
if (((a.x <= p.x && p.x <= b.x) || (b.x <= p.x && p.x <= a.x)) && ((a.y <= p.y && p.y <= b.y) || (b.y <= p.y && p.y <= a.y)) && (p.y - a.y) * (b.x - a.x) == (p.x - a.x) * (b.y - a.y)) {
return RAY_ON;
}
…oint on vertex and point on segment/line Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…point on vertex and point on segment/line Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
…nly use cartesian coordinates to calculate the centroid Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
|
Major decision approved as long as there are no additional API, config, or info changes. Once the PR is closed we can merge it. |
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
Signed-off-by: KarthikSubbarao <karthikrs2021@gmail.com>
|
@yangbodong22011 / @valkey-io/core-team - You can take a look when you have time |
This PR implements the
BYPOLYGONsearch (described here: #1755) for the GEOSEARCH and GEOSEARCHSTORE valkey commands