Timeline for Fastest point-in-polygon solution with billions of points over thousands of polygons
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2020 at 18:00 | history | tweeted | twitter.com/StackGIS/status/1270415382675931137 | ||
| Jun 9, 2020 at 15:43 | vote | accept | Jivan | ||
| Jun 9, 2020 at 14:56 | answer | added | CL. | timeline score: 2 | |
| Jun 9, 2020 at 10:41 | comment | added | Jivan | @CL this is a very good question — the answer is yes in this particular case | |
| Jun 9, 2020 at 9:20 | comment | added | CL. | Do you need to determine which polygon is hit? | |
| Jun 9, 2020 at 7:57 | comment | added | user30184 | Raster operations are sometimes much faster than playing with geometries. If you could convert your polygons into a raster in a clever way you migh be able to do point-in-polygon check by reading the pixel value. You should use binary encoding: first polygon=1, next=2, then 4, 8 and so on. Increase the value for overlapping polygons. If the pixel value is 10 you know that it comes from 2+8. | |
| Jun 8, 2020 at 19:01 | comment | added | user30184 | Sounds interesting. This one is quite fast as well youtu.be/_r4IqjGqGEY but the methods are not open. | |
| Jun 8, 2020 at 18:21 | comment | added | Jivan | @user30184 right, I didn't understand it like that — pretty agnostic to the environment, but the method I'm thinking of and have been trying works by 1. drawing bounding boxes around polygons to filter out the obvious non-matches, then 2. use the ray casting method (first on edge's bounding boxes to weed out obvious negatives once again for ray-casting, then checking actual intersections for the rest) — we're starting to get to very, very fast results compared to anything we've seen before | |
| Jun 8, 2020 at 17:16 | comment | added | user30184 | Please define your environment. I did not suggest you to use SpatiaLite but the method with simple polygons and tight spatial index. Or do you have evidense that the method is too slow? What is the speed that you need in some exact numbers? | |
| Jun 8, 2020 at 16:35 | comment | added | obchardon |
Should your point really be contained by your polygon or ST_intersects is acceptable ? ST_intersects is faster than ST_contains.
|
|
| Jun 8, 2020 at 16:17 | comment | added | Jivan | @user30184 it's a cool idea but doesn't get us anywhere near the kind of speed we need unfortunately | |
| Jun 8, 2020 at 15:21 | history | edited | julien |
edited tags
|
|
| Jun 8, 2020 at 7:23 | comment | added | user30184 | Splitting complex polygons with many vertices into smaller ones with less vertices is a relevant approach everywhere so consider PostGIS and ST_Subdivide as an example. Read a study with SpatiaLite gaia-gis.it/spatialite-3.0.0-BETA1/WorldBorders.pdf | |
| Jun 7, 2020 at 18:55 | comment | added | Gabriel De Luca | @Jivan, It occurs to me that if the points and polygons are defined in a half portion of the Earth they can be converted to a gnomonic projected system, in which the geodesic lines are straight lines, and apply the function on geometries instead of geographies. | |
| Jun 6, 2020 at 10:41 | history | reopened | Ian Turton | ||
| Jun 6, 2020 at 10:34 | comment | added | Jivan | @IanTurton this is irrelevant — I'm asking for a solution other than PostGIS, so whether I tried with PostGIS or not is not relevant. You don't know the reasons why we need to get away from PostGIS (performance is only one of the factors, but there are many others). | |
| Jun 6, 2020 at 7:20 | comment | added | Ian Turton | did you try to use postgis properly to get a solution? | |
| Jun 5, 2020 at 20:36 | comment | added | Jivan | @IanTurton sorry but I fail to see how the question you linked answers this question. The linked question is about tuning PostGIS, and my question is about finding a different solution apart from PostGIS. Could you undo the duplicate and reopen the question please? | |
| Jun 5, 2020 at 19:43 | comment | added | Jeremy Malczyk | The other technique you can use to do something like this quicky is to index the polygons using something like geohashes or S2 geometries. That allows you to run a point in polygon query without spatial tools since the intersection query is effective just some bit math. | |
| Jun 5, 2020 at 19:37 | comment | added | Jeremy Malczyk | @Jivan sure, I guess it depends on where this implementation is going and how much of your time you want to invest in it. Loading the data into BQ and running the same query you are using in Postgres would be the lowest level of effort. | |
| Jun 5, 2020 at 19:03 | comment | added | Ian Turton | And I would ignore the worry about rounding errors (no one cares about nanometers) | |
| Jun 5, 2020 at 19:02 | history | closed | Ian Turton | Duplicate of Fixing performance problem in PostGIS ST_Intersects | |
| Jun 5, 2020 at 17:59 | comment | added | Ian Turton | Postgis has a st_subdivide function, | |
| Jun 5, 2020 at 17:44 | comment | added | Jivan | if bigquery can do it in minutes, then I believe CUDA can do it in seconds? given we put that onto 16 parallelized GPUs? | |
| Jun 5, 2020 at 17:40 | comment | added | Jeremy Malczyk | Google's BigQuery can run a spatial join like this in a few minutes, with the same SQL you are using in PostGIS. Not free, but it handles much larger datasets than that. | |
| Jun 5, 2020 at 16:20 | comment | added | Jivan | @IanTurton triangles? it's gonna be a lot of them... but it also means we can compute them all at once on a GPU, if we write a bit of custom CUDA code | |
| Jun 5, 2020 at 16:19 | comment | added | Ian Turton | sub divide the polygons | |
| Jun 5, 2020 at 16:16 | history | asked | Jivan | CC BY-SA 4.0 |